מפת הסיבוכיות
EN
שאלה מבוססת מקור

4. עבור מספר טבעי k וקבוצה A 0,1,...,k נגדיר את בעיית ההכרעה kSAT A כלהלן. קלט: נוסחה בוליאנית φ מצורת kCNF. ש…

0בחינות0מטלות1שיעורים1מסמכי מקור
שאלה פתוחהq-ec8518bbf0c6

נוסח השאלה

  1. עבור מספר טבעי k וקבוצה A⊆0,1,...,kA \subseteq {0,1,...,k} נגדיר את בעיית ההכרעה kSATAkSAT_A כלהלן. קלט: נוסחה בוליאנית φφ מצורת kCNF. שאלה: האם קיימת השמה עבור משתני הנוסחה φφ שבהצבתה מתקיים שבכל הסגר של φφ מספר הליטרלים שערכם True שייך לקבוצה A? למשל, בבעיה 3SAT2,33SAT_{2,3}, הקלט הוא נוסחה בוליאנית מצורת 3CNF, ויש לקבוע אם קיימת עבורה השמה שמספקת בכל הסגר בדיוק שניים או בדיוק שלושה ליטרלים. (ג) הוכיחו כי לכל k, מתקיים kSATk∈PkSAT_{k} \in P. הוכחה: יהי k∈INk\in IN. נוכיח:kSATk∈P: kSAT_{k} \in P. נתבונן באלגוריתם הבא - על קלט φφ שלב 1: לכל משתנה x המופיע בנוסחה, בדוק האם x ו-x̄ מופיעים שניהם בנוסחה. אם כן, דחה. 2 קבל. ניתוח זמן ריצה- לכל משתנה x, האלגוריתם עובר על כל הנוסחה. זמן ריצה −O(∣φ∣2)- O(|φ|^2). ניתוח סמנטי- נראה כי האלגוריתם מכריע את kSATkkSAT_{k}. יהי φφ נוסחה. נניח−<φ>∈kSATk- <φ>\in kSAT_{k}: אזי קיימת השמה σσ עבור משתני הנוסחה φφ שבהצבתה מתק״ם שבכל הסגר של φφ מס' הליטרלים שערכם T הוא k בכל הסגר k ליטרלים, לכן עבור ההשמה σσ, כל משתני φφ מקבלים ערך T. לכן ב−φ-φ אין משתנה ושלילתו. נניח- ב−φ-φ אין משתנה ושלילתו- נגדיר השמה עבור משתני הנוסחה φφ שנותנת ערך T לכל ליטרל המופיע ב−φ-φ. לכל משתנה x- σ(x) = { T x מופיע ב-φ (בצורה חיובית) σ(x) = { F אחרת לכן,<φ>∈kSATk, <φ>\in kSAT_{k} מכאן,kSATk∈P, kSAT_{k} \in P.

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

ייחוס מדויק

מופעים לפי מסמך מקור

כל כרטיס הוא קובץ שונה באמת. גרסאות או שאלונים כפולים באותו PDF מוצגים בתוך אותו כרטיס ואינם מגדילים את מספר המועדים.

שיעור

שיעור 26-תרגילים.pdf

שיעור 26-תרגילים.pdf

שאלה 4עמוד 2קריאה חזותית

העמודים שמהם זה נכתב

3 עמודים

העמודים נבחרו לפי חפיפת מילים בין הטקסט כאן לתמלול העמוד — לא אומתו ידנית. הם הצעה לבדיקה, לא ציטוט.

תרגול המשך

אלו התאמות לפי נושא ושיעור — לא מופעים זהים של אותה שאלה.

מטלהעבור כל אחת ממחלקות הסיבוכיות שלהלן, קבעו האם היא מכילה את המחלקה NP, האם NP מוכלת בה, והאם היא שווה לה, אם ידוע. אחרת הוכיחו כי השאלה שקולה לשאלה פתו…דומה בנושא — לא כפילותמטלה1. הוכיחו כי RP NP. 2. הוכיחו כי BPP PSPACE. 3. הוכיחו כי מחלקת הסיבוכיות RP סגורה לחיתוך, כלומר שאם A,B RP אז A B RP. 4. זהו את מחלקות הסיבוכיות שלהל…דומה בנושא — לא כפילותבחינהנתונות מחלקות הסיבוכיות הבאות. I. המחלקה C 1 היא מחלקת כל השפות A Σ* עבור קיימת מכונת טיורינג אי-דטרמיניסטית M וקיימים c 1 כך שלכל x Σ*, אם x A אז קיי…דומה בנושא — לא כפילותבחינהנתונות מחלקות הסתביכויות הבאות. I. המחלקה C 1 היא כל השפות A Σ* עבורן קיימת מכונת טיורינג אי-דטרמיניסטית M וקיים c 1 כך שלכל x Σ*, אם x A אז כל ריצה ש…דומה בנושא — לא כפילותבחינהלפניכם 2 מחלקות סיבוכיות: • C 1 – מחלקת השפות A * עבורן קיים c 1 כך שקיימת מכונת טיורינג אי-דטרמיניסטית M, כך שלכל x * מתקיים: אם x A אז קיימת ריצה של…דומה בנושא — לא כפילותבחינהתהא D מחלקת השפות A Σ* עבורן קיימים מכונת טיורינג M עם זמן ריצה פולינומיאלי ופולינום q כך שלכל x Σ* מתקיים: אם x A אז Pr r ~ 0,1 q(|x|)[M(x,r) = True]…דומה בנושא — לא כפילות