Complexity Atlas
HE
Source-backed question

תהא Φ נוסחה בוליאנית מצורת CNF עם n משתנים ופחות מ- n logn פסוקיות. בכל פסוקית יש בדיוק m ליטרלים ממשתנים שוני…

1Exams0Assignments0Lessons1Source documents
שאלת רב־ברירהq-733a2becfe93

נוסח השאלה

תהא ΦΦ נוסחה בוליאנית מצורת CNF עם n משתנים ופחות מ−nlogn- n^{logn} פסוקיות. בכל פסוקית יש בדיוק m ליטרלים ממשתנים שונים (אך כמובן שבין פסוקיות שונות המשתנים אינם המשתנים בהכרח שונים). מבין ערכי m הבאים, מהו ה- m המינימלי שיבטיח שהנוסחה ΦΦ תהיה בוודאות ספיקה? (רמז: חישבו על השמה אקראית).

  1. אm = log^2 n.
  2. בm = logn.
  3. גm = logn · loglogn.
  4. דm = n^{log^2 n}.
  5. הm = n^{logn}.
  6. וm = n^{loglogn}.

תמלול ראשון מתוך עמוד המקור ב־tools/summary/.work. צילום העמוד מצורף למטה כדי שאפשר יהיה לאמת סימון מתמטי וניסוח.

Exact provenance

Appearances by source document

Each card is a genuinely distinct file. Printed versions inside one PDF stay in that card and do not inflate the sitting count.

Exam

2024 A · moed B

נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 2.pdf

Question 11Page 5Visual reading
View source scan — page 5Source page 5 from נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 2.pdf Open full size
Further practice

These are topic and lesson matches, not identical appearances.

Assignment1. תהא נוסחה בוליאנית מצורת 5CNF בעלת m הסגרים, שבכל אחד מהם מופיעים חמישה משתנים שונים, בחיוב או בשלילה. 1. חשבו את תוחלת מספר ההסגרים המסופקים בנוסח…Topically related — not a duplicateAssignmentבכל סעיף מוצגות טענה ואלגוריתם. קבעו אם האלגוריתם מגדיר רדוקציית זמן פולינומי המוכיחה את הטענה, והוכיחו את קביעתכם. נשתמש בהגדרות: - נוסחת CNF ספיקה ב…Topically related — not a duplicateAssignmentהוכיחו שבעיות ההכרעה הבאות שייכות ל-P. 1. קלט: נוסחה בוליאנית מצורת 1CNF. שאלה: האם ספיקה? 2. קלט: נוסחה בוליאנית מצורת CNF. שאלה: האם קיימת השמה שנות…Topically related — not a duplicateAssignmentלכל אחת מבעיות ההכרעה שלהלן קבעו מהי מחלקת הסיבוכיות הקטנה ביותר ביחס להכלה שאליה ידוע שהיא שייכת מבין המחלקות P,NP,coNP,EXP. הוכיחו את קביעותיכם. 1.…Topically related — not a duplicateAssignment1. נגדיר את בעיית ההכרעה A כלהלן: קלט: נוסחה בוליאנית מצורת CNF ומספר טבעי k. שאלה: האם המספר המרבי של הסגרים שהשמה יכולה לספק בנוסחה הוא בדיוק k? 1.…Topically related — not a duplicateAssignmentמולטיגרף הוא גרף לא מכוון שעשויות להיות בו קשתות מקבילות ולולאות. הקלט לבעיית Max-Cut-Multi הוא מולטיגרף G=(V,E) ומספר טבעי k, והשאלה היא האם קיים חתך…Topically related — not a duplicate

Near variants — not duplicates