ריפוד פסוקיות קצרות

3SAT ≤p 3SAT=

תהי $\mathrm{3SAT}^{=}$ הבעיה שבה כל פסוקית מכילה בדיוק שלושה ליטרלים. אז $\mathrm{3SAT}\le_p\mathrm{3SAT}^{=}$ , ולכן גם $\mathrm{3SAT}^{=}$ היא NP-שלמה.

הבנייה

על נוסחת 3CNF $\varphi$ , נטפל בכל פסוקית לפי אורכה, עם משתנים חדשים $y,y'$ לכל פסוקית בנפרד:

אורך 3: משאירים כמו שהיא.
אורך 2, $C=\ell_1\vee\ell_2$ : מחליפים ב- $(\ell_1\vee\ell_2\vee y)\wedge(\ell_1\vee\ell_2\vee\bar y)$ .
אורך 1, $C=\ell_1$ : מחליפים ב- $(\ell_1\vee y\vee y')\wedge(\ell_1\vee y\vee\bar y')\wedge(\ell_1\vee\bar y\vee y')\wedge(\ell_1\vee\bar y\vee\bar y').$

המחשה

v: x₁ = F, x₂ = F, x₃ = T

ליטרל של φ

נכונות — שני הכיוונים

3SAT ∈ ⟹ 3SAT= ∈

נניח ש- $\varphi$ ספיקה על ידי $v$ . נרחיב את $v$ למשתני העזר באופן שרירותי (נאמר $y=y'=0$ ). כל פסוקית מקורית $C$ מסופקת על ידי $v$ , כלומר קיים בה ליטרל $\ell$ עם $v(\ell)=1$ ; אותו $\ell$ מופיע בכל אחת מהפסוקיות שהחליפו את $C$ , ולכן כולן מסופקות ללא תלות בערכי $y,y'$ . לכן הפלט ספיק.

3SAT= ∈ ⟹ 3SAT ∈

נניח שהפלט ספיק על ידי $v$ , ונצמצם את $v$ למשתני $\varphi$ . תהי $C$ פסוקית של $\varphi$ ; נראה שהיא מסופקת.

אם $|C|=3$ היא מופיעה כמות שהיא בפלט ולכן מסופקת.
אם $C=\ell_1\vee\ell_2$ : נניח בשלילה $v(\ell_1)=v(\ell_2)=0$ . אחד מבין $y,\bar y$ מקבל $0$ תחת $v$ , ולכן אחת משתי הפסוקיות $(\ell_1\vee\ell_2\vee y)$ , $(\ell_1\vee\ell_2\vee\bar y)$ אינה מסופקת — סתירה.
אם $C=\ell_1$ : נניח בשלילה $v(\ell_1)=0$ . הזוג $(v(y),v(y'))$ הוא אחד מארבעת הצירופים, ולכל צירוף קיימת בדיוק אחת מארבע הפסוקיות שבה שני ליטרלי העזר מקבלים $0$ ; אותה פסוקית אינה מסופקת — סתירה.

לכן $v$ מספקת כל פסוקית של $\varphi$ , כלומר $\varphi$ ספיקה.

סיבוכיות הרדוקציה

זמןO(|φ|)

מקוםO(|φ|)

גודל הפלט≤ 4|φ|

מעבר יחיד על הפסוקיות. הפלט גדל פי $4$ לכל היותר, במקרה הקיצוני שבו כל הפסוקיות באורך $1$ .

מה זה קונה

שתי ההגדרות של 3SAT — "לכל היותר שלושה" ו"בדיוק שלושה" — שקולות תחת $\le_p$ , ולכן אפשר להשתמש בהנחת הנרמול "בכל פסוקית בדיוק שלושה ליטרלים שונים" בלי לאבד כלליות. הרדוקציות $\mathrm{3NAE}\le_p\mathrm{MAXCUT}$ ו- $\mathrm{3NAE}\le_p\mathrm{3COL}$ נשענות על ההנחה הזאת.

מלכודות

משתני העזר חייבים להיות חדשים לכל פסוקית בנפרד. אילו אותו $y$ שירת שתי פסוקיות, כיוון $\Leftarrow$ היה נשבר: הטיעון "אחד מבין $y,\bar y$ מקבל $0$ " הופך לתלות בין פסוקיות שאין עליה שליטה.

השרשרת

נשענת על

SAT ≤p 3SAT

מאיפה זה נקרא

שיעור 8משפט 7 (השלמה): הווריאנט "בדיוק 3 ליטרלים"

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