Complexity Atlas
HE
Source-backed question

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

0Exams0Assignments1Lessons1Source documents
שאלה פתוחה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. צילום העמוד מצורף למטה כדי שאפשר יהיה לאמת סימון מתמטי וניסוח.

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.

Lesson

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

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

Question 4Page 2Visual reading

The pages this was written from

3 pages

These pages were chosen by word overlap between the text here and the page's transcription — nobody has verified them. Treat them as a lead to check, not a citation.

Further practice

These are topic and lesson matches, not identical appearances.

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