21The 7/8 Approximation Ratio for MAX-3ECNF, Self-Reducibility of SAT, and coNP

בקצרה

• הפתיחה אורזת את האלגוריתם הדטרמיניסטי מהשיעור הקודם כאלגוריתם קירוב: יחס $\alpha=\tfrac78$ במוסכמת המקסימיזציה של שיעור 13, $\mathrm{ALG}\ge \alpha\cdot\mathrm{OPT}$ עם $0<\alpha\le 1$. הצעד שאסור לדלג עליו הוא החסם $\mathrm{OPT}\le m$.
• האלגוריתם עצמו — שיטת התוחלות המותנות ל‑3ECNF — והוכחת נכונותו נלמדו ונכתבו בשיעור 20, ותוצאת הקיום $\ge\tfrac{7}{8}m$ שעליה הכול נשען הוכחה בשיעור 19. כאן הם משמשים כקופסה שחורה, בניסוח מדויק.
• מוכיחים שה‑SAT היא self-reducible: אלגוריתם פולינומי לבעיית ההכרעה גורר אלגוריתם פולינומי לבעיית החיפוש. זהו חימום דטרמיניסטי, אבל אותה בנייה בדיוק היא לב ההוכחה הבאה.
• המשפט המרכזי: אם $\mathrm{SAT}\in\mathrm{BPP}$ אז $\mathrm{NP}\subseteq\mathrm{RP}$ — כלומר טעות דו‑צדדית לכל בעיה ב‑$\mathrm{NP}$ גוררת טעות חד‑צדדית לכל בעיה ב‑$\mathrm{NP}$. ההוכחה משלבת את הרדוקציה העצמית עם אמפליפיקציה וחסם האיחוד.
• הטריק שגורם לטעות להיות חד‑צדדית: השלב האחרון של האלגוריתם הוא בדיקה דטרמיניסטית של ההשמה שנבנתה. "כן" נאמר רק כשההשמה מספקת בפועל.
• הפרקון האחרון מגדיר את $\mathrm{coNP}$ ומוכיח: $\mathrm{coP}=\mathrm{P}$, $\mathrm{P}\subseteq\mathrm{NP}\cap\mathrm{coNP}$, ש‑$\mathrm{NP}=\mathrm{coNP}$ שקול ל‑$\mathrm{NP}\subseteq\mathrm{coNP}$ וגם שקול ל‑$\mathrm{SAT}\in\mathrm{coNP}$, ושבעיה $A$ היא $\mathrm{coNP}$‑קשה אם ורק אם $\bar A$ היא $\mathrm{NP}$‑קשה.

רקע ותלויות

מבעיות אופטימיזציה ויחס קירוב (שיעור 13). בעיית אופטימיזציה של מקסימיזציה מתאימה לכל קלט $x$ אוסף פתרונות אפשריים ולכל פתרון ערך; $\mathrm{OPT}(x)$ הוא הערך המקסימלי. אלגוריתם $\mathrm{ALG}$ הוא קירוב ביחס $\alpha$ (עם $0<\alpha\le 1$) אם לכל קלט $x$ הוא מחזיר פתרון חוקי שערכו מקיים $\mathrm{ALG}(x)\;\ge\;\alpha\cdot \mathrm{OPT}(x).$ זו המוסכמת של בעיות מקסימום; בבעיות מינימום המוסכמת ההפוכה, $\mathrm{ALG}(x)\le\alpha\cdot\mathrm{OPT}(x)$ עם $\alpha\ge 1$ (כמו הקירוב 2 ל‑$\mathrm{VC}$ שם). בכל טענת קירוב כאן נדרשות שתי הוכחות נפרדות: שהפלט חוקי, ושהוא עומד בחסם מול $\mathrm{OPT}$.

חסם ה‑$\tfrac78$ (שיעור 19). תהא $\varphi$ נוסחה בצורת 3ECNF — כלומר בכל הסגר בדיוק שלושה ליטרלים מעל שלושה משתנים שונים — עם $m$ הסגרים. נדגום השמה $v$ במידה אחידה מתוך $2^n$ ההשמות, ונסמן ב‑$X$ את מספר ההסגרים המסופקים. לכל הסגר $C$, ההסתברות שהוא אינו מסופק היא $\left(\tfrac12\right)^3=\tfrac18$, כי שלושת הליטרלים הם מעל משתנים שונים ולכן ערכיהם בלתי תלויים, ויש בדיוק השמה אחת לשלושת המשתנים האלה שמפילה את ההסגר. מלינאריות התוחלת מעל ההסגרים, $\mathbb{E}[X]\;=\;\sum_{C\in\varphi}\Pr[C \text{ satisfied}]\;=\;m\cdot\tfrac78 .$ מכאן, בשיטה ההסתברותית, קיימת השמה המספקת לפחות $\tfrac78 m$ הסגרים.

למה דווקא 3ECNF ולא 3CNF. בקורס הזה 3CNF מוגדרת כ"לכל היותר שלושה ליטרלים בהסגר" (ראו שיעור 8, שם הרדוקציה $\mathrm{SAT}\le_p \mathrm{3SAT}$ מייצרת הסגרים כאלה). החישוב למעלה נשען על כך שבכל הסגר יש בדיוק שלושה ליטרלים מעל שלושה משתנים שונים: הסגר באורך 1 נכשל בהסתברות $\tfrac12$, ולכן נוסחה של הסגרי יחידה בלבד מקיימת $\mathbb{E}[X]=\tfrac12 m$ ולא $\tfrac78 m$; והסגר שבו אותו משתנה מופיע פעמיים ($x\vee x\vee y$) נכשל בהסתברות $\tfrac14$. לכן $\mathrm{MAX\text{-}3ECNF}$ ולא $\mathrm{MAX\text{-}3SAT}$.

הדרנדומיזציה (שיעור 20). שיטת התוחלות המותנות (שהופיעה לראשונה בשיעור 19 על $\mathrm{MAXCUT}$) הופכת את הקיום לבנייה: משתנה מקרי $X$ שתוחלתו ידועה, ורצף החלטות בינאריות; בכל צעד קובעים משתנה אחד לפי הענף שבו התוחלת המותנית אינה יורדת מתחת לסף, ובסוף התוחלת המותנית היא ערך קונקרטי. שיעור 20 מבצע את השיטה במלואה עבור 3ECNF ומוכיח את נכונותה; כאן מנוסחת התוצאה שלו כמשפט 1 ומשמשת כקופסה שחורה, וההוכחה החדשה שנוספת עליה היא רק אריזת התוצאה כיחס קירוב מול $\mathrm{OPT}$.

מחלקות אקראיות (שיעורים 16–17). נזכיר: $L\in\mathrm{BPP}$ אם קיימת מכונה אקראית פולינומית $M$ כך שלכל $x$, $\Pr[M(x)=[x\in L]]\ge\tfrac23$ — טעות דו‑צדדית. $L\in\mathrm{RP}$ אם קיימת מכונה אקראית פולינומית $M$ כך שאם $x\in L$ אז $\Pr[M \text{ accepts } x]\ge\tfrac12$, ואם $x\notin L$ אז $\Pr[M \text{ accepts } x]=0$ — טעות חד‑צדדית, רק false negatives. שתי המחלקות סגורות לרדוקציות זמן פולינומי. אמפליפיקציה: לכל פולינום $q$, כל שפה ב‑$\mathrm{BPP}$ מוכרעת בזמן פולינומי בהסתברות שגיאה $\le 1/q(|x|)$ (חזרות בלתי תלויות והכרעת רוב, עם חסם צ'רנוף).

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

הגדרות

הגדרה 1: MAX-3ECNF

הקלט: נוסחה $\varphi$ בצורת 3ECNF מעל המשתנים $x_1,\dots,x_n$, עם $m$ הסגרים. הפתרונות החוקיים: כל ההשמות המלאות $v:\{x_1,\dots,x_n\}\to\{0,1\}$. הערך: מספר ההסגרים של $\varphi$ שההשמה $v$ מספקת. המטרה: מקסימום. נסמן $\mathrm{OPT}(\varphi)=\max_v \#\{C\in\varphi: v \models C\}$.

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

דוגמה. $\varphi=(x_1\vee x_2\vee x_3)\wedge(\neg x_1\vee \neg x_2\vee \neg x_3)$: כאן $m=2$, $\mathrm{OPT}=2$ (למשל $v=(1,0,0)$).

דוגמה נגדית (מה איננו קלט חוקי). $(x_1\vee x_2)\wedge(x_1\vee\neg x_1\vee x_2)$ אינה 3ECNF: ההסגר הראשון באורך 2, ובשני מופיע $x_1$ פעמיים. שתי החריגות שוברות את חישוב ה‑$\tfrac18$.

הגדרה 2: השמה חלקית והשלמה

השמה חלקית $v$ היא פונקציה חלקית מקבוצת המשתנים ל‑$\{0,1\}$ — כלומר, ייתכן שאינה מוגדרת על חלק מהמשתנים. השלמה של $v$ היא השמה מלאה $\hat v$ המוגדרת על כל המשתנים, כך שבכל מקום שבו $v$ מוגדרת מתקיים $\hat v(x)=v(x)$; על המשתנים שבהם $v$ אינה מוגדרת אין ל‑$\hat v$ שום מחויבות.

אינטואיציה. האלגוריתמים בשיעור בונים את ההשמה משתנה‑משתנה. בכל רגע ביד יש השמה חלקית, והאינווריאנטה שנשמור עליה תמיד תהיה מהצורה "קיימת השלמה של $v$ בעלת תכונה טובה". כשההשמה נעשית מלאה, ההשלמה היחידה שלה היא היא עצמה — ולכן התכונה הטובה עוברת אליה. זה כל מנגנון ההוכחה בשני האלגוריתמים הבאים.

הגדרה 3: התוחלת המותנית של מספר ההסגרים המסופקים (מובאת משיעור 20 לצורך ציטוט)

יהי $\varphi$ קבוע עם $m$ הסגרים, ותהא $\rho$ השמה חלקית. נסמן $\mathbb{E}[X\mid \rho]\;=\;\mathbb{E}\big[\,\#\{C\in\varphi: v\models C\}\;\big|\; v \text{ extends } \rho\,\big],$ כאשר ההשמה $v$ נדגמת אחידה מבין כל ההשמות המלאות המרחיבות את $\rho$ — כלומר, כל משתנה שאינו בתחום של $\rho$ מקבל $0$ או $1$ בהסתברות $\tfrac12$ באופן בלתי תלוי.

אינטואיציה ואופן החישוב. למרות שהביטוי הזה מדבר על אקראיות, יש לו נוסחה סגורה שמחושבת דטרמיניסטית במעבר אחד על הנוסחה. עוברים הסגר‑הסגר; אם בהסגר יש ליטרל ש‑$\rho$ כבר קבעה ל‑TRUE, תרומתו $1$; אם $\rho$ הפילה את כל ליטרליו, תרומתו $0$; אחרת, אם נותרו בו $k\ge 1$ ליטרלים חופשיים (מעל משתנים שונים), תרומתו $1-2^{-k}$. סוכמים. אין כאן שום הטלת מטבע. זו נקודה שהמרצה עמד עליה ארוכות: כל השיעורים על אלגוריתמים אקראיים דיברו על אקראיות באופן דטרמיניסטי לגמרי — הניתוח על הנייר הוא חישוב, לא ניסוי.

מקרה קצה חשוב. אם $\rho$ היא השמה מלאה, אין משתנים חופשיים, המשתנה המקרי הוא קבוע, ולכן $\mathbb{E}[X\mid\rho]$ שווה בדיוק למספר ההסגרים שהשמה $\rho$ מספקת. זהו הצעד שסוגר את הוכחת הנכונות בשיעור 20.

הגדרה 4: גרסת ההכרעה מול גרסת החיפוש של SAT

גרסת ההכרעה ($\mathrm{SAT}$): הקלט הוא נוסחת CNF $\varphi$, והפלט הוא "כן" אם קיימת ל‑$\varphi$ השמה מספקת ו"לא" אחרת. גרסת החיפוש: הקלט הוא נוסחת CNF $\varphi$, והפלט הוא השמה מספקת ל‑$\varphi$ אם קיימת כזו, ו"אין השמה מספקת" אחרת.

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

הגדרה 5: coNP

$\mathrm{coNP}=\{\,\bar A \;\mid\; A\in\mathrm{NP}\,\}.$

אינטואיציה ואזהרה. $\mathrm{coNP}$ היא אוסף המשלימים של שפות ב‑$\mathrm{NP}$, ולא המשלים של האוסף $\mathrm{NP}$. שפה שאינה ב‑$\mathrm{NP}$ אינה בהכרח ב‑$\mathrm{coNP}$, ושפה ב‑$\mathrm{coNP}$ יכולה בהחלט להיות גם ב‑$\mathrm{NP}$ (כל שפה ב‑$\mathrm{P}$, למשל). זה בדיוק כמו $\mathrm{R}$ ו‑$\mathrm{coR}$ בחישוביות — שם $\mathrm{coR}=\mathrm{R}$, ולא "המשלים של $\mathrm{R}$".

מקור אי‑הסימטריה: ההגדרה של $\mathrm{NP}$ אינה סימטרית. עבור yes-instance נדרש קיום (קיים עד קצר, או קיימת ריצה מקבלת של מכונה לא‑דטרמיניסטית), ועבור no-instance נדרש לכל (כל עד נדחה). היפוך התשובה של מכונה לא‑דטרמיניסטית אינו מחליף בין "קיים" ל"לכל", ולכן הטריק שעובד ב‑$\mathrm{P}$ אינו עובד כאן.

מופע. $\overline{\mathrm{SAT}}$ — קבוצת נוסחאות ה‑CNF שאין להן השמה מספקת — היא ב‑$\mathrm{coNP}$ לפי ההגדרה, כי $\mathrm{SAT}\in\mathrm{NP}$. אי‑מופע. אין לנו הצדקה לטעון ש‑$\overline{\mathrm{SAT}}\in\mathrm{NP}$: אין עד קצר ידוע לאי‑ספיקות. השאלה אם $\mathrm{NP}=\mathrm{coNP}$ פתוחה.

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

משפט 1: יחס הקירוב 7/8 ל‑MAX-3ECNF

גבול בעלוּת: האלגוריתם שלהלן והוכחת נכונותו (האינווריאנטה, האינדוקציה, סיום המשתנה המנוון וחשבון זמן הריצה) שייכים לשיעור 20 ונכתבו שם במלואם. כאן הם מובאים בניסוח מדויק בלבד, כדי שאפשר יהיה לצטט אותם; מה שמוכח כאן במלואו הוא אריזת התוצאה כיחס קירוב — חוקיות הפלט והשוואה ל‑$\mathrm{OPT}$.

האלגוריתם $A$ (משיעור 20). קלט: נוסחה $\varphi$ בצורת 3ECNF. נסמן ב‑$x_1,\dots,x_n$ את משתני הנוסחה, וב‑$m$ את מספר ההסגרים. הערך $m$ נקבע פעם אחת בתחילת הריצה ואינו משתנה.

1. לכל $1\le i\le n$:
   1. אם $\mathbb{E}[X\mid v(x_i)=1]\ \ge\ \tfrac78 m$ — קבע $v(x_i)=1$ והצב $1$ במקום $x_i$ ב‑$\varphi$.
   2. אחרת — קבע $v(x_i)=0$ והצב $0$ במקום $x_i$ ב‑$\varphi$.
2. החזר את $v$.

(התוחלת בשלב 1 מחושבת ביחס להשמה החלקית שנבנתה עד כה, כלומר $\mathbb{E}[X\mid v(x_1),\dots,v(x_{i-1}),v(x_i)=1]$ בסימוני הגדרה 3; זו בדיוק התוחלת על הנוסחה הנוכחית לאחר ההצבות, בתוספת ההסגרים שכבר סופקו.)

מה הוכח בשיעור 20 (מצוטט כאן). האלגוריתם $A$ הוא דטרמיניסטי (אין בו ביט אקראי אחד — $\mathbb{E}[X\mid\cdot]$ הוא מספר שמחושב בנוסחה סגורה לפי הגדרה 3), רץ בזמן $O(|\varphi|^2)$, ולכל נוסחה $\varphi$ בצורת 3ECNF עם $m$ הסגרים הוא מחזיר השמה מלאה $v$ המקיימת $\#\{C\in\varphi:\ v\models C\}\ \ge\ \tfrac78 m .$ ההוכחה שם היא אינדוקציה על האינווריאנטה $\mathbb{E}[X\mid\rho_i]\ge\tfrac78 m$, המשלבת את משפט התוחלת השלמה עם טיעון "ממוצע של שניים ⟸ אחד מהם לפחות הממוצע", ומסתיימת בכך שכשההשמה מלאה המשתנה המקרי מנוון ולכן תוחלתו היא ערכו. ראו שיעור 20 לפרטים המלאים, ושיעור 19 לתנאי ההתחלה $\mathbb{E}[X]=\tfrac78 m$ שממנו האינדוקציה יוצאת.

המשפט (החלק החדש כאן). האלגוריתם $A$ הוא אלגוריתם קירוב ביחס $\alpha=\tfrac78$ ל‑$\mathrm{MAX\text{-}3ECNF}$ במוסכמת המקסימיזציה של שיעור 13: לכל נוסחה $\varphi$ בצורת 3ECNF הוא מחזיר פתרון חוקי המקיים $\mathrm{ALG}(\varphi)\ge\tfrac78\cdot\mathrm{OPT}(\varphi)$.

הוכחה — חוקיות הפלט. האלגוריתם קובע ערך לכל $x_i$, $1\le i\le n$, בדיוק פעם אחת. לכן הפלט הוא השמה מלאה על כל המשתנים, וכל השמה מלאה היא פתרון חוקי של $\mathrm{MAX\text{-}3ECNF}$ (הגדרה 1). אין כאן מה להוכיח מעבר לכך, אבל חשוב לומר זאת במפורש: בהוכחת יחס קירוב תמיד יש שני חלקים, וזה הראשון.

הוכחה — חסימת $\mathrm{OPT}$ מלמעלה. זהו הצעד המהותי, והוא זה שאסור להשאיר משתמע. הערבות של האלגוריתם היא מוחלטת — "לפחות $\tfrac78 m$ הסגרים" — ואילו יחס קירוב מוגדר תמיד יחסית ל‑$\mathrm{OPT}$, שערכו לא ידוע לנו. המעבר בין השניים דורש לחסום את $\mathrm{OPT}$ מלמעלה בגודל שהאלגוריתם שולט בו. כאן החסם מיידי: לנוסחה יש בסך הכול $m$ הסגרים, ולכן שום השמה — ובכללן ההשמה האופטימלית — אינה יכולה לספק יותר מ‑$m$ מהם: $\mathrm{OPT}(\varphi)\ \le\ m .$

הוכחה — יחס הקירוב. נשלב את שני החסמים: $\mathrm{ALG}(\varphi)\ \ge\ \tfrac78 m\ \ge\ \tfrac78\cdot \mathrm{OPT}(\varphi),$ כאשר אי‑השוויון הראשון הוא הערבות של שיעור 20 והשני הוא $\mathrm{OPT}\le m$ מוכפל ב‑$\tfrac78>0$. כלומר $\mathrm{ALG}\ge\alpha\cdot\mathrm{OPT}$ עם $\alpha=\tfrac78\in(0,1]$ — בדיוק מוסכמת המקסימיזציה של שיעור 13. $\blacksquare$

שתי הערות על היחס.

1. הערבות $\mathrm{ALG}\ge\tfrac78 m$ חזקה מיחס הקירוב $\tfrac78$: כל אימת ש‑$\mathrm{OPT}<m$ (כלומר, כשהנוסחה אינה ספיקה) היחס בפועל טוב מ‑$\tfrac78$. ראו דוגמה 2, שבה $\mathrm{OPT}=7$, $m=8$, והיחס בפועל הוא $1$.
2. הכיוון של אי‑השוויון תלוי במוסכמה. במוסכמת המינימיזציה של שיעור 13 היינו כותבים $\mathrm{ALG}\le\alpha\cdot\mathrm{OPT}$ עם $\alpha\ge1$; לכתוב כאן $\alpha=\tfrac87$ יהיה שגוי במוסכמה שנקבעה בקורס. תמיד לציין את המוסכמה במפורש.

איפה נגמרת הבעלוּת של שיעור 20 ומתחילה זו של השיעור הזה. כל מה שקדם לחסם $\mathrm{OPT}\le m$ — האלגוריתם, האינווריאנטה, האינדוקציה, וההסבר מדוע תכונת ה‑3ECNF נחוצה אך ורק לתנאי ההתחלה — נלמד בהקלטה לפני [00:27:36] ונכתב בשיעור 20. החומר של השיעור הזה מתחיל ב‑[00:27:36], עם הטענה המרכזית על $\mathrm{BPP}$ ו‑$\mathrm{RP}$ (משפט 4).

משפט 2: SAT היא self-reducible

המשפט. אם קיים אלגוריתם זמן ריצה פולינומי עבור $\mathrm{SAT}$ (גרסת ההכרעה), אז קיים אלגוריתם זמן ריצה פולינומי עבור גרסת החיפוש של $\mathrm{SAT}$.

הערה על השם. זו אינה רדוקציית מיפוי: רדוקציות מיפוי הוגדרו בין בעיות הכרעה, וגרסת החיפוש אינה בעיית הכרעה. במובן של קורס אלגוריתמים זו בהחלט רדוקציה (שימוש באלגוריתם אחד כתת‑שגרה בתוך אחר), אך לא רדוקציה במובן של חישוביות/סיבוכיות. התכונה נקראת self-reducibility, ולא כל בעיה $\mathrm{NP}$‑שלמה ידועה ככזו — עבור חלק מהן זו שאלה פתוחה. זו אחת הדוגמאות לכך שבעיות $\mathrm{NP}$‑שלמות אינן נראות אותו הדבר ברזולוציה עדינה יותר מ‑$\mathrm{NP}$‑קושי; הבדל אחר הוא קירוביות — ל‑$\mathrm{VC}$ יש קירוב 2 (שיעור 13), ואילו ל‑$\mathrm{TSP}$ הכללי קירוב כלשהו כבר גורר $\mathrm{P}=\mathrm{NP}$ (שם).

הוכחה. נניח שקיים אלגוריתם $M$ המכריע את $\mathrm{SAT}$ בזמן פולינומי. נתבונן באלגוריתם $\hat M$ הבא:

קלט: נוסחה $\varphi$ בצורת CNF. נסמן $x_1,\dots,x_n$ את משתני הנוסחה.

1. אם $M$ דוחה את $\varphi$ — החזר "אין השמה מספקת".
2. לכל $1\le i\le n$:
   1. אם $M$ מקבלת את $\varphi\wedge x_i$ — קבע $v(x_i)=1$ והצב $\varphi \leftarrow \varphi\wedge x_i$.
   2. אחרת — קבע $v(x_i)=0$ והצב $\varphi \leftarrow \varphi\wedge \neg x_i$.
3. החזר את $v$.

החלטת התכנון החשובה. במשפט 1 קבענו משתנה על ידי הצבה, וכך המשתנה נעלם מהנוסחה. כאן, במקום להציב, אנחנו מוסיפים הסגר יחידה $(x_i)$ או $(\neg x_i)$. האפקט זהה — כל השמה מספקת של הנוסחה החדשה חייבת לתת ל‑$x_i$ את הערך שקבענו — אבל מספר המשתנים ואורך הנוסחה נשמרים בערך. במשפט 2 עצמו אין לכך צורך; הסיבה תתגלה במשפט 4, שם הסתברות השגיאה תלויה ב‑$n$ ולכן חשוב ש‑$n$ לא יקטן. (בנוסף, דידקטית זו דרך שנייה ושימושית לקבע ערך של משתנה.) הנוסחה שנשארת היא עדיין נוסחת CNF תקינה.

ניתוח זמן ריצה. קיים $c>0$ כך שלכל נוסחה $\psi$ מתקיים $\mathrm{time}_M(\psi)\le O(|\psi|^{c})$. האלגוריתם $\hat M$ מריץ את $M$ לכל היותר $n+1\le|\varphi|+1$ פעמים. לגבי אורך הקלטים: בכל איטרציה מתווסף הסגר יחידה בודד, ומשתנה זה כבר הופיע ב‑$\varphi$; לכן לאחר $n$ איטרציות האורך גדל לכל היותר פי שניים, $|\psi|\le 2|\varphi|$. מכאן $\mathrm{time}_{\hat M}(\varphi)\ \le\ (|\varphi|+1)\cdot O\big((2|\varphi|)^{c}\big)\ =\ O\big(|\varphi|^{\,c+1}\big),$ פולינומי באורך הקלט.

ניתוח סמנטי. תהא $\varphi$ נוסחת CNF.

אם $\varphi\notin\mathrm{SAT}$: $M$ מכריעה נכון, לכן היא דוחה בשלב 1 ו‑$\hat M$ מחזירה "אין השמה מספקת" — נכון.

אם $\varphi\in\mathrm{SAT}$: נסמן ב‑$\varphi_i$ את הנוסחה שבידי האלגוריתם בסוף איטרציה $i$ (ו‑$\varphi_0=\varphi$), וב‑$v_i$ את ההשמה החלקית שנבנתה עד אז. נוכיח באינדוקציה על $i$ את האינווריאנטה:

$\varphi_i\in\mathrm{SAT}$, כלומר קיימת השמה מספקת של $\varphi$ המשלימה את $v_i$.

(שתי הניסוחים שקולים כאן: $\varphi_i=\varphi\wedge\bigwedge_{j\le i}(\text{literal for } v_i(x_j))$, ולכן השמה מספקת את $\varphi_i$ אם ורק אם היא מספקת את $\varphi$ ומסכימה עם $v_i$.)

בסיס $i=0$: $\varphi_0=\varphi\in\mathrm{SAT}$ לפי ההנחה, ו‑$v_0$ ריקה.

צעד: נניח $\varphi_{i-1}\in\mathrm{SAT}$. — אם $M$ מקבלת את $\varphi_{i-1}\wedge x_i$: מכיוון ש‑$M$ מכריעה את $\mathrm{SAT}$ נכון, $\varphi_i=\varphi_{i-1}\wedge x_i$ אכן ספיקה. — אם $M$ דוחה את $\varphi_{i-1}\wedge x_i$: אז $\varphi_{i-1}\wedge x_i$ אינה ספיקה, כלומר אין השמה המספקת את $\varphi_{i-1}$ ונותנת ל‑$x_i$ את הערך $1$. אבל $\varphi_{i-1}$ כן ספיקה לפי הנחת האינדוקציה, ולכל השמה יש ערך יחיד עבור $x_i$; לכן כל השמה מספקת של $\varphi_{i-1}$ נותנת ל‑$x_i$ את הערך $0$, ובפרט קיימת כזו. מכאן $\varphi_i=\varphi_{i-1}\wedge\neg x_i$ ספיקה.

הערה: בהרצאה ובסיכום הצעד הזה נאמר בקיצור — "באינדוקציה"; הפירוט למעלה הוא מה שהאינדוקציה עומדת עליו. הנקודה היחידה שאינה אוטומטית היא שדחייה של הענף $x_i=1$ בשילוב עם ספיקות $\varphi_{i-1}$ מכריחה את קיומה של השמה מספקת עם $x_i=0$.

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

משפט 3: $\mathrm{NP}\subseteq\mathrm{BPP}$ אם ורק אם $\mathrm{SAT}\in\mathrm{BPP}$ (וכנ"ל עבור $\mathrm{RP}$)

המשפט. $\mathrm{NP}\subseteq\mathrm{BPP}$ אם ורק אם $\mathrm{SAT}\in\mathrm{BPP}$.

הוכחה. ($\Rightarrow$) $\mathrm{SAT}\in\mathrm{NP}$, ולכן מהכלה $\mathrm{SAT}\in\mathrm{BPP}$. זהו טיעון תורת‑קבוצות בלבד — ובכל זאת יש לכתוב אותו; דילוג על מה שנראה מובן מאליו הוא מקור נפוץ לטעויות.

($\Leftarrow$) נניח $\mathrm{SAT}\in\mathrm{BPP}$, ותהא $L\in\mathrm{NP}$. מכיוון ש‑$\mathrm{SAT}$ היא $\mathrm{NP}$‑קשה, קיימת רדוקציה $L\le_p \mathrm{SAT}$. מכיוון ש‑$\mathrm{BPP}$ סגורה לרדוקציות זמן פולינומי, נובע $L\in\mathrm{BPP}$. לכן $\mathrm{NP}\subseteq\mathrm{BPP}$. $\blacksquare$

איזו תכונה שימשה בכל כיוון. לכיוון ($\Leftarrow$) נדרשה רק $\mathrm{NP}$‑קושי של $\mathrm{SAT}$ (שיש רדוקציה אליה מכל בעיה ב‑$\mathrm{NP}$) וסגירות המחלקה לרדוקציות. לכיוון ($\Rightarrow$) נדרשה דווקא השייכות $\mathrm{SAT}\in\mathrm{NP}$. שני התנאים יחד הם בדיוק $\mathrm{NP}$‑שלמות. אותו טיעון בדיוק תקף עם $\mathrm{RP}$ במקום $\mathrm{BPP}$, כי גם $\mathrm{RP}$ סגורה לרדוקציות זמן פולינומי.

משפט 4: אם $\mathrm{SAT}\in\mathrm{BPP}$ אז $\mathrm{NP}\subseteq\mathrm{RP}$

מה המשפט אומר. זוהי טענת הכלה, ולכן היא מתחילה ב"לכל": אם לכל בעיה ב‑$\mathrm{NP}$ יש אלגוריתם אקראי פולינומי עם טעות דו‑צדדית, אז לכל בעיה ב‑$\mathrm{NP}$ יש אלגוריתם אקראי פולינומי עם טעות חד‑צדדית. ההבדל בין $\mathrm{BPP}$ ל‑$\mathrm{RP}$ אינו הקבועים $\tfrac23$ ו‑$\tfrac12$ (ראינו באמפליפיקציה שהם ניתנים לשינוי כמעט כרצוננו) אלא צדדיות הטעות: ב‑$\mathrm{RP}$ אין false positives כלל.

הערת ניסוח. ניסחנו את התנאי כ‑$\mathrm{SAT}\in\mathrm{BPP}$ (החלש ביותר) ואת המסקנה כ‑$\mathrm{NP}\subseteq\mathrm{RP}$ (החזקה ביותר), למרות שלפי משפט 3 שתי הצורות שקולות. זה עניין של נראות: תמיד עדיף לנסח משפט עם הנחה חלשה ככל האפשר ומסקנה חזקה ככל האפשר.

הוכחה. נניח $\mathrm{SAT}\in\mathrm{BPP}$. נעבור ממכונה אקראית למכונה אקראית — אין סיבה לעבור דרך מכונה דטרמיניסטית, כי היעד $\mathrm{RP}$ הוא ממילא אקראי.

שלב א' — אמפליפיקציה. מהנחת $\mathrm{SAT}\in\mathrm{BPP}$ ומשפט האמפליפיקציה (שיעור 17) קיימת מכונה אקראית $M$ הרצה בזמן פולינומי כך שלכל נוסחת CNF $\psi$: