Question

classification_p_np
sat

בהנחה ש-PNPP \neq NP עבור כל אחת מהשפות הבאות קבעו האם היא ב-PP או לא. הוכיחו את תשובתכם.

1. }\}מתקיים φSAT\varphi \in SAT ויש בו לפחות 100 פסוקיות L1={φ:L_1 = \{\varphi :

2. }\}מתקיים φSAT\varphi \in SAT ויש בה לכל היותר 100 פסוקיותL2={φ:L_2 = \{\varphi :

3. }\}מתקיים φSAT\varphi \in SAT מכיל nn משתנים ולפחות 2n2^n פסוקיותL3={φ:L_3 = \{\varphi :

1

Answers

1. נראה ש-L1PL_1 \notin P על ידי רדוקציה מ-SAT:

f(φ)=φi=1100(zi)f(\varphi) = \varphi \bigwedge_{i = 1}^{100} (z_i)

כאשר z1z100z_1 \ldots z_{100} משתנים שלא מופיעים ב-φ\varphi.

קל לראות ש-φφi=1100(zi)L1\varphi \iff \varphi \bigwedge_{i = 1}^{100} (z_i) \in L_1.

2. נתאר אלגוריתם חיפוש יעיל שמכריע את L2L_2. על קלט φ=c1ck\varphi = c_1 \land \ldots \land c_k

  • אם k>100k > 100 דחה
  • עבור 1ik1 \leq i \leq kבחר ליטרל מ-c1c_1 ספק אותו והסר את כל הליטרלים עם אותו משתנה מכל שאר הפסוקיות.
  • בדוק רקורסיבית אם c2ckc_2 \land \ldots \land c_k (אחרי הסרת הליטרלים המתאימים) ספיק.
  • אם כן קבל
  • אחרת החזר את הליטרלים לפסוקיות ובחר ליטרל חדש ב-c1c_1 ואם אין כזה דחה.

סיבוכיות האלגוריתם היא O(n100)O(n^{100})וקל לוודא את הנכונות שלו.

3. ניתן להכריע את L3L_3 על ידי חיפוש ממצה על כל ההשמות האפשריות (2n2^n) בזמן שהוא פולינומי באורך הקלט (לפחות 2n2^n).

1
Feedback