8The Reduction from SAT to 3SAT

בקצרה

• מוכיחים את הרדוקציה $\mathrm{SAT} \le_p \mathrm{3SAT}$: כל נוסחת CNF ניתנת לתרגום, בזמן פולינומי, לנוסחת 3CNF שקולת‑ספיקות לה.
• הכיוון ההפוך, $\mathrm{3SAT} \le_p \mathrm{SAT}$, הוא רדוקציית הזהות — ומכאן ש‑$\mathrm{3SAT} \in \mathrm{NP}$.
• בשילוב עם משפט קוק–לוין (SAT היא NP‑קשה; ראו שיעור 9) מתקבל ש‑$\mathrm{3SAT}$ היא NP‑שלמה. זו הבעיה הנוחה ביותר להתחיל ממנה רדוקציות, כי מבנה הקלט שלה נוקשה — בדיוק 3 ליטרלים לפסוקית לכל היותר.
• לב הבנייה: פסוקית באורך $k>3$ נחתכת לשתי פסוקיות באורכים $3$ ו‑$k-1$ בעזרת משתנה עזר חדש $z$ שמשמש כמתג. חוזרים על הצעד עד שכל הפסוקיות קצרות.
• החצי העדין הוא הכיוון ההפוך של הנכונות: להראות שמשתני העזר אינם יכולים לרמות — כל השמה שמספקת את $\hat\varphi$ מצטמצמת להשמה שמספקת את $\varphi$. זה מוכח כאן במלואו.
• בנוסף: השיעור פותח בשלוש טענות תשתית ($\mathrm{NP} \subseteq \mathrm{PSPACE}$, סגירות $\mathrm{P}$ תחת רדוקציות, ומשמעות NP‑שלמות), ונחתם בהדגמת כוח הביטוי של CNF — קידוד "בדיוק אחד", "לא ריק ולא מלא", ובעיית 8 המלכות כנוסחת CNF.

רקע ותלויות

השיעור הזה נשען כמעט כולו על שלושה דברים שכבר נלמדו. כדי לא לשלוח את הקורא אחורה, הנה הם במלואם.

1. המחלקה NP — שתי ההגדרות השקולות (שיעור 5–6). בהגדרה הראשונה, $A \in \mathrm{NP}$ אם קיימת מכונת טיורינג אי‑דטרמיניסטית $N$ שמכריעה את $A$ וזמן הריצה של כל ריצה שלה חסום בפולינום באורך הקלט. בהגדרה השנייה (הגדרת ה‑verifier), $A \in \mathrm{NP}$ אם קיימות מכונה דטרמיניסטית $M$ בזמן פולינומי ופולינום $q$ כך שלכל $x$: $x \in A \iff \exists\, w \in \{0,1\}^{q(|x|)} \ \text{ s.t. } \ M \text{ accepts } (x,w).$ המחרוזת $w$ נקראת עדות (witness). בשיעור 6 הוכח ששתי ההגדרות שקולות. בהוכחות כאן נוח לעבוד עם הגדרת ה‑verifier, וכך נעשה גם בשיעור 9 — כדברי המרצה, "דטרמיניזם תמיד יותר נוח לי, כי אני יודע כל צעד מה קורה בצעד הבא" [00:02:41, תמלול 15].

הערה על סימון המכונה: מכונת טיורינג נכתבת כאן כ‑$M=(Q,q_{start},F,\Sigma,\Gamma,\delta)$, כולל מצב ההתחלה. בכמה עמודי סיכום בקורס מושמט $q_{start}$; זו החלקה ידועה במקור והתיקון נעשה כאן במכוון.

2. הבעיה SAT (נלמדה בשיעור 7, ומופיעה בהקלטה [00:06:24]–[00:16:14]). $\mathrm{SAT}$ היא בעיית ההכרעה שקלטיה הם נוסחאות CNF, והשאלה היא האם הנוסחה ספיקה. בשיעור 7 הוכח $\mathrm{SAT} \in \mathrm{NP}$: המכונה האי‑דטרמיניסטית כותבת על סרט שני $n$ ביטים ($n$ = מספר המשתנים בנוסחה), מתייחסת אליהם כהשמה, ובודקת האם ההשמה מספקת. זמן הריצה $O(|\varphi|^2)$ [00:25:26].

3. רדוקציית זמן פולינומי (שיעור 7, [01:04:14]–[01:08:34]). $f:\Sigma^*\to\Sigma^*$ היא רדוקציית זמן פולינומי מ‑$A$ ל‑$B$ אם היא ניתנת לחישוב בזמן פולינומי ולכל $x$ מתקיים $x\in A \iff f(x)\in B$. מסמנים $A \le_p B$.

כיוון הרדוקציה — קראו את זה לאט. $A \le_p B$ פירושו ש‑$B$ היא הבעיה הקשה יותר: מי שיודע לפתור את $B$ יודע לפתור גם את $A$ (מתרגמים את הקלט ופותרים). הכיוון הזה מתהפך כל הזמן בדיבור, ולכן בכל פעם שנכתוב $\le_p$ נאמר גם במילים מי הקשה. בשיעור הזה נוכיח $\mathrm{SAT} \le_p \mathrm{3SAT}$ — כלומר 3SAT היא לפחות קשה כמו SAT, וזו בדיוק המטרה: להעביר את הקושי של SAT אל 3SAT.

4. שתי הערות מתודיות שחזרו בהקלטה ושייכות גם כאן.

• ברדוקציה אין פתרון של אף בעיה: "אני לא מכריע פה את IS ולא מכריע פה את CLIQUE, כל מה שאני עושה זה להמיר קלט" [01:11:50, 01:22:33].
• יש שני שלבים נפרדים לגמרי: בניית המכונה (שנעשית בלי לדעת אם הקלט בשפה — אם היינו יודעים, היינו מכריעים בזמן פולינומי), ורק אחר כך הוכחת הנכונות, שבה מותר להניח שהקלט בשפה [01:25:54].

הגדרות

הגדרה 1: משתנים, ליטרלים, פסוקיות ונוסחת CNF

יהיו $x_1,\dots,x_n$ משתנים בוליאניים, כלומר משתנים שיכולים לקבל את הערכים $\text{true}$ ו‑$\text{false}$ (נסמן גם $1$ ו‑$0$).

• ליטרל הוא משתנה או שלילתו: $x_i$ או $\bar x_i$.
• פסוקית (clause) היא "או" בין ליטרלים: $\ell_1 \vee \ell_2 \vee \dots \vee \ell_k$.
• נוסחת CNF (conjunctive normal form) היא "וגם" בין פסוקיות.

אינטואיציה. CNF היא נוסחה בוליאנית שנכפתה עליה צורה נוקשה מאוד: שתי שכבות בלבד, "או" בפנים ו"וגם" בחוץ. הנוקשות הזו היא בדיוק מה שהופך את SAT לבעיה נוחה לרדוקציות — קלט של SAT הוא אובייקט פשוט לתיאור, ולכן קל "לכתוב לתוכו" בעיות אחרות. כדי לספק נוסחת CNF צריך לספק את כל הפסוקיות, אבל בכל פסוקית מספיק ליטרל אחד מסופק [00:14:32].

דוגמה. $\varphi=(x_1 \vee \bar x_2) \wedge (\bar x_1 \vee x_3 \vee x_4 \vee \bar x_5)$ היא נוסחת CNF בת שתי פסוקיות.

אי‑דוגמה. $(x_1 \wedge x_2) \vee x_3$ אינה CNF — כאן ה"וגם" נמצא בפנים וה"או" בחוץ (זו צורת DNF). היא כמובן שקולה לנוסחת CNF כלשהי, אבל בתור מחרוזת קלט היא אינה חוקית עבור SAT.

הגדרה 2: השמה וסיפוק

השמה היא פונקציה $v$ שנותנת לכל אחד מהמשתנים $x_1,\dots,x_n$ ערך ב‑$\{0,1\}$. עבור ליטרל מסמנים $v(\bar x)=1-v(x)$. ההשמה מספקת פסוקית אם לפחות ליטרל אחד בה מקבל $1$, ומספקת נוסחת CNF אם היא מספקת כל אחת מפסוקיותיה. נוסחה נקראת ספיקה אם קיימת השמה שמספקת אותה.

דוגמה (מההרצאה, [00:12:20]–[00:13:56]). עבור $\varphi=(x_1\vee x_3 \vee x_4)\wedge(\bar x_1\vee x_2)\wedge(\bar x_2 \vee x_3 \vee \bar x_4)$ וההשמה $v(x_1)=1,\ v(x_2)=1,\ v(x_3)=0,\ v(x_4)=1$: הפסוקית הראשונה מסופקת על ידי $x_1$, השנייה על ידי $x_2$, אך בשלישית $\bar x_2=0,\ x_3=0,\ \bar x_4=0$ — ולכן $v$ אינה מספקת את $\varphi$. אם משנים ל‑$v(x_3)=1$ ההשמה כן מספקת. שימו לב: הנוסחה ספיקה, אך ההשמה הספציפית אינה מספקת — אלה שני דברים שונים.

הגדרה 3: נוסחת 3CNF

נוסחת CNF $\varphi$ נקראת נוסחת 3CNF אם כל פסוקית שלה מכילה לא יותר מ‑3 ליטרלים.

אינטואיציה ואי‑דוגמה. הנוסחה $(x_1\vee \bar x_2)\wedge(\bar x_1\vee x_3\vee x_4\vee \bar x_5)$ היא CNF ואף 5CNF ו‑4CNF, אבל אינה 3CNF, בגלל הפסוקית השנייה שאורכה 4. לעומת זאת $(x_1\vee\bar x_2)\wedge(x_3)$ היא 3CNF — פסוקיות באורך 2 ו‑1 מותרות, כי הדרישה היא "לכל היותר 3".

הערה חשובה על הגדרה זו. יש ספרים שמגדירים 3CNF כ"בדיוק 3 ליטרלים בכל פסוקית". ההבדל אינו מהותי (ראו משפט 7), אבל הוא משנה את פרטי הבנייה. בקורס הזה ההגדרה היא "לכל היותר 3", וזו ההגדרה שממנה נגזר האלגוריתם שלהלן — לכן אין בו טיפול נפרד בפסוקיות באורך 1 או 2.

הגדרה 4: הבעיות SAT ו‑3SAT

$\mathrm{SAT}=\{\langle\varphi\rangle \ : \ \varphi \text{ is a satisfiable CNF formula}\}$ $\mathrm{3SAT}=\{\langle\varphi\rangle \ : \ \varphi \text{ is a satisfiable 3CNF formula}\}$

כמו בהרצאה, לא נעסוק בפרטי הקידוד $\langle\cdot\rangle$: מניחים שהקלט מתקבל כמחרוזת תקינה שמתארת נוסחה, ואם אינו תקין — בודקים זאת בזמן פולינומי ודוחים [00:17:52]. נחזור לנקודה הזו כשנבנה את הרדוקציה, כי שם היא דורשת טיפול קטן אך אמיתי.

הגדרה 5: NP‑קשה ו‑NP‑שלמה

שפה $B$ נקראת NP‑קשה (NP-hard) אם לכל $A \in \mathrm{NP}$ מתקיים $A \le_p B$. שפה $B$ נקראת NP‑שלמה (NP-complete) אם $B$ NP‑קשה וגם $B\in\mathrm{NP}$.

אינטואיציה. NP‑קשה = "לפחות קשה כמו כל דבר ב‑NP", ולאו דווקא שייכת ל‑NP בעצמה. NP‑שלמה = "הכי קשה ב‑NP, ובתוך NP". סדר הכמתים קריטי: לכל שפה ב‑NP קיימת רדוקציה — לא קיימת רדוקציה אחת שמתאימה לכולן [00:01:08, תמלול 15].

משפטים והוכחות

משפט 1: $\mathrm{NP} \subseteq \mathrm{PSPACE}$

טענה. כל שפה ב‑$\mathrm{NP}$ ניתנת להכרעה במקום פולינומי.

הוכחה. תהא $A \in \mathrm{NP}$. לפי הגדרת ה‑verifier קיימות מכונה דטרמיניסטית $M$ שזמן ריצתה פולינומי — נסמן את הפולינום $p$ — ופולינום $q$, כך שלכל $x$: $x \in A \iff \exists\, w\in\{0,1\}^{q(|x|)}\ \text{ s.t. } \ M \text{ accepts } (x,w).$

נגדיר מכונה דטרמיניסטית $M_A$, על קלט $x$:

1. חשב את $q(|x|)$.
2. לכל $w \in \{0,1\}^{q(|x|)}$ בסדר לקסיקוגרפי (יש $2^{q(|x|)}$ אפשרויות):
   • 2.1 הרץ את $M$ על $(x,w)$.
   • 2.2 אם $M$ קיבלה — קבל.
3. דחה.

הנקודה שכל ההוכחה תלויה בה: בונים את $M_A$ כך שכל איטרציה של הלולאה תשתמש באותם תאים — לפני מעבר ל‑$w$ הבא מוחקים את סרט העבודה. מספר האיטרציות אקספוננציאלי, אבל המקום לא מצטבר.

נכונות. אם $x\in A$ אז קיים $w$ שעבורו $M$ מקבלת את $(x,w)$; מכיוון ש‑$M_A$ עוברת על כל המחרוזות באורך $q(|x|)$, היא תגיע ל‑$w$ הזה, שלב 2.2 יופעל, ו‑$M_A$ תקבל. אם $x\notin A$ אז לכל $w\in\{0,1\}^{q(|x|)}$ המכונה $M$ דוחה את $(x,w)$, לכן שלב 2.2 לא מופעל לעולם ו‑$M_A$ דוחה בשלב 3.

ניתוח מקום. $q$ פולינום, ולכן כתיבת $w$ ומונה הלולאה דורשות $O(q(|x|))$ תאים. הרצת $M$ על $(x,w)$: זמן הריצה של $M$ פולינומי ב‑$|(x,w)| \le |x|+|w| = |x|+q(|x|)$, ומכונה אינה יכולה לבקר ביותר תאים ממספר הצעדים שעשתה, ולכן המקום שהיא דורשת חסום ב‑$p(|x|+q(|x|))$. בסך הכול $\mathrm{space}_{M_A}(x) = O\big(q(|x|) + p(|x|+q(|x|))\big),$ וזהו פולינום ב‑$|x|$ — הרכבה וסכום של פולינומים הם פולינום. לכן $A \in \mathrm{PSPACE}$. $\blacksquare$

הערה: ההוכחה הזו היא הסיבה שלא ניתן לקוות ל"הפרדה בזול" בין $\mathrm{P}$ ל‑$\mathrm{NP}$ דרך מקום: כל $\mathrm{NP}$ יושבת בתוך $\mathrm{PSPACE}$, כלומר החיפוש האקספוננציאלי עולה הרבה זמן אך מעט מקום.

משפט 2: $\mathrm{P}$ סגורה כלפי רדוקציות פולינומיות

טענה. אם $A \le_p B$ ו‑$B\in\mathrm{P}$, אז $A\in\mathrm{P}$.

הוכחה. נניח $A \le_p B$. אז קיימת מכונה $M_{AB}$ שמחשבת את הרדוקציה, עם פולינום $P$ כך שלכל $x$ מתקיים $\mathrm{time}_{M_{AB}}(x) \le P(|x|)$, ולכל $x$: $x\in A \iff M_{AB}(x) \in B .$ נניח $B\in\mathrm{P}$. אז קיימת מכונה $M_B$ שמכריעה את $B$ עם פולינום $q$ כך שלכל $y$ מתקיים $\mathrm{time}_{M_B}(y)\le q(|y|)$.

נגדיר מכונה $M_A$, על קלט $x$:

1. חשב את $M_{AB}(x)$.
2. הרץ את $M_B$ על $M_{AB}(x)$ והחזר את אותה תשובה.

נכונות. אם $x\in A$ אז $M_{AB}(x)\in B$, לכן $M_B$ מקבלת את $M_{AB}(x)$, לכן $M_A$ מקבלת את $x$. אם $x\notin A$ אז $M_{AB}(x)\notin B$, לכן $M_B$ דוחה, לכן $M_A$ דוחה.

ניתוח זמן. שלב 1 לוקח לכל היותר $P(|x|)$ צעדים. לשלב 2 דרוש $q(|M_{AB}(x)|)$, ולכן צריך לחסום את אורך הפלט. מכונה שרצה $t$ צעדים אינה יכולה להאריך את הקלט ביותר מ‑$t$ תווים, ולכן $|M_{AB}(x)| \le \mathrm{time}_{M_{AB}}(x) + |x| \le P(|x|)+|x|,$ ומכאן ששלב 2 עולה לכל היותר $q\big(P(|x|)+|x|\big)$. סכום שני הביטויים הוא סכום והרכבה של פולינומים — ולכן פולינום. לכן $M_A$ מכריעה את $A$ בזמן פולינומי, כלומר $A\in\mathrm{P}$. $\blacksquare$

הערה: החסם על אורך הפלט הוא בדיוק הצעד ש"נבלע" בדרך כלל. בלעדיו לא הייתה סיבה ש‑$q$ מופעל על ארגומנט קטן, וההרכבה יכלה להתפוצץ. זו הסיבה שכדאי תמיד לכתוב $|f(x)| \le P(|x|)+|x|$ במפורש.

מסקנות (עמוד 3 בסיכום).

1. באותו אופן בדיוק — מחליפים את $\mathrm{P}$ במחלקה המתאימה ואת חסם הזמן בחסם המתאים — מקבלים ש‑$\mathrm{NP}$, $\mathrm{PSPACE}$, $\mathrm{NPSPACE}$, $\mathrm{EXP}$ ו‑$\mathrm{NEXP}$ כולן סגורות כלפי רדוקציות זמן פולינומי.
2. היחס $\le_p$ טרנזיטיבי: אם $A\le_p B$ דרך $f$ ו‑$B \le_p C$ דרך $g$, אז $g\circ f$ היא רדוקציה מ‑$A$ ל‑$C$; היא ניתנת לחישוב בזמן פולינומי כי $|f(x)|$ פולינומי ב‑$|x|$ (אותו חישוב בדיוק כמו למעלה), והנכונות היא שרשור של שתי שקילויות.
3. מכאן המסקנה המבצעית של כל התחום: מספיק למצוא בעיה קשה אחת. אם $A$ NP‑קשה ו‑$A \le_p B$, אז $B$ NP‑קשה — כי לכל $C\in\mathrm{NP}$ מתקיים $C \le_p A \le_p B$ ולפי הטרנזיטיביות $C\le_p B$.

משפט 3: משמעות NP‑שלמות

טענה. תהא $A$ שפה NP‑שלמה. אז $A\in\mathrm{P}$ אם ורק אם $\mathrm{P}=\mathrm{NP}$.

הוכחה. $(\Leftarrow)$ אם $\mathrm{P}=\mathrm{NP}$: מכיוון ש‑$A$ NP‑שלמה בפרט $A\in\mathrm{NP}=\mathrm{P}$. $(\Rightarrow)$ נניח $A\in\mathrm{P}$. ההכלה $\mathrm{P}\subseteq\mathrm{NP}$ ידועה. לכיוון השני, תהא $B\in\mathrm{NP}$ שרירותית. מכיוון ש‑$A$ NP‑קשה מתקיים $B\le_p A$, ומכיוון ש‑$A\in\mathrm{P}$, לפי משפט 2 מתקבל $B\in\mathrm{P}$. מכאן $\mathrm{NP}\subseteq\mathrm{P}$, ובסך הכול $\mathrm{P}=\mathrm{NP}$. $\blacksquare$

זו הסיבה שכל התחום מתעניין בבעיות NP‑שלמות: אלגוריתם פולינומי לאחת מהן מפיל את כולן. הצעד הבא — קיומה של בעיה NP‑קשה ראשונה — הוא משפט קוק–לוין: SAT היא NP‑קשה (שיעור 9). כל מה שנעשה כאן מתבסס עליו כקופסה שחורה.

משפט 4: $\mathrm{3SAT} \le_p \mathrm{SAT}$, ומכאן $\mathrm{3SAT}\in\mathrm{NP}$

טענה. $\mathrm{3SAT} \le_p \mathrm{SAT}$.

הוכחה. הרדוקציה היא פונקציית הזהות: בהינתן $\langle\varphi\rangle$ מחזירים $\langle\varphi\rangle$. זמן החישוב הוא זמן ההעתקה, כלומר $O(|\varphi|)$ — פולינומי. הנכונות: אם $\varphi$ נוסחת 3CNF ספיקה, אז בפרט $\varphi$ נוסחת CNF ספיקה (כל 3CNF היא CNF), כלומר $\langle\varphi\rangle \in\mathrm{SAT}$. ולהפך, אם $\langle\varphi\rangle\in \mathrm{SAT}$ ו‑$\varphi$ 3CNF, אז $\langle\varphi\rangle\in\mathrm{3SAT}$ לפי ההגדרה. (קלט שאינו 3CNF תקין נדחה על ידי שתי הבעיות ולכן אינו מפר את השקילות.) $\blacksquare$

מסקנה: $\mathrm{3SAT}\in\mathrm{NP}$. נובע ממשפט 4, מ‑$\mathrm{SAT}\in\mathrm{NP}$ (שיעור 7) ומסגירות $\mathrm{NP}$ תחת רדוקציות פולינומיות (מסקנה 1 למשפט 2). לחלופין ישירות: מנחשים השמה ובודקים.

הערה: בהקלטה של השיעור העוקב המרצה מזכיר בדיוק את זה: "הראנו גם את הרדוקציה בכיוון השני, שהיא כמעט הייתה טריוויאלית — הרדוקציה מחזירה לכל נוסחה את עצמה" [00:00:00, תמלול 15].

משפט 5 (הלמה המרכזית): נכונות צעד הפיצול

זהו הלב המתמטי של השיעור. נגדיר תחילה את הצעד הבודד.

אלגוריתם 1. על קלט $\varphi$, נוסחה מצורת CNF:

1. אם $\varphi$ היא כבר נוסחת 3CNF — החזר את $\varphi$.
2. אחרת, נסמן ב‑$C$ את הפסוקית הראשונה ב‑$\varphi$ שיש בה יותר מ‑3 ליטרלים, ונכתוב $C=\ell_1 \vee \ell_2 \vee \dots \vee \ell_k$ (כאשר $k>3$). נגדיר $C' = \ell_1 \vee \ell_2 \vee z \qquad (3 \text{ literals})$ $C'' = \ell_3 \vee \ell_4 \vee \dots \vee \ell_k \vee \bar z \qquad (k-1 \text{ literals})$ כאשר $z$ הוא משתנה חדש שאינו מופיע ב‑$\varphi$.
3. נגדיר את $\hat\varphi$ כנוסחה המתקבלת מ‑$\varphi$ על ידי החלפת $C$ ב‑$C' \wedge C''$ (במקומה, כך ש‑$C''$ נשארת הפסוקית הארוכה הראשונה).
4. החזר את $\hat\varphi$.

האינטואיציה — מה $z$ עושה. $z$ הוא מתג שאומר "הליטרלים הראשונים לא סיפקו את $C$, מישהו מאוחר יותר יסדר את זה". אם $z=1$ אז $C'$ מסופקת בזכות $z$ בלבד, ואז $\bar z=0$ ולכן $C''$ חייבת להיות מסופקת על ידי אחד מ‑$\ell_3,\dots,\ell_k$. אם $z=0$ אז $C''$ מסופקת בזכות $\bar z$ בלבד, ואז $C'$ חייבת להיות מסופקת על ידי $\ell_1$ או $\ell_2$. בשני המקרים "מישהו אמיתי" מתוך $\ell_1,\dots,\ell_k$ חייב להיות אמיתי — וזו בדיוק $C$.

בניסוח קומפקטי: לכל השמה $v$ למשתני $\varphi$, $v(C)=1 \iff \exists\, b\in\{0,1\}:\ v[z\mapsto b](C' \wedge C'')=1 .$ כלומר $C' \wedge C''$ אינה שקולה ל‑$C$ — היא שקולה לה רק אחרי שמכמתים קיומית את $z$. השקילות שאנחנו צריכים היא שקילות ספיקות (equisatisfiability), לא שקילות לוגית. זו נקודה שנופלים עליה במבחן.

טענה (משפט 5). תהא $\varphi$ נוסחת CNF, ונסמן ב‑$\hat\varphi$ את פלט אלגוריתם 1 על $\varphi$. אז $\varphi$ ספיקה $\iff$ $\hat\varphi$ ספיקה.

הוכחה. נפריד לשני מקרים.

מקרה A: $\hat\varphi = \varphi$. זה קורה בדיוק כאשר $\varphi$ כבר 3CNF, ואז הטענה טריוויאלית.

מקרה B: $\hat\varphi \ne \varphi$. נסמן כמו באלגוריתם: $C=\ell_1\vee\dots\vee\ell_k$ היא הפסוקית הראשונה באורך $>3$, ו‑$C'=\ell_1\vee\ell_2\vee z$, $C''=\ell_3\vee\dots\vee\ell_k\vee\bar z$, כאשר $z$ חדש. שימו לב לעובדה שתשמש שוב ושוב: פסוקיות $\varphi$ ו‑$\hat\varphi$ זהות פרט לכך ש‑$C$ הוחלפה ב‑$C',C''$, ו‑$z$ אינו מופיע באף פסוקית אחרת.

כיוון ראשון: $\varphi$ ספיקה $\Rightarrow$ $\hat\varphi$ ספיקה.

תהא $v$ השמה המספקת את $\varphi$. מכיוון ש‑$v$ מספקת את $\varphi$ היא בפרט מספקת את $C$, ולכן קיים $1\le i\le k$ עם $v(\ell_i)=1$. נפריד לשני תת‑מקרים לפי מה שקורה בשני הליטרלים הראשונים.

מקרה B.1: $v(\ell_1)=0$ וגם $v(\ell_2)=0$. נגדיר השמה $\hat v$ עבור $\hat\varphi$: $\hat v(x)=\begin{cases} v(x) & x \ne z\\ 1 & x=z\end{cases}$

• כל פסוקית $D$ של $\hat\varphi$ שאינה $C'$ ואינה $C''$: $D$ היא גם פסוקית של $\varphi$, ולכן $v$ מספקת אותה. המשתנה $z$ אינו מופיע ב‑$D$, ולכן $\hat v$ ו‑$v$ נותנות את אותם ערכים לכל משתני $D$. מכאן ש‑$\hat v$ מספקת את $D$.
• $C'$: מכיוון ש‑$\hat v(z)=1$, הליטרל $z$ מספק את $C'$.
• $C''$: $v$ מספקת את $C$ ומתקיים $v(\ell_1)=v(\ell_2)=0$, ולכן קיים $3\le j\le k$ כך ש‑$v(\ell_j)=1$. הליטרל $\ell_j$ הוא מעל משתנה של $\varphi$, כלומר משתנה ששונה מ‑$z$, ולכן מהגדרת $\hat v$ מתקיים $\hat v(\ell_j)=v(\ell_j)=1$. לכן $\hat v$ מספקת את $C''$.

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

מקרה B.2: $v(\ell_1)=1$ או $v(\ell_2)=1$. נגדיר השמה $\hat v$ עבור $\hat\varphi$: $\hat v(x)=\begin{cases} v(x) & x \ne z\\ 0 & x=z\end{cases}$

הערה: בסיכום הכתוב, המקרה הזה מסוכם במילים "באופן דומה $\hat v$ מספקת את $\hat\varphi$". הנה הפירוט המלא.

• כל פסוקית $D$ שאינה $C',C''$: בדיוק כמו קודם — $D$ פסוקית של $\varphi$, $z$ אינו מופיע בה, $\hat v$ מסכימה עם $v$ על משתניה, ו‑$v$ מספקת אותה. לכן $\hat v$ מספקת את $D$.
• $C'$: הליטרלים $\ell_1,\ell_2$ הם מעל משתנים של $\varphi$, ולכן $\hat v(\ell_1)=v(\ell_1)$ ו‑$\hat v(\ell_2)=v(\ell_2)$. לפי ההנחה אחד מהם שווה $1$, ולכן $\hat v$ מספקת את $C'$.
• $C''$: מכיוון ש‑$\hat v(z)=0$ מתקיים $\hat v(\bar z)=1$, והליטרל $\bar z$ מספק את $C''$.

לכן $\hat v$ מספקת את $\hat\varphi$, ו‑$\hat\varphi$ ספיקה. הכיוון הזה הושלם.

כיוון שני (החצי העדין): $\hat\varphi$ ספיקה $\Rightarrow$ $\varphi$ ספיקה.

כאן צריך להראות שמשתנה העזר אינו יכול לרמות — שאי אפשר "לספק" את $\hat\varphi$ בזכות $z$ בלבד ולהשאיר את $\varphi$ בלתי מסופקת. שימו לב שכאן אין לנו חופש בבחירת ההשמה: היא נתונה לנו, ולעומת זאת בכיוון הראשון אנחנו אלה שבנינו אותה.

תהא $\hat v$ השמה המספקת את $\hat\varphi$. נגדיר השמה $v$ עבור $\varphi$ על ידי צמצום: לכל משתנה $x$ המופיע ב‑$\varphi$ נגדיר $v(x)=\hat v(x)$. (זה מוגדר היטב, כי כל משתני $\varphi$ הם משתני $\hat\varphi$.)

כל פסוקית $D$ של $\varphi$ שאינה $C$: $D$ היא גם פסוקית של $\hat\varphi$, ולכן $\hat v$ מספקת אותה; $v$ נותנת אותם ערכים כמו $\hat v$ לכל משתני $D$, ולכן $v$ מספקת את $D$.

נותר להראות ש‑$v$ מספקת את $C$. נפריד לשני מקרים לפי הערך ש‑$\hat v$ נתנה למשתנה החדש.

מקרה B.3: $\hat v(z)=1$. $\hat v$ מספקת את $\hat\varphi$ ובפרט את $C''=\ell_3\vee\dots\vee\ell_k\vee\bar z$. אבל $\hat v(\bar z)=0$, ולכן הליטרל $\bar z$ אינו זה שמספק את $C''$; לכן חייב להתקיים שקיים $3\le j\le k$ עם $\hat v(\ell_j)=1$. הליטרל $\ell_j$ הוא מעל משתנה של $\varphi$, ולכן $v(\ell_j)=\hat v(\ell_j)=1$. מכאן ש‑$v$ מספקת את $C$.

מקרה B.4: $\hat v(z)=0$. $\hat v$ מספקת בפרט את $C'=\ell_1\vee\ell_2\vee z$. אבל $\hat v(z)=0$, ולכן הליטרל $z$ אינו מספק את $C'$; לכן $\hat v(\ell_1)=1$ או $\hat v(\ell_2)=1$. שוב $\ell_1,\ell_2$ מעל משתנים של $\varphi$, ולכן $v(\ell_1)=1$ או $v(\ell_2)=1$, ומכאן ש‑$v$ מספקת את $C$.

בשני המקרים $v$ מספקת את כל פסוקיות $\varphi$, ולכן $\varphi$ ספיקה. $\blacksquare$

למה הוכחה כזו לא יכולה להיות "ברורה מאליה": ההוכחה בכיוון השני נשענת על שתי עובדות שאינן אוטומטיות — (א) שהמשתנה $z$ מופיע בדיוק בשתי פסוקיות, פעם חיובית ופעם שלילית; (ב) שהוא חדש. אם אחת מהן נופלת, הטענה נופלת. בסעיף הדוגמאות מובאות שתי דוגמאות נגדיות מפורשות בדיוק לשני הכשלים האלה.

למה לא בנייה נאיבית? שווה לראות מה נשבר:

• ניסיון א' — לחתוך את $C$ לבלוקים: $C=\ell_1\vee\dots\vee\ell_6$ מוחלפת ב‑$(\ell_1\vee\ell_2\vee\ell_3)\wedge(\ell_4\vee\ell_5\vee\ell_6)$. זה שגוי לחלוטין: הבנייה דורשת שכל בלוק יסופק, כלומר היא חזקה מדי — $C$ עם $\ell_1=1$ וכל השאר $0$ מסופקת, בעוד הנוסחה החדשה אינה מסופקת.
• ניסיון ב' — פשוט לזרוק ליטרלים: מחליפים את $C$ ב‑$(\ell_1\vee\ell_2\vee\ell_3)$. גם זה שגוי, מאותה סיבה בכיוון ההפוך — נוסחה ספיקה יכולה להיות ספיקה רק בזכות $\ell_5$.
• מה שחסר בשני הניסיונות הוא בדיוק אמצעי להעביר את המידע "כבר סיפקתי" מבלוק לבלוק. משתנה עזר חדש $z$ הוא בדיוק אמצעי כזה — ולכן הוא הכרחי, ולכן הבנייה יוצרת נוסחה שאינה שקולה ללוגית ל‑$\varphi$ אלא רק שקולת‑ספיקות.

משפט 6: $\mathrm{SAT} \le_p \mathrm{3SAT}$

טענה. קיימת רדוקציית זמן פולינומי מ‑$\mathrm{SAT}$ ל‑$\mathrm{3SAT}$. במילים: 3SAT היא לפחות קשה כמו SAT.

הוכחה. נתבונן באלגוריתם הבא. על קלט $\varphi$, נוסחה מצורת CNF:

1. כל עוד $\varphi$ אינה נוסחה מצורת 3CNF:
   • 1.1 הרץ את אלגוריתם 1 על $\varphi$ ונסמן את הפלט $\hat\varphi$ (בכל הפעלה נבחר משתנה עזר חדש, שלא הופיע באף שלב קודם).
   • 1.2 $\varphi \leftarrow \hat\varphi$.
2. החזר את $\varphi$.

בנוסף, אם הקלט אינו קידוד תקין של נוסחת CNF — נדחה אותו, כלומר נחזיר נוסחת 3CNF קבועה ובלתי‑ספיקה, למשל $(y)\wedge(\bar y)$. בדיקת התקינות והפלט הקבוע נעשים בזמן לינארי. (בהרצאה הנקודה הזו נאמרה כהנחה: "אני מניח שקיבלתי נוסחה בצורת CNF... אפשר לבדוק תקינות ולדחות" [00:17:52].)

עצירה. בכל איטרציה, פסוקית באורך $k>3$ מוחלפת בפסוקיות באורכים $3$ ו‑$k-1$; פסוקיות באורך $\le 3$ אינן משתנות לעולם. לכן הסכום $\sum_{C \in \varphi,\ |C|>3}(|C|-3)$ יורד בדיוק ב‑$1$ בכל איטרציה, והוא מספר טבעי אי‑שלילי — אז הלולאה עוצרת, ובפלט כל הפסוקיות באורך $\le 3$, כלומר הפלט הוא 3CNF.

נכונות. נסמן ב‑$\varphi_0=\varphi$ את הקלט, וב‑$\varphi_1,\dots,\varphi_m$ את הנוסחאות אחרי כל איטרציה, כאשר $\varphi_m$ הוא הפלט. לפי משפט 5, לכל $0\le t<m$ מתקיים "$\varphi_t$ ספיקה $\iff$ $\varphi_{t+1}$ ספיקה". באינדוקציה על $t$ מתקבל $\varphi \text{ satisfiable} \iff \varphi_m \text{ satisfiable}.$ מכיוון ש‑$\varphi_m$ היא 3CNF, זה בדיוק $\langle \varphi\rangle \in \mathrm{SAT} \iff \langle\varphi_m\rangle \in \mathrm{3SAT}.$

הערה על תנאי הרעננות בלולאה: משפט 5 דורש ש‑$z$ לא יופיע ב‑$\varphi$ הנוכחית, כלומר גם לא במשתני העזר שנוספו באיטרציות קודמות. לכן מקצים משתנה עזר חדש לכל איטרציה. הדבר גם מבטיח שהאינדוקציה למעלה חוקית: בכל צעד תנאי משפט 5 מתקיימים.

ניתוח זמן ריצה (במפורש). נסמן ב‑$L$ את מספר מופעי הליטרלים בנוסחת הקלט; ברור ש‑$L \le |\varphi|$.

1. מספר האיטרציות. כפי שראינו בהוכחת העצירה, מספר האיטרציות שווה בדיוק ל‑$\sum_{|C|>3}(|C|-3) \le L \le |\varphi|$, כלומר $O(|\varphi|)$. (בסיכום כתוב לצד זה בכחול: כל הפעלה מקטינה את הפסוקית הארוכה ב‑1 — זו בדיוק הסיבה.)
2. גידול אורך הנוסחה. בכל איטרציה פסוקית באורך $k$ מוחלפת בשתי פסוקיות באורכים $3$ ו‑$k-1$, כלומר מספר מופעי הליטרלים גדל ב‑$2$ בדיוק, ומספר הפסוקיות ב‑$1$. לכן אחרי כל האיטרציות $L_{\text{final}} \le L + 2\cdot(\text{number of iterations}) \le 3L = O(|\varphi|),$ כלומר הנוסחה אינה מתנפחת — היא נשארת לינארית באורך הקלט. בפרט לכל אורך הריצה כל נוסחת ביניים היא בגודל $O(|\varphi|)$.
3. מחיר איטרציה בודדת. סריקת הנוסחה הנוכחית כדי לאתר את הפסוקית הארוכה הראשונה, והעתקתה עם הפיצול, עולים $O(|\varphi_t|) = O(|\varphi|)$.
4. סך הכול. $O(|\varphi|) \cdot O(|\varphi|) = O(|\varphi|^2)$ — פולינומי. $\blacksquare$

הערה על דיוק החסם: בסיכום נכתב שאורך $\hat\varphi$ אינו עולה על $2|\varphi|$. ספירה מדויקת של מופעי ליטרלים נותנת $3L$ ולא $2L$ (הקלט $L$ ועוד $2$ לכל אחת מעד $L$ איטרציות). ההבדל אינו משנה דבר — שני החסמים לינאריים ולכן זמן הריצה $O(|\varphi|^2)$ בעינו. הערה נוספת ברמת הביטים: הרדוקציה מוסיפה עד $L$ משתנים חדשים, וקידוד אינדקס של משתנה חדש עשוי לדרוש $O(\log L)$ ביטים, כך שאורך הפלט בביטים הוא $O(|\varphi|\log|\varphi|)$. עדיין פולינומי, וזמן הריצה עדיין פולינומי — אך כדאי לדעת שהחסם הלינארי הוא בספירת סמלים, לא בהכרח בספירת ביטים.

מסקנה: $\mathrm{3SAT}$ היא NP‑שלמה

• $\mathrm{3SAT}\in\mathrm{NP}$ — מסקנת משפט 4.
• $\mathrm{3SAT}$ NP‑קשה — לפי משפט קוק–לוין $\mathrm{SAT}$ NP‑קשה, לפי משפט 6 מתקיים $\mathrm{SAT}\le_p \mathrm{3SAT}$, ולפי מסקנה 3 של משפט 2 (טרנזיטיביות) מתקבל שכל $A\in\mathrm{NP}$ מקיימת $A\le_p\mathrm{SAT}\le_p\mathrm{3SAT}$.

לכן $\mathrm{3SAT}$ NP‑שלמה. $\blacksquare$

למה בכלל טורחים? אחרי משפט קוק–לוין כבר יש לנו בעיה NP‑שלמה, אז מדוע להוסיף עוד אחת? כי 3SAT היא נקודת מוצא נוחה בהרבה לרדוקציות עתידיות: קלט של 3SAT הוא אוסף פסוקיות שכל אחת מהן מכילה לכל היותר 3 ליטרלים, מבנה נוקשה שקל להעתיק לגרף, לקבוצות או לאילוצים גיאומטריים. בשיעורים הבאים כמעט כל רדוקציה תתחיל מ‑3SAT ולא מ‑SAT. בהקלטה של שיעור 9 המרצה מציין שזו בדיוק הדרך של Karp: "הוא עשה את הרדוקציה מ‑SAT ל‑3SAT שהראינו, את הרדוקציה מ‑SAT ל‑IS, ואז מ‑IS ל‑CLIQUE" [01:20:52, תמלול 15].

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

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

הערה: הטענה הזו אינה בסיכום ואינה בהקלטה. היא נכללת כאן כי ההגדרה השנייה נפוצה בספרות, וכי היא משלימה את ניתוח המקרים לפסוקיות באורך 1 ו‑2 — מקרים שההגדרה של הקורס פשוט אינה זקוקה לטיפול בהם.

הוכחה. בהינתן נוסחת 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)$. נכונות: אם $v(\ell_1)=1$ או $v(\ell_2)=1$ — שתי הפסוקיות מסופקות בכל ערך של $y$. אם שניהם $0$ — אחת משתי הפסוקיות נכשלת, כי אחד מ‑$y,\bar y$ מקבל $0$. כלומר הצמד מסופק אם ורק אם $C$ מסופקת, בכל השמה ל‑$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(\ell_1)=1$ הכול מסופק. אם $v(\ell_1)=0$, אז לכל בחירה של $(y,y')$ אחת מארבע הפסוקיות מכילה את שני הליטרלים המשלימים ומקבלת $0$.

בשני המקרים המשתנים החדשים אינם מופיעים בשום מקום אחר, ולכן אפשר לצמצם/להרחיב השמות בדיוק כמו במשפט 5. גודל הפלט לכל היותר פי 4 מגודל הקלט, וזמן החישוב לינארי. $\blacksquare$

דוגמאות ותרגילים מהשיעור

דוגמה 1: מסלול מלא של נוסחה דרך הרדוקציה, בשני הכיוונים

ניקח את הדוגמה מעמוד 4 בסיכום: $\varphi = (x_1 \vee \bar x_2) \wedge (x_1 \vee x_3 \vee x_4 \vee \bar x_5 \vee \bar x_6).$

איטרציה 1. הפסוקית הראשונה באורך $>3$ היא $C=x_1\vee x_3\vee x_4\vee\bar x_5\vee \bar x_6$, כלומר $k=5$, $\ell_1=x_1$, $\ell_2=x_3$. עם משתנה חדש $z_1$: $C' = x_1\vee x_3\vee z_1, \qquad C''=x_4\vee \bar x_5\vee\bar x_6\vee \bar z_1 \quad (k-1=4 \text{ literals}),$ $\varphi_1 = (x_1\vee\bar x_2)\wedge(x_1\vee x_3\vee z_1)\wedge(x_4\vee\bar x_5\vee\bar x_6\vee\bar z_1).$

איטרציה 2. הפסוקית הארוכה היחידה היא $x_4\vee\bar x_5\vee\bar x_6\vee\bar z_1$ ($k=4$), עם $\ell_1=x_4,\ \ell_2=\bar x_5$. עם משתנה חדש $z_2$: $\varphi_2=(x_1\vee\bar x_2)\wedge(x_1\vee x_3\vee z_1)\wedge(x_4\vee\bar x_5\vee z_2)\wedge(\bar x_6\vee\bar z_1\vee\bar z_2).$ כל הפסוקיות באורך $\le 3$ — זהו הפלט. שימו לב לאימות המספרים: $L=2+5=7$ מופעי ליטרלים בקלט, שתי איטרציות (כי $5-3=2$), ובפלט $2+3+3+3=11 = 7+2\cdot 2$ מופעים. בדיוק כמו שניתוח הזמן חזה.

מסלול קדימה ($\varphi$ ספיקה $\Rightarrow$ $\varphi_2$ ספיקה). ניקח $v: \ x_1=1,\ x_2=1,\ x_3=0,\ x_4=0,\ x_5=1,\ x_6=1.$ $v$ מספקת את $\varphi$: הפסוקית הראשונה בזכות $x_1$, השנייה בזכות $x_1$.

• באיטרציה 1: $v(\ell_1)=v(x_1)=1$ — זהו מקרה B.2, ולכן $\hat v(z_1)=0$. בדיקה: $(x_1\vee x_3\vee z_1)=1$ בזכות $x_1$; $(x_4\vee\bar x_5\vee\bar x_6\vee\bar z_1)=1$ בזכות $\bar z_1$.
• באיטרציה 2, ביחס לנוסחה $\varphi_1$ ולהשמה שהתקבלה: $\ell_1=x_4=0$ ו‑$\ell_2=\bar x_5=0$ — זהו מקרה B.1, ולכן $z_2=1$. בדיקה: $(x_4\vee\bar x_5\vee z_2)=1$ בזכות $z_2$; $(\bar x_6\vee\bar z_1\vee\bar z_2) = 0\vee 1\vee 0=1$ בזכות $\bar z_1$.

ההשמה הסופית $\hat v: x_1{=}1,x_2{=}1,x_3{=}0,x_4{=}0,x_5{=}1,x_6{=}1,z_1{=}0,z_2{=}1$ מספקת את כל ארבע הפסוקיות של $\varphi_2$.

מסלול אחורה ($\varphi_2$ ספיקה $\Rightarrow$ $\varphi$ ספיקה). ניקח הפעם השמה "עוינת" ל‑$\varphi_2$ שמנסה להישען על משתני העזר: $u:\ x_1=0,\ x_2=0,\ x_3=0,\ x_4=0,\ x_5=0,\ x_6=0,\ z_1=1,\ z_2=0.$ בדיקה: $(x_1\vee\bar x_2)=1$; $(x_1\vee x_3\vee z_1)=1$ בזכות $z_1$; $(x_4\vee\bar x_5\vee z_2)=1$ בזכות $\bar x_5$; $(\bar x_6\vee\bar z_1\vee\bar z_2)=1$ בזכות $\bar x_6$. אכן $u$ מספקת את $\varphi_2$.

נצמצם: $v=u|_{x_1,\dots,x_6}$, כלומר כל ה‑$x$‑ים אפס. האם $v$ מספקת את $\varphi$? $(x_1\vee\bar x_2)=0\vee 1=1$; $(x_1\vee x_3\vee x_4\vee\bar x_5\vee\bar x_6)=0\vee0\vee0\vee1\vee1=1$. כן.

וזה בדיוק הטיעון של מקרה B.3 בפעולה: $u(z_1)=1$ אילץ את $\bar z_1$ להיות $0$, כך שהפסוקית $(x_4\vee\bar x_5\vee\bar x_6\vee\bar z_1)$ נאלצה להיות מסופקת על ידי ליטרל מקורי — ואכן $\bar x_5=1$. משתנה העזר "העביר את החוב הלאה" ולא הצליח לפרוע אותו בעצמו.

דוגמה 2: $C' \wedge C''$ אינה שקולה ל‑$C$

יהי $C=a\vee b\vee c\vee d$, ונפצל: $C'=a\vee b\vee z$, $C''=c\vee d\vee\bar z$.

• קחו $a=1$ ו‑$b=c=d=0$. אז $C$ מסופקת. אבל אם בנוסף $z=1$: $C'=1$ ואילו $C''=0\vee0\vee0=0$ — הצמד אינו מסופק.
• קחו $a=b=c=d=0$. אז $C$ אינה מסופקת, ואכן בשתי הבחירות של $z$ הצמד נכשל: $z=1$ מפיל את $C''$, $z=0$ מפיל את $C'$.

המסקנה: לא לכל $z$ מתקיים $C'\wedge C''$ כאשר $C$ מתקיימת — אלא קיים $z$ כזה. כל הוכחה שכותבת "$C \equiv C'\wedge C''$" שגויה; הניסוח הנכון הוא שקילות ספיקות, ולכן ההוכחה חייבת לעבור דרך בניית ההשמה בכל כיוון בנפרד.

תרגיל 1: מה נשבר אם משתמשים באותו $z$ פעמיים?

התרגיל. נניח שבמקום להקצות משתנה חדש בכל איטרציה, האלגוריתם משתמש שוב ושוב באותו $z$. תנו דוגמה נגדית.

פתרון. יהי $\varphi = (a\vee b\vee c\vee d)\wedge(e\vee f\vee g\vee h).$ עם אותו $z$ בשני הפיצולים מקבלים $\hat\varphi = (a\vee b\vee z)\wedge(c\vee d\vee\bar z)\wedge(e\vee f\vee z)\wedge(g\vee h\vee\bar z).$ קחו את ההשמה $a=1,\ g=1$ וכל השאר $0$. אז $\varphi$ מסופקת (הפסוקית הראשונה בזכות $a$, השנייה בזכות $g$). אבל ב‑$\hat\varphi$: