Question

classification_p_np
sat
proof

בשאלה זו φ\varphi הוא פסוק CNF, ו-nn מספר המשתנים ב φ\varphi. כמו כן נניח ש-P̸=NPP \neq NP.

א. קבעו האם השפות הבאות הן ב-PP והאם הן ב-NPCNPC.

הערה: השמה נותנת ערכים אך ורק למשתני הפסוק.

  1. }\}קיימות (לפחות) 22 השמות שונות המספקות את φ\varphiSAT2={φ:\text{SAT}_2 = \{\varphi :
  2. }\}קיימות 2n2^n השמות שונות המספקות את φ\varphiSAT2n={φ:\text{SAT}_{2^n} = \{\varphi :

ב. הוכיחו/הפריכו: קיימת מ"ט פולינומית אשר בהינתן פסוק φ\varphi והשמה מספקת τ\tau פולטת השמה מספקת τ̸=τ\tau' \neq \tau אם יש כזאת.

1

Answers

1. נראה ש-SAT2/P\text{SAT}_2 \notin P על ידי רדוקציה מ-SAT\text{SAT}:

f(φ)=φ=φ(zz)f(\varphi) = \varphi' = \varphi \land (z \lor \overline{z}) כאשר zz משתנה חדש שלא קיים ב-φ\varphi.

נשים לב שעבור שלכל השמה ל-φ\varphi', הערך שהיא מציבה ב-zz אינו משנה את הערך של φ\varphi' ולכן או שקיימות לפחות שתי השמות שמספקות את φ\varphi' או שלא קיימות כלל. מכאן ש-φSAT    φSAT2\varphi \in \text{SAT} \iff \varphi' \in \text{SAT}_2.

קל לראות שהרדוקציה פולינומית.

2. נשים לב ש-2n2^n הוא מספר ההשמות האפשריות לפסוק עם nn משתנים ולכן פסוק הוא בשפה אמ"מ הוא טאוטולוגיה וזה קורה אמ"מ בכל פסוקית כל משתנה מופיע אמ"מ השלילה שלו מופיע וזה תנאי שניתן לוודא ביעילות. לכן SAT2nP\text{SAT}_{2^n} \in \text{P}.

ב. נראה שבעזרת מ"ט כזו אפשר להכריע את SAT בזמן פולינומי:

בהינתן פסוק CNF, φ=C1Cm\varphi = C_1 \land \ldots \land C_m עם nn משתנים, נבנה פסוק חדש φ=(C1z)(Cmz)(x1z)(xnz)\varphi' = (C_1 \lor z) \land \ldots \land (C_m \lor z) \land (x_1 \lor \overline{z}) \land \ldots \land (x_n \lor \overline{z}).

כאשר x1,,xnx_1, \ldots, x_n משתני הפסוק המקורי ו-zzמשתנה חדש.

כעת נניח כי קיימת מ"ט פולינומית, MM, כמתואר. נריץ אותה על φ\varphi' וההשמה (המספקת) שנותנת לכל המשתנים ערך TT. נראה ש-MM תפלוט השמה נוספת אמ"מ φ\varphi ספיק:

נניח ש-φ\varphi ספיק ו-τ\tauהשמה שמספקת אותו, נרחיב את τ\tau כך ש-τ(z)=F\tau(z) = F. קל לראות שזאת גם השמה מספקת.

מצד שני, אם MM החזירה השמה נוספת τ\tau' אז קל לראות ש-τ(z)=F\tau'(z) = F ולכן, τ\tau', מוגבלת למשתנים של φ\varphi, היא השמה מספקת.

מכיוון שהנחנו ש-P̸=NP\text{P} \neq \text{NP} אז לא קיימת מ"ט כזאת.

2
Feedback