20Randomized Algorithms for Satisfiability: Markov's Inequality, Amplification and Derandomization

בקצרה

• בשיעור הקודם הראינו שהשמה אקראית אחידה מספקת בתוחלת $\tfrac78$ מהפסוקיות של נוסחת $\mathrm{3ECNF}$. תוחלת היא מדד חלש: היא אינה אומרת דבר על ההסתברות שריצה בודדת באמת תשיג את המספר הזה.
• אי־שוויון מרקוב הוא הגשר: הוא מתרגם ידיעה על תוחלת לחסם על הסתברות. הוא חד־כיווני — חוסם מלמעלה את ההסתברות שמשתנה אי־שלילי גדול, ולכן מפעילים אותו על $Y=m-X$ (מספר הפסוקיות הלא מסופקות) ולא על $X$ עצמו.
• התוצאה: לכל נוסחת $\mathrm{3ECNF}$ קבועה, ההסתברות (מעל מטבעות האלגוריתם) שריצה בודדת תספק לפחות $\tfrac{7m}{8}$ פסוקיות היא לפחות $\Theta(1/m)$ — הסתברות קטנה, אבל הסתברות אמיתית ולא רק תוחלת.
• מכיוון שהטעות כאן חד־צדדית (לוקחים את המקסימום מבין הריצות), הגברה פשוטה בעלות $t=\Theta(m)$ חזרות מביאה את הצלחה ל־$99\%$, ובעלות $t=\Theta(m\log m)$ אף ל־$1-1/m$.
• לבסוף מסלקים את האקראיות לגמרי: שיטת התוחלות המותנות בונה השמה משתנה־אחר־משתנה, שומרת על השמורה $\mathbb{E}[X\mid \rho]\ge \tfrac{7m}{8}$ כאשר $\rho$ היא ההשמה החלקית שנקבעה עד כה, ומחזירה בוודאות השמה שמספקת לפחות $\tfrac{7m}{8}$ פסוקיות בזמן $O(|\varphi|^2)$.
• הדרישה לבדיוק שלושה ליטרלים מעל שלושה משתנים שונים דרושה רק לתנאי ההתחלה של האינדוקציה. לאחר הצבה ראשונה הנוסחה כבר אינה $\mathrm{3ECNF}$ — וזה בסדר, כי מכאן והלאה החסם $\tfrac{7m}{8}$ עובר בירושה מהאיטרציה הקודמת ולא מחושב מחדש.

רקע ותלויות

מודל האקראיות ומוסכמת ההסתברות

מכונות ומחלקות אקראיות ($\mathrm{RP}$, $\mathrm{coRP}$, $\mathrm{BPP}$) הוגדרו בשיעור 16, והגברת הסתברות הצלחה נדונה שם ובשיעור 17. כאן איננו זקוקים למחלקות עצמן — רק לתמונת המכונה: אלגוריתם אקראי מקבל קלט קבוע ובנוסף אליו מחרוזת ביטים אקראיים ("מטבעות").

מוסכמה שתלווה את כל הקובץ. כל הסתברות וכל תוחלת שנכתוב הן מעל מטבעות האלגוריתם בלבד, עבור נוסחה $\varphi$ קבועה שנתונה כקלט. אין כאן שום התפלגות על נוסחאות. בהרצאה זה נאמר במפורש ברגע שהוצג הסימון: "עד פה שום דבר אקראי — קיבלתי נוסחה ואני מסמן את מספר הפסוקיות שלה" [00:11:24].

הצורה $\mathrm{3ECNF}$ ומדוע היא לא $\mathrm{3CNF}$

בשיעור 8 (הרדוקציה $\mathrm{SAT}\le_p \mathrm{3SAT}$) הוגדרה נוסחת $\mathrm{3CNF}$ כקוניונקציה של פסוקיות שבכל אחת מהן לכל היותר שלושה ליטרלים. ההגדרה הגמישה הזו נוחה לרדוקציות, אך היא הורסת את החישוב שאנחנו עומדים לעשות. לכן עובדים כאן עם צורה קשיחה יותר, שהסיכום מסמן $\mathrm{3ECNF}$ (בהרצאה: "3 exact CNF"): בכל פסוקית בדיוק שלושה ליטרלים, מעל שלושה משתנים שונים [00:13:40].

התוצאה משיעור 19, במלואה

זו התוצאה שכל השיעור הזה נשען עליה, ולכן היא מובאת כאן במלואה ולא בהפניה בלבד (ההוכחה עצמה שייכת לשיעור 19; ראו שם, וכן את השיטה ההסתברותית ל־$\mathrm{MAXCUT}$ בשיעור 18).

האלגוריתם האקראי הבסיסי. בהינתן $\varphi$ בצורת $\mathrm{3ECNF}$ מעל $x_1,\dots,x_n$: לכל משתנה, באופן אחיד ובלתי תלוי באחרים, קבע את ערכו ל־$1$ בהסתברות $\tfrac12$ ול־$0$ בהסתברות $\tfrac12$. החזר את ההשמה $v$ שהתקבלה.

התוצאה. אם $m$ הוא מספר הפסוקיות ב־$\varphi$ ו־$X$ הוא מספר הפסוקיות ש־$v$ מספקת, אז $\mathbb{E}[X]=\frac{7m}{8}.$

ההוכחה חוזרת כאן במלואה כמשפט 1, גם מפני שהיא נדרשת שוב מילולית בחלק הדה־רנדומיזציה.

כלי ההגברה של טעות חד־צדדית

בשיעור 18, בניתוח אלגוריתם החתך המינימלי, ראינו את התבנית: אם ריצה בודדת מצליחה בהסתברות $p$ והטעות חד־צדדית (כלומר החזרת ה"טובה ביותר" מבין הריצות אינה יכולה להזיק), אז $t$ ריצות בלתי תלויות נכשלות כולן בהסתברות $\le (1-p)^t$. המרצה הדגיש שזו בדיוק אותה תבנית: "החזרתיות הזו — חשוב שתראו אותה, זה תמיד אותו פרינציפ" [00:57:32].

הגדרות

הגדרה 1: נוסחת $\mathrm{3ECNF}$

נוסחה $\varphi$ היא בצורת $\mathrm{3ECNF}$ אם $\varphi=C_1\wedge C_2\wedge\dots\wedge C_m$, וכל פסוקית היא דיסיונקציה $C_i=(\ell_{i,1}\vee \ell_{i,2}\vee \ell_{i,3})$ של בדיוק שלושה ליטרלים, כאשר שלושת הליטרלים הם מעל שלושה משתנים שונים.

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

דוגמה. $(\bar x_1\vee x_2\vee \bar x_3)\wedge(x_1\vee \bar x_4\vee x_3)\wedge(\bar x_1\vee \bar x_2\vee x_3)$ — שלוש פסוקיות, כל אחת בדיוק שלושה ליטרלים מעל שלושה משתנים שונים.

אי־דוגמה 1 (הגבול החשוב). $(x_1\vee x_2)\wedge(x_3)$ היא $\mathrm{3CNF}$ תקינה לפי הגדרת שיעור 8, אך אינה $\mathrm{3ECNF}$. הפסוקית $(x_3)$ אינה מסופקת בהסתברות $\tfrac12$ ולא $\tfrac18$ — וזה בדיוק מה שהורס את החסם.

אי־דוגמה 2. $(x_1\vee x_1\vee x_2)$ — שלושה ליטרלים, אך שני משתנים בלבד. כאן ההסתברות שהפסוקית אינה מסופקת היא $\Pr[x_1=0\wedge x_2=0]=\tfrac14$ ולא $\tfrac18$.

הגדרה 2: המשתנים המקריים $X$ ו־$Y$

תהי $\varphi$ נוסחת $\mathrm{3ECNF}$ קבועה עם $m$ פסוקיות, ותהי $v$ ההשמה שדוגם האלגוריתם האקראי הבסיסי. נגדיר: $X$ הוא מספר הפסוקיות של $\varphi$ שההשמה $v$ מספקת, ו־$Y=m-X$.

אינטואיציה. $X$ הוא הרווח ו־$Y$ הוא ההפסד. שניהם פונקציות של המטבעות בלבד (כי $\varphi$ קבועה), שניהם מקבלים ערכים שלמים בין $0$ ל־$m$, ובפרט שניהם אי־שליליים. שתי התכונות האלה — אי־שליליות ושלמוּת — הן בדיוק שתי התכונות שנצטרך בהמשך, ולא במקרה.

מופע. עבור $\varphi$ מהדוגמה שבהגדרה 1 ו־$v=(x_1,x_2,x_3,x_4)=(1,0,1,0)$ מתקבל $X=2$ (הפסוקית הראשונה מופרת) ו־$Y=1$.

הגדרה 3: בעיית האופטימיזציה שברקע

בהינתן נוסחת $\mathrm{3ECNF}$, המטרה היא למצוא השמה המספקת כמה שיותר פסוקיות. בספרות הבעיה נקראת $\mathrm{MAX\text{-}E3SAT}$; בהרצאה היא לא זכתה לשם, ודובר עליה ישירות כ"לספק כמה שיותר פסוקיות". שימו לב שזו אינה בעיית הכרעה: איננו שואלים אם $\varphi$ ספיקה, אלא כמה מפסוקיותיה ניתן לספק בו־זמנית. בפרט התוצאה שלנו תקפה גם לנוסחאות לא ספיקות.

הגדרה 4: השמה חלקית והנוסחה השיורית

תהי $\rho$ השמה חלקית שקובעת ערכים לתת־קבוצה של המשתנים. הנוסחה השיורית $\varphi|_\rho$ מתקבלת מ־$\varphi$ על ידי הצבת הערכים והפשטה: ליטרל שקיבל $1$ הופך את פסוקיתו לאמת, וליטרל שקיבל $0$ נמחק מהפסוקית.

אינטואיציה והערה קריטית. לאחר הצבה אחת בלבד הנוסחה כבר אינה $\mathrm{3ECNF}$ — יש בה פסוקיות באורך $2$ ופסוקיות שהן קבוע האמת. המרצה חזר לנקודה הזו פעמיים, כי היא נראית כמו קריסה של כל הבנייה, והיא לא [01:26:10] ו־[הקלטה 26, 00:23:17].

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

משפט 1: התוחלת של מספר הפסוקיות המסופקות (תזכורת משיעור 19)

תוצאה זו הוכחה בשיעור 19 והיא בבעלותו; היא מובאת כאן במלואה משום ששלוש התוצאות המרכזיות של השיעור הזה (משפט 4, משפט 5 ובסיס האינדוקציה של משפט 7) נשענות עליה ישירות, ומשום שאותו חישוב־פסוקית עצמו חוזר ומשמש בשלב א של משפט 7.

טענה. תהי $\varphi$ נוסחת $\mathrm{3ECNF}$ קבועה עם $m$ פסוקיות. אז, מעל מטבעות האלגוריתם האקראי הבסיסי, $\mathbb{E}[X]=\frac{7m}{8}.$

הוכחה. לכל $1\le i\le m$ נגדיר משתנה מציין (אינדיקטור) שערכו $X_i=1$ אם הפסוקית $C_i$ מסופקת על ידי $v$, ו־$X_i=0$ אחרת, ואז $X=\sum_{i=1}^m X_i$ (סכימת אינדיקטורים היא בדיוק ספירה).

חישוב לפסוקית בודדת. תהי $C_i=(\ell_{i,1}\vee\ell_{i,2}\vee\ell_{i,3})$. פסוקית זו אינה מסופקת אם ורק אם שלושת הליטרלים מקבלים $0$. ליטרל בודד $\ell$ מעל משתנה $x$ מקבל $0$ בהסתברות $\tfrac12$ בדיוק: אם $\ell=x$ זה קורה כאשר $v(x)=0$, ואם $\ell=\bar x$ זה קורה כאשר $v(x)=1$ — בשני המקרים הסתברות $\tfrac12$, כי $v(x)$ אחיד. כאן נכנסת לפעולה הדרישה ששלושת הליטרלים הם מעל שלושה משתנים שונים: שלושת המאורעות "$\ell_{i,j}=0$" נקבעים על ידי שלושה משתנים שונים, שהאלגוריתם הגריל בלתי תלוי זה בזה, ולכן הם בלתי תלויים ומותר לכפול. לכן ההסתברות ש־$C_i$ אינה מסופקת היא $\left(\tfrac12\right)^3=\frac18 .$ כלומר: מבין $8$ תבניות האמת האפשריות של שלושת המשתנים, בדיוק אחת מפילה את הפסוקית — זו שמאפסת את כל שלושת הליטרלים. לכן $\mathbb{E}[X_i]=\Pr[X_i=1]=1-\frac18=\frac78 .$

סכימה. מליניאריות התוחלת, $\mathbb{E}[X]=\mathbb{E}\!\left[\sum_{i=1}^m X_i\right]=\sum_{i=1}^m \mathbb{E}[X_i]=m\cdot\frac78=\frac{7m}{8}. \qquad\blacksquare$

הערה: ליניאריות התוחלת אינה דורשת אי־תלות בין ה־$X_i$. וזה חיוני: פסוקיות שונות חולקות משתנים, ולכן ה־$X_i$ תלויים זה בזה מאוד. המרצה הדגיש שזה בדיוק ה"טרייד־אוף" של התוחלת — "התוחלת מאפשרת לי את הליניאריות, אבל היא גם מדד מאוד חלש" [00:02:07]. אי־התלות שכן שימשה אותנו היא רק בתוך פסוקית בודדת, בין שלושת הליטרלים שלה.

מסקנה 1א: הטענה הקיומית (השיטה ההסתברותית)

טענה (בבעלות שיעור 19 — ראו שם להוכחה המלאה בהקשר השיטה ההסתברותית). לכל נוסחת $\mathrm{3ECNF}$ עם $m$ פסוקיות קיימת השמה $v^{*}$ המספקת לפחות $\tfrac{7m}{8}$ פסוקיות; מכיוון שמספר פסוקיות הוא שלם, קיימת השמה המספקת לפחות $\lceil 7m/8\rceil$ פסוקיות.

שרטוט הטיעון, כי הוא נדרש להבנת ההמשך. ההשמה נדגמת אחידה מבין כל $2^n$ ההשמות, ולכן $\mathbb{E}[X]$ הוא בדיוק הממוצע של $X$ על פני כל ההשמות: $\frac{7m}{8}=\mathbb{E}[X]=\frac{1}{2^n}\sum_{v\in\{0,1\}^n} X(v).$ אילו לכל השמה $v$ היה מתקיים $X(v)<\tfrac{7m}{8}$, היה הסכום קטן ממש מ־$2^n\cdot\tfrac{7m}{8}$ והממוצע קטן ממש מ־$\tfrac{7m}{8}$ — בסתירה לשוויון לעיל. לכן קיימת $v^{*}$ עם $X(v^{*})\ge \tfrac{7m}{8}$. $\blacksquare$

אזהרה מרכזית, וזו נקודת הפתיחה של כל השיעור. "קיימת השמה טובה" ו"האלגוריתם מוצא השמה טובה בסבירות סבירה" הם שני דברים שונים לחלוטין. מסקנה 1א היא טענת קיום בלבד: היא אינה נותנת אלגוריתם ואינה מבטיחה שדגימה אחת תפגע. באופן עקרוני ייתכן היה שהתוחלת $\tfrac{7m}{8}$ מושגת על ידי מיעוט זעיר של השמות מצוינות ורוב עצום של השמות בינוניות. המרצה ניסח את זה כך: "אולי לקבל השמה שמספקת שבע שמיניות — יש לי הסתברות מאוד קטנה. איך בדיוק התוחלת מתפרקת אני לא יודע, כי לא חישבתי את ההתפלגות, ואני גם לא רוצה — יש שם המון תלויות" [00:03:43]. כל מה שנעשה מכאן הוא לסגור את הפער הזה בלי לחשב את ההתפלגות.

משפט 2: אי־שוויון מרקוב

טענה. יהי $X$ משתנה מקרי אי־שלילי בעל תוחלת סופית. אז לכל $a>0$: $\Pr\big(X\ge a\,\mathbb{E}[X]\big)\le \frac1a .$

הוכחה. נניח $\mathbb{E}[X]>0$ (אחרת, אם $\mathbb{E}[X]=0$ ו־$X$ אי־שלילי, אז $X=0$ כמעט תמיד והטענה טריוויאלית). נסמן $t=a\,\mathbb{E}[X]>0$ ונגדיר את האינדיקטור $I=\mathbf{1}[X\ge t]$. מכיוון ש־$X\ge 0$, מתקיים לכל ערך אפשרי של $X$ אי־השוויון הנקודתי $X\ \ge\ t\cdot I .$ אכן: אם $X\ge t$ אז $I=1$ והאגף הימני הוא $t\le X$; ואם $X<t$ אז $I=0$ והאגף הימני הוא $0\le X$ מאי־שליליות. כעת ניקח תוחלת משני האגפים (מונוטוניות התוחלת): $\mathbb{E}[X]\ \ge\ t\cdot\mathbb{E}[I]=t\cdot\Pr(X\ge t)=a\,\mathbb{E}[X]\cdot \Pr\big(X\ge a\mathbb{E}[X]\big),$ וחלוקה ב־$a\,\mathbb{E}[X]>0$ נותנת את הטענה. $\blacksquare$

הערה: בהרצאה אי־השוויון הוצג בלי הוכחה, כתוצאה מקורס הסתברות ("בעיקרון לומדים את זה בהסתברות; אני מבין שאתם לא למדתם את זה" [00:06:27]). ההוכחה הובאה כאן במלואה כי היא קצרה, וכי היא מסבירה מיד למה דרושה אי־שליליות: בלעדיה אי־השוויון הנקודתי $X\ge t\cdot I$ קורס במקרה $X<0$.

אינטואיציה ומופע מספרי (מההרצאה, [00:14:12]). מרקוב אומר: משתנה אי־שלילי לא יכול להיות הרבה יותר גדול מהתוחלת שלו לעיתים קרובות. אם $\mathbb{E}[X]=3$, אז $\Pr(X\ge 6)\le\tfrac12$ — כי $6=2\mathbb{E}[X]$, כלומר $a=2$. שימו לב ש־$a$ אינו סף מוחלט אלא "פי כמה מהתוחלת".

מה מרקוב לא נותן. מרקוב חוסם מלמעלה את ההסתברות שהמשתנה גדול. הוא לא אומר כלום על ההסתברות שהמשתנה קטן. זו נקודת המפתח של השיעור, ואליה נחזור מיד. עוד שימו לב שעבור $a\le 1$ החסם הוא $\ge 1$ ולכן חסר תוכן; מרקוב מתחיל להיות שימושי רק כאשר $a>1$ [00:36:29].

משפט 3: אי־שוויון צ'בישב (העשרה — לא בחומר)

טענה. יהי $X$ משתנה מקרי בעל תוחלת ושונות סופיות. אז לכל $a>0$: $\Pr\Big(\big|X-\mathbb{E}[X]\big|>a\sqrt{V(X)}\Big)\le\frac{1}{a^2}.$

הוכחה. נגדיר $Z=(X-\mathbb{E}[X])^2$. זהו משתנה מקרי אי־שלילי, ו־$\mathbb{E}[Z]=V(X)$ לפי הגדרת השונות. המאורע $|X-\mathbb{E}[X]|>a\sqrt{V(X)}$ שקול בדיוק למאורע $Z>a^2 V(X)=a^2\,\mathbb{E}[Z]$. הפעלת מרקוב (משפט 2) על $Z$ עם המקדם $a^2$ נותנת $\Pr(Z\ge a^2\mathbb{E}[Z])\le 1/a^2$, ומכיוון שהמאורע עם $>$ מוכל במאורע עם $\ge$, נובעת הטענה. $\blacksquare$

למה הוא טוב יותר, ומה המחיר. צ'בישב חוסם דו־כיוונית (מרחק מהתוחלת בשני הכיוונים) ושואף לאפס מהר יותר — $1/a^2$ במקום $1/a$ [00:09:07]. אבל הוא דורש יותר: קיום שונות וידיעת ערכה. בשיעור נאמר במפורש: "אי־שוויון מרקוב אנחנו נשתמש בו, יש לכם אותו גם במטלה. את צ'בישב אני רק מראה לכם — אתם לא צריכים לדעת אותו בקורס הזה, אבל אתם כן צריכים לדעת שהוא קיים" [00:09:40]. במקרה שלנו חישוב $V(X)$ קשה בגלל התלויות בין הפסוקיות, ולכן ממילא לא היינו רוצים ללכת בדרך הזו.

משפט 4: חסם הסתברותי לריצה בודדת

טענה. תהי $\varphi$ נוסחת $\mathrm{3ECNF}$ עם $m$ פסוקיות, ונניח $8\mid m$. אז, מעל מטבעות האלגוריתם האקראי הבסיסי, $\Pr\left(X\ge \frac{7m}{8}\right)\ \ge\ \frac{4}{m+4}.$

מדוע לא מפעילים את מרקוב על $X$ ישירות — הניסיון שנכשל. מה שאנחנו רוצים הוא ש־$X$ יהיה גדול, כלומר חסם מלמטה על $\Pr(X\ge\cdot)$. מרקוב נותן בדיוק את ההפך: חסם מלמעלה על ההסתברות ש־$X$ גדול. המרצה עצר על כך זמן רב, כי זה בדיוק המקום שבו נופלים: "אני הייתי רוצה את האי־שוויון ההפוך, אבל אין לי את האי־שוויון ההפוך; מרקוב נותן לי כיוון אחד" [00:17:52]. הפתרון: לעבור למשלים הכמותי ולא הלוגי — לא $\Pr$ המשלימה, אלא המשתנה המשלים $Y=m-X$. מכיוון ש־"$Y$ קטן" שקול ל־"$X$ גדול", חסם מלמעלה על ההסתברות ש־$Y$ גדול הוא בדיוק החסם מלמטה שרצינו [00:18:54].

הוכחה.

שלב 1 — תנאי מרקוב. $Y=m-X$, ומכיוון ש־$0\le X\le m$ תמיד, $Y$ אי־שלילי. מליניאריות התוחלת ומשפט 1, $\mathbb{E}[Y]=m-\mathbb{E}[X]=m-\frac{7m}{8}=\frac{m}{8}.$ לכן $Y$ הוא מועמד חוקי למרקוב, ולכל $a>0$: $\Pr\left(Y> a\cdot\frac m8\right)\le \frac1a .$ (השאלה אם לכתוב $>$ או $\ge$ אינה מהותית: $\Pr(Y>t)\le\Pr(Y\ge t)$, ומרקוב חוסם כבר את הגדול מביניהם. כך נאמר גם בהרצאה [00:20:00].)

שלב 2 — בחירת $a$, וזה הלב. מה שאנחנו רוצים באמת הוא $Y\le \tfrac m8$ (שקול ל־$X\ge\tfrac{7m}{8}$). אבל הצבת $a=1$ במרקוב נותנת את החסם הריק $\Pr(Y>\tfrac m8)\le 1$. לכן מגדילים את הסף טיפה, ומנצלים ש־$Y$ מקבל ערכים שלמים: תחת ההנחה $8\mid m$ המספר $\tfrac m8$ הוא שלם, ולכן לכל $Y$ שלם $Y\le \frac m8+\frac12\ \Longleftrightarrow\ Y\le \frac m8 .$ (אם ידוע שמספר שלם קטן־שווה מ־$3.5$, ידוע שהוא קטן־שווה מ־$3$ [00:59:13].) הגדלת הסף בחצי היחידה "עולה" לנו בהסתברות, אך לא מוסיפה ולו פסוקית אחת לא־מסופקת. נחשב את ה־$a$ המתאים: $a\cdot\frac m8=\frac m8+\frac12=\frac{m+4}{8}\ \Longrightarrow\ a=\frac{m+4}{m}.$

שלב 3 — הצבה. $\Pr\left(Y>\frac m8+\frac12\right)=\Pr\left(Y>\frac{m+4}{m}\cdot\frac m8\right)\ \le\ \frac{1}{\frac{m+4}{m}}=\frac{m}{m+4}.$

שלב 4 — משלים לוגי. מעבר למאורע המשלים הופך $>$ ל־$\le$ ומחליף כיוון: $\Pr\left(Y\le\frac m8+\frac12\right)\ \ge\ 1-\frac{m}{m+4}=\frac{m+4-m}{m+4}=\frac{4}{m+4}.$

שלב 5 — שלמוּת ותרגום חזרה. לפי שלב 2, המאורע $Y\le \tfrac m8+\tfrac12$ הוא בדיוק המאורע $Y\le\tfrac m8$, ולכן $\Pr\big(Y\le \tfrac m8\big)\ge \tfrac{4}{m+4}$. לבסוף, $Y=m-X$ ולכן $Y\le\frac m8\iff m-X\le\frac m8\iff X\ge m-\frac m8=\frac{7m}{8},$ ומכאן $\Pr\big(X\ge\tfrac{7m}{8}\big)\ge\tfrac{4}{m+4}$. $\blacksquare$

הערה: בשלבים 4 ו־5 מתרחשים שני מעברים שונים שקל לבלבל ביניהם, והמרצה הפריד ביניהם במפורש [00:38:39]. שלב 4 הוא משלים לוגי של מאורע — ולכן $>$ הופך ל־$\le$ וכיוון אי־השוויון בין ההסתברויות מתהפך. שלב 5 הוא אלגברה בתוך המאורע — סידור מחדש של $Y=m-X$, שאינו נוגע בהסתברויות כלל.

הכללה ל־$m$ שרירותי (הרחבה של מה שנרמז בהרצאה). ההנחה $8\mid m$ נאמרה בהרצאה במפורש [00:34:17] אך אינה רשומה בסיכום, והיא הכרחית לשלב 2. במקרה הכללי $\tfrac m8$ אינו שלם, ותוספת של $\tfrac12$ עלולה לחצות את השלם הבא. התיקון שהוצע בהרצאה הוא להשתמש בתוספת קטנה יותר, $\tfrac{1}{16}$ [00:39:43]: מכיוון ש־$\tfrac m8$ הוא כפולה של $\tfrac18$, כל תוספת קטנה מ־$\tfrac18$ אינה מגיעה לשלם הבא, ולכן $Y\le \frac m8+\frac1{16}\iff Y\le \left\lfloor\frac m8\right\rfloor .$ עם $a\cdot\tfrac m8=\tfrac{2m+1}{16}$, כלומר $a=\tfrac{2m+1}{2m}$, מתקבל $\Pr\left(X\ge \frac{7m}{8}\right)\ \ge\ 1-\frac{2m}{2m+1}=\frac{1}{2m+1}.$ ניסוח נקי ותקף לכל $m$ (מקבלים אותו בבחירת הסף $\lfloor m/8\rfloor+1$ ישירות): $\Pr\left(X\ge \frac{7m}{8}\right)\ \ge\ \frac{1}{m+1}.$ בכל אחת מהגרסאות החסם הוא $\Theta(1/m)$, וזה כל מה שנדרש בהמשך. המרצה אמר בדיוק את זה: "הייתי מקבל קבועים קצת יותר מגעילים, אבל העיקרון היה נשאר אותו עיקרון... סדר הגודל הוא $\Theta(1/m)$" [00:43:26].

הערה: המרצה כינה את התעלול של שלב 2 "קצת רמאות" [00:42:56], ולשאלת סטודנטית "למה דווקא חצי, אפשר היה כל מספר?" ענה שאין לחצי שום חשיבות מיוחדת — הוא נבחר רק כדי שהמספרים יצאו נוחים תחת ההנחה $8\mid m$.

משפט 5: האלגוריתם המשודרג — הגברה

האלגוריתם. בהינתן נוסחה $\varphi$ בצורת $\mathrm{3ECNF}$:

1. חזור $t$ פעמים, באופן בלתי תלוי, על דגימת ההשמה של האלגוריתם הבסיסי.
2. החזר את ההשמה שסיפקה מספר מקסימלי של פסוקיות.

טענה. נניח $8\mid m$ ונבחר $t\ \ge\ \dfrac{m+4}{4}\ln 100$. אז $\Pr\left(X\ge\frac{7m}{8}\right)\ \ge\ 1-\frac{1}{100},$ כאשר $X$ הוא מספר הפסוקיות שמספקת ההשמה שהאלגוריתם מחזיר. זמן הריצה הוא $O(t\cdot|\varphi|)=O(m\cdot|\varphi|)$, כלומר פולינומי.

הוכחה.

סימונים. לכל $j=1,2,\dots,t$ נסמן ב־$X_j$ את מספר הפסוקיות שמספקת ההשמה שנדגמה בריצה $j$, וב־$X$ את מספר הפסוקיות שמספקת ההשמה המוחזרת. מהגדרת האלגוריתם, $X=\max\{X_1,X_2,\dots,X_t\}.$

מדוע "לכל" ולא "קיים". המאורע $X\ge\tfrac{7m}{8}$ הוא "קיים $j$ שעבורו $X_j\ge\tfrac{7m}{8}$", ואיתו קשה לעבוד: המאורעות $\{X_j\ge \tfrac{7m}{8}\}$ אינם זרים, ולכן אי אפשר לחבר את הסתברויותיהם; וכימות "קיים" מתורגם ל־$\vee$, בעוד שאי־תלות מתורגמת למכפלה ולכן משרתת רק את $\wedge$ [00:51:08]. לכן עוברים למאורע המשלים, שבו המקסימום הופך ל"כולם": $\max_j X_j<\frac{7m}{8}\iff \forall j:\ X_j<\frac{7m}{8}.$

חישוב. $\Pr\left(X<\frac{7m}{8}\right)=\Pr\left(\bigwedge_{j=1}^{t}\left(X_j<\frac{7m}{8}\right)\right)\overset{(\ast)}{=}\prod_{j=1}^{t}\Pr\left(X_j<\frac{7m}{8}\right)\le\left(1-\frac{4}{m+4}\right)^{t},$ כאשר $(\ast)$ היא אי־תלות בין הריצות — כל ריצה משתמשת במטבעות טריים משלה — והאי־שוויון האחרון הוא משפט 4 המופעל על כל ריצה בנפרד (לכל $j$: $\Pr(X_j<\tfrac{7m}{8})=1-\Pr(X_j\ge\tfrac{7m}{8})\le 1-\tfrac{4}{m+4}$).

כעת נשתמש באי־השוויון האלמנטרי $1-z\le e^{-z}$ התקף לכל $z\in\mathbb{R}$: $\left(1-\frac{4}{m+4}\right)^{t}\le \left(e^{-\frac{4}{m+4}}\right)^{t}=e^{-\frac{4t}{m+4}} .$

בחירת $t$. נדרוש $e^{-4t/(m+4)}\le \tfrac1{100}$. לקיחת לוגריתם טבעי (פונקציה מונוטונית עולה) נותנת $-\frac{4t}{m+4}\le -\ln 100\ \Longleftrightarrow\ \frac{4t}{m+4}\ge \ln 100\ \Longleftrightarrow\ t\ \ge\ \frac{m+4}{4}\,\ln 100 .$ (שימו לב לכפל ב־$(-1)$ שהפך את כיוון אי־השוויון — המרצה עצר על כך במפורש [00:55:59].) לכן לכל $t$ כזה, $\Pr\big(X<\tfrac{7m}{8}\big)\le\tfrac1{100}$, ובמעבר למשלים מתקבלת הטענה.

חשבון זמן ריצה. ריצה בודדת עולה $O(|\varphi|)$: דגימת ההשמה דורשת ביט אקראי אחד לכל משתנה, ומספר המשתנים אינו עולה על $|\varphi|$; וספירת הפסוקיות המסופקות היא מעבר אחד על הנוסחה. סך הכול $O(t\cdot|\varphi|)$, ועם $t=\Theta(m)$ ו־$m\le|\varphi|$ זהו $O(|\varphi|^2)$ לכל היותר — בוודאי פולינומי [00:48:28]. $\blacksquare$

הערה — למה טעות חד־צדדית היא מה שמציל אותנו כאן. האלגוריתם מחזיר את המקסימום, ולכן הוא לא יכול לטעות כלפי מעלה: אי אפשר שהמקסימום יהיה גדול ממה שבאמת הושג. הטעות היחידה האפשרית היא להשיג פחות מהיעד. המרצה קישר זאת ישירות לבחירת הכלי: "לכן גם מרקוב היה כלי טוב, כי הוא חוסם לי רק כיוון אחד" [01:01:21]. לשם השוואה, אילו היינו רוצים בדיוק $\tfrac{7m}{8}$ פסוקיות ולא "לפחות", היינו יכולים לטעות לשני הכיוונים, וההגברה על ידי מקסימום לא הייתה עובדת [01:01:51].

וריאציה. אם רוצים הסתברות כישלון $\tfrac1m$ במקום $\tfrac1{100}$, מחליפים $\ln 100$ ב־$\ln m$ ומקבלים $t=\Theta(m\log m)$ — עדיין פולינומי [00:56:29].

משפט 6: נוסחת התוחלת השלמה, והמסקנה על הממוצע

טענה (תוחלת שלמה, המקרה הבינארי). יהי $X$ משתנה מקרי בעל תוחלת ויהי $A$ מאורע עם $0<\Pr(A)<1$. אז $\mathbb{E}[X]=\mathbb{E}[X\mid A]\cdot\Pr(A)+\mathbb{E}[X\mid \bar A]\cdot \Pr(\bar A).$ במקרה שלנו $A=\{v(x_1)=1\}$ ו־$\Pr(A)=\Pr(\bar A)=\tfrac12$, ולכן $\mathbb{E}[X]=\frac{\mathbb{E}[X\mid v(x_1)=1]+\mathbb{E}[X\mid v(x_1)=0]}{2}.$

מסקנה 6א. אם $\mathbb{E}[X]=\tfrac{7m}{8}$ אז $\mathbb{E}[X\mid v(x_1)=1]\ \ge\ \frac{7m}{8}$

או

$\mathbb{E}[X\mid v(x_1)=0]\ \ge\ \frac{7m}{8}.$

הוכחה של המסקנה. זו טענה על ממוצעים בלבד. נסמן $a=\mathbb{E}[X\mid v(x_1)=1]$, $b=\mathbb{E}[X\mid v(x_1)=0]$ ו־$c=\tfrac{7m}{8}$, כך ש־$\tfrac{a+b}{2}=c$. נניח בשלילה $a<c$ וגם $b<c$. אז $c=\frac{a+b}{2}<\frac{c+c}{2}=c,$ סתירה. לכן $a\ge c$ או $b\ge c$ [הקלטה 26, 00:17:21]. $\blacksquare$

הערה: בהרצאה זה נאמר בקיצור ("אם ממוצע של שני מספרים שווה למשהו, אחד מהם חייב להיות לפחות המשהו הזה"); הפירוט כאן. שימו לב שהמסקנה נותנת $\ge$ ולא $>$: ייתכן ששני האגפים שווים בדיוק ל־$\tfrac{7m}{8}$.

משפט 7: דה־רנדומיזציה בשיטת התוחלות המותנות

זהו החלק שבו "מוציאים את האקראיות". השיטה — בניית פתרון משתנה־אחר־משתנה תוך שמירה על ערכה של תוחלת מותנית — מוצגת כאן לראשונה בקורס, ולכן היא נכתבת במלואה. הרקע שהיא נשענת עליו הוא הטענה הקיומית ההסתברותית (מסקנה 1א, בבעלות שיעור 19, ובמקבילה ל־$\mathrm{MAXCUT}$ — שיעורים 18–19): אנחנו כבר יודעים שהשמה טובה קיימת, והשאלה היחידה היא איך למצוא אותה בלי הגרלות ובלי לסרוק את כל $2^n$ ההשמות.

הערה על מיקום החומר: בפתיחת המפגש הקודם הוכרזה הדה־רנדומיזציה כיעד היום ואז נדחתה במפורש ("יכול להיות שנשאיר את זה ליום חמישי"), ולכן היא נלמדה בפועל כאן ואינה מופיעה בסיכום של שיעור 19.

האלגוריתם (דטרמיניסטי). בהינתן $\varphi$ בצורת $\mathrm{3ECNF}$ מעל $x_1,\dots,x_n$, עם $m$ פסוקיות:

לכל $i=1,\dots,n$:

1. חשב $E_1=\mathbb{E}\big[X\mid v(x_1),\dots,v(x_{i-1}),\,v(x_i)=1\big]$, כאשר $v(x_1),\dots,v(x_{i-1})$ הם הערכים שכבר נקבעו.
2. אם $E_1\ge \tfrac{7m}{8}$ — קבע $v(x_i)=1$ והצב $1$ במקום $x_i$ בנוסחה.
3. אחרת — קבע $v(x_i)=0$ והצב $0$ במקום $x_i$.

בסוף החזר את $v$.

כאן $X$ הוא, כמו תמיד, מספר הפסוקיות של הנוסחה המקורית $\varphi$ שמסופקות על ידי ההשמה שמתקבלת מהשלמת המשתנים שטרם נקבעו בהגרלה אחידה בלתי תלויה.

טענה. האלגוריתם דטרמיניסטי לחלוטין, רץ בזמן $O(|\varphi|^2)$, ומחזיר בוודאות השמה $v$ המספקת לפחות $\tfrac{7m}{8}$ מפסוקיות $\varphi$.

הוכחה.

שלב א — חישוב התוחלת המותנית הוא דטרמיניסטי, ולינארי. זו הנקודה שהמרצה חזר עליה יותר מכל אחרת [01:13:14], [הקלטה 26, 00:04:17]: כדי לחשב תוחלת אין צורך להגריל דבר. תהי $\rho$ ההשמה החלקית הנוכחית. לכל פסוקית $C_i$ של $\varphi$ נגדיר את תרומתה:

• אם $\rho$ כבר קבעה ליטרל של $C_i$ ל־$1$ — הפסוקית מסופקת בוודאות, תרומתה $1$.
• אם $\rho$ אפסה את כל שלושת הליטרלים — תרומתה $0$.
• אחרת, אם נותרו $k\in\{1,2,3\}$ ליטרלים לא־מוכרעים (מעל משתנים שונים, כי כך היה כבר בנוסחה המקורית וההצבה רק מוחקת ליטרלים) — התרומה היא $1-\left(\tfrac12\right)^{k}$.

לפי ליניאריות התוחלת (בדיוק כמו במשפט 1), $\mathbb{E}[X\mid\rho]$ הוא סכום התרומות. חישוב זה הוא מעבר בודד על הנוסחה: $O(|\varphi|)$, ואינו צורך אף ביט אקראי [הקלטה 26, 00:00:34]. לכן האלגוריתם דטרמיניסטי, למרות שבניסוחו מופיעים משתנה מקרי ותוחלת — אלה תיאורים על הנייר של ניסוי שלעולם אינו מבוצע.

שלב ב — השמורה, באינדוקציה. נסמן ב־$\rho_i$ את ההשמה החלקית שנקבעה אחרי $i$ איטרציות. נוכיח באינדוקציה על $i$: $\mathbb{E}[X\mid \rho_i]\ \ge\ \frac{7m}{8}.$

בסיס $i=0$: $\rho_0$ ריקה, ולכן $\mathbb{E}[X\mid\rho_0]=\mathbb{E}[X]=\tfrac{7m}{8}$ לפי משפט 1. זהו — וזה בלבד — המקום שבו נדרשת ההנחה ש־$\varphi$ היא $\mathrm{3ECNF}$.

צעד: נניח $\mathbb{E}[X\mid\rho_{i-1}]\ge\tfrac{7m}{8}$. לפי משפט 6 המופעל על המשתנה $x_i$ (בהינתן $\rho_{i-1}$), $\mathbb{E}[X\mid\rho_{i-1}]=\frac{\mathbb{E}[X\mid\rho_{i-1},v(x_i)=1]+\mathbb{E}[X\mid\rho_{i-1},v(x_i)=0]}{2},$ ולכן לפי מסקנה 6א לפחות אחד משני הענפים הוא לפחות $\mathbb{E}[X\mid\rho_{i-1}]\ge\tfrac{7m}{8}$. האלגוריתם בודק את הענף $v(x_i)=1$; אם הוא עומד בסף — הוא נבחר, ואז $\mathbb{E}[X\mid\rho_i]=E_1\ge\tfrac{7m}{8}$. אם אינו עומד בסף, אז בהכרח הענף השני עומד בו, והאלגוריתם בוחר בו. בשני המקרים $\mathbb{E}[X\mid\rho_i]\ge\tfrac{7m}{8}$.

שלב ג — סיום. אחרי $n$ איטרציות $\rho_n$ קובעת ערך לכל משתנה. בהינתן $\rho_n$ אין יותר אקראיות: $X$ הוא משתנה מקרי מנוון, כלומר פונקציה קבועה [הקלטה 26, 00:27:06]. תוחלת של קבוע היא הקבוע עצמו, ולכן $X(v)=\mathbb{E}[X\mid\rho_n]\ \ge\ \frac{7m}{8},$ כלומר ההשמה $v$ שהוחזרה מספקת לפחות $\tfrac{7m}{8}$ פסוקיות — בוודאות, בלי הסתברות כלל.

שלב ד — חשבון זמן ריצה. יש $n$ איטרציות; בכל איטרציה מחשבים לכל היותר שתי תוחלות מותנות, כל אחת ב־$O(|\varphi|)$, ומבצעים הצבה שגם היא $O(|\varphi|)$. מכיוון ש־$n\le|\varphi|$, סך הכול $O(n\cdot|\varphi|)=O(|\varphi|^2)$ — ריבועי [01:22:59]. $\blacksquare$

הערה — מדוע זה לא מעבר על עץ ההשמות. לשאלה טבעית מהכיתה ("אבל אתה מחשב שני ענפים כל פעם, אז זה $2^n$?") התשובה היא: בכל צומת מחשבים שני ערכים אך יורדים רק בענף אחד. סך החישובים הוא $2n$ ולא $2^n$ [01:24:35]. זו בדיוק הנקודה שבה הוכחת הקיום ההסתברותית "משלמת" — היא מבטיחה שהענף שנבחר לעולם אינו מבוי סתום.

הערה — מדוע מותר שהנוסחה השיורית אינה $\mathrm{3ECNF}$. זו הייתה שאלת המחשבה שהמרצה השאיר לכיתה בסוף השיעור [01:25:37], והתשובה ניתנה בפתיחת המפגש הבא: את התכונה "בדיוק שלושה ליטרלים מעל משתנים שונים" צריכים רק לתנאי ההתחלה — כדי לקבל $\mathbb{E}[X]=\tfrac{7m}{8}$ באיטרציה ה־$0$. מהאיטרציה הראשונה והלאה, החסם $\tfrac{7m}{8}$ אינו מחושב מחדש מהמבנה של הנוסחה השיורית אלא עובר בירושה מהאיטרציה הקודמת דרך מסקנה 6א. "מאיפה הגיע השבע שמיניות על הנוסחה החדשה? מהתוחלת הקודמת. את השלוש־אקזקט הייתי צריך רק בשביל תנאי ההתחלה" [הקלטה 26, 00:23:17]. שימו לב גם ש־$m$ בביטוי $\tfrac{7m}{8}$ הוא תמיד מספר הפסוקיות ב־$\varphi$ המקורית, ופסוקית שההצבה הפכה לאמת ממשיכה להיספר כמסופקת.

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

דוגמה 1: מרקוב במספרים

$X$ אי־שלילי עם $\mathbb{E}[X]=3$. מהו חסם על $\Pr(X\ge 6)$?

פתרון. $6=2\cdot\mathbb{E}[X]$, כלומר $a=2$, ולכן $\Pr(X\ge6)\le\tfrac12$. שימו לב ש־$a$ נמדד ביחידות של תוחלת ולא בערך מוחלט; לו היינו שואלים על $\Pr(X\ge 3)$ היינו מקבלים $a=1$ והחסם הריק $\le1$.

דוגמה 2: הגרסה ה"עצלה" של משפט 4

בהרצאה הודגם קודם חסם חלש יותר, כחימום [00:30:03]. ניקח $a=2$ במרקוב על $Y$: $\Pr\left(Y>2\cdot\frac m8\right)=\Pr\left(Y>\frac m4\right)\le\frac12 .$ לכן $\Pr\big(Y\le \tfrac m4\big)\ge\tfrac12$, ומכיוון ש־$Y=m-X$: $\Pr\left(X\ge \frac{3m}{4}\right)\ \ge\ \frac12 .$ כלומר: בהסתברות לפחות חצי, ריצה בודדת מספקת לפחות $\tfrac34$ מהפסוקיות. עם הגברה על ידי $t$ חזרות ולקיחת המקסימום, ההצלחה עולה ל־$1-\left(\tfrac12\right)^{t}$ — שלוש ריצות כבר נותנות $\tfrac78$ הסתברות להשיג $\tfrac34$ מהפסוקיות [00:17:21]. אל תתבלבלו בין שני ה־$\tfrac78$ האלה: האחד הוא הסתברות והשני הוא שבר מהפסוקיות.

דוגמה 3: מעקב מלא אחרי נוסחה קונקרטית

זו הנוסחה שבסיכום (עמוד 3) ובהרצאה [01:14:34]: $\varphi=(\bar x_1\vee x_2\vee \bar x_3)\wedge(x_1\vee \bar x_4\vee x_3)\wedge(\bar x_1\vee \bar x_2\vee x_3),\qquad m=3,\ n=4 .$

(א) התוחלת. כל פסוקית היא בדיוק שלושה ליטרלים מעל שלושה משתנים שונים, ולכן $\mathbb{E}[X_i]=\tfrac78$ לכל $i$, ומליניאריות $\mathbb{E}[X]=3\cdot\frac78=\frac{21}{8}=2.625 .$

(ב) ההתפלגות המלאה, כבדיקת שפיות. נבדוק מתי כל פסוקית נכשלת:

• $C_1$ נכשלת אך ורק כאשר $x_1=1,\ x_2=0,\ x_3=1$.
• $C_2$ נכשלת אך ורק כאשר $x_1=0,\ x_4=1,\ x_3=0$.
• $C_3$ נכשלת אך ורק כאשר $x_1=1,\ x_2=1,\ x_3=0$.

שלושת מאורעות הכישלון זרים בזוגות: $C_1$ ו־$C_3$ דורשות $x_1=1$ בעוד $C_2$ דורשת $x_1=0$; ו־$C_1$ דורשת $x_3=1$ בעוד $C_3$ דורשת $x_3=0$. מבין $2^4=16$ ההשמות, כל מאורע כישלון מתקיים ב־$2$ השמות (המשתנה הרביעי חופשי), ולכן ב־$6$ השמות בדיוק פסוקית אחת נכשלת ($X=2$), וב־$10$ השמות אף פסוקית לא נכשלת ($X=3$). בדיקה: $\mathbb{E}[X]=\frac{10\cdot3+6\cdot2}{16}=\frac{42}{16}=\frac{21}{8}\ \checkmark$ מכאן גם $\Pr\big(X\ge\tfrac{7m}{8}\big)=\Pr(X\ge 2.625)=\Pr(X=3)=\tfrac{10}{16}=0.625$ — לעומת החסם הכללי $\tfrac{1}{m+1}=\tfrac14$ שנתן משפט 4. מרקוב אכן רופף מאוד; זו המחיר של כלי שאינו מניח דבר על ההתפלגות.

(ג) קיום מול הסתברות. התוחלת $\tfrac{21}{8}$ מבטיחה לפי מסקנה 1א שקיימת השמה עם $X\ge\tfrac{21}{8}$, ומכיוון ש־$X$ שלם — עם $X\ge3$. ואכן $v=(0,1,1,1)$ מספקת את שלוש הפסוקיות.

(ד) איטרציה ראשונה של הדה־רנדומיזציה. נחשב את שתי התוחלות המותנות (זהו החישוב שבסיכום, עמוד 3):

עבור $v(x_1)=1$ הנוסחה הופכת ל־$(0\vee x_2\vee\bar x_3)\wedge(1\vee\bar x_4\vee x_3)\wedge(0\vee\bar x_2\vee x_3)$, כלומר לפסוקיות $(x_2\vee\bar x_3)$, אמת, $(\bar x_2\vee x_3)$. התרומות: $1-\tfrac14=\tfrac34$, ואז $1$, ואז $\tfrac34$. סך הכול $\mathbb{E}[X\mid v(x_1)=1]=\frac34+1+\frac34=2\tfrac12=\frac{20}{8}.$

עבור $v(x_1)=0$ הנוסחה הופכת ל־$(1\vee x_2\vee\bar x_3)\wedge(0\vee\bar x_4\vee x_3)\wedge(1\vee\bar x_2\vee x_3)$, כלומר אמת, $(\bar x_4\vee x_3)$, אמת. התרומות: $1$, $\tfrac34$, $1$. סך הכול $\mathbb{E}[X\mid v(x_1)=0]=1+\frac34+1=2\tfrac34=\frac{22}{8}.$

בדיקת עקביות עם משפט 6: $\tfrac12\left(\tfrac{20}{8}+\tfrac{22}{8}\right)=\tfrac{42}{16}=\tfrac{21}{8}=\mathbb{E}[X]$ $\checkmark$. אכן אחת התוחלות $\ge\tfrac{21}{8}$ והשנייה $\le\tfrac{21}{8}$, כפי שהעיר הסיכום בשוליים. האלגוריתם בודק תחילה את $v(x_1)=1$, מוצא $\tfrac{20}{8}<\tfrac{21}{8}$, ולכן קובע $\boxed{v(x_1)=0}$.

(ה) המשך המעקב עד הסוף (הרחבה — בהרצאה נעצרו אחרי המשתנה הראשון). אחרי ההצבה נותרנו עם שתי פסוקיות מסופקות בוודאות ועם הפסוקית $(\bar x_4\vee x_3)$; הסף שיש לשמור עליו הוא תמיד $\tfrac{7m}{8}=\tfrac{21}{8}=2.625$.

• $x_2$: אינו מופיע יותר. שני הענפים נותנים $2+\tfrac34=2.75\ge 2.625$; האלגוריתם בודק תחילה את $1$ ומקבל אותו: $v(x_2)=1$.
• $x_3$: עבור $v(x_3)=1$ הפסוקית הופכת לאמת והתוחלת היא $2+1=3\ge2.625$ — נקבע $v(x_3)=1$. (עבור $v(x_3)=0$ היינו מקבלים $2+\tfrac12=2.5<2.625$, כלומר הענף הזה היה נופל מהסף — בדיוק ההתנהגות שהמרצה תיאר בתשובה לשאלה מהכיתה [01:24:03].)
• $x_4$: הפסוקית כבר מסופקת, שני הענפים נותנים $3$; נקבע $v(x_4)=1$.

התוצאה: $v=(0,1,1,1)$, ובבדיקה ידנית — $C_1=\bar 0\vee1\vee\bar1=1$, $C_2=0\vee\bar1\vee1=1$, $C_3=\bar0\vee\bar1\vee1=1$. כל שלוש הפסוקיות מסופקות, ובוודאי $3\ge\tfrac{21}{8}$. $\checkmark$

תרגיל 1 (שאלת המרצה בסוף השיעור): למה דווקא $\mathrm{3ECNF}$?

השאלה [01:25:37]. למה היינו חייבים "בדיוק שלושה ליטרלים מעל משתנים שונים"? מה היה קורה עם ההגדרה הרגילה של $\mathrm{3CNF}$ ("לכל היותר שלושה")?

פתרון מלא. החסם $\tfrac78$ מגיע כולו מהחישוב שההסתברות שפסוקית אינה מסופקת היא $2^{-3}$. תחת "לכל היותר שלושה":

• פסוקית עם ליטרל אחד, $(x)$, אינה מסופקת בהסתברות $\tfrac12$, כלומר מסופקת בהסתברות $\tfrac12$ בלבד.
• פסוקית עם שני ליטרלים מסופקת בהסתברות $\tfrac34$.
• פסוקית עם שלושה ליטרלים אך שני משתנים, כגון $(x\vee x\vee y)$, מסופקת בהסתברות $\tfrac34$ ולא $\tfrac78$.

בהינתן נוסחת $\mathrm{3CNF}$ כללית, החסם התחתון הטוב ביותר שאפשר לתת אחיד על כל הפסוקיות הוא $\tfrac12$, ולכן היינו מקבלים $\mathbb{E}[X]\ge\tfrac{m}{2}$ בלבד — תוצאה חלשה בהרבה. זו בדיוק תשובת המרצה: "אם זה היה לכל היותר שלושה ליטרלים — מה החסם הכי טוב שהייתי יכול לתת? חצי" [01:26:10]. (הערה: אילו כל הפסוקיות היו בדיוק באורך $k$ מעל משתנים שונים, אותו חישוב היה נותן $\mathbb{E}[X]=(1-2^{-k})m$.)

תרגיל 2 (שאלת המחשבה לשיעור הבא)

השאלה. אחרי איטרציה אחת של הדה־רנדומיזציה הנוסחה כבר אינה $\mathrm{3ECNF}$. למה האלגוריתם עדיין נכון?

פתרון. ראו ההערה בסוף משפט 7: הדרישה $\mathrm{3ECNF}$ נחוצה רק לבסיס האינדוקציה. שלב האינדוקציה משתמש אך ורק בנוסחת התוחלת השלמה (משפט 6), שתקפה לכל נוסחת $\mathrm{CNF}$ שהיא, ובעובדה שהתוחלת המותנית ניתנת לחישוב מדויק בזמן לינארי גם כשאורכי הפסוקיות מעורבים ($1-2^{-k}$ עבור פסוקית עם $k$ ליטרלים חיים). לכן הערך $\tfrac{7m}{8}$ נשמר לאורך כל הריצה כירושה, ולא כתוצאה של מבנה הנוסחה השיורית.

תרגיל 3: איפה ההנחה $8\mid m$ באמת נחוצה

השאלה. הראו שבלי ההנחה $8\mid m$, הטענה $\Pr\big(X\ge\tfrac{7m}{8}\big)>\tfrac{4}{m+4}$ אינה נכונה.

פתרון. ניקח $m=5$ ושלושה משתנים $x_1,x_2,x_3$. יש בדיוק $8$ פסוקיות אפשריות של שלושה ליטרלים מעל שלושת המשתנים, וכל אחת מהן נכשלת בהשמה אחת ויחידה, ולכולן השמות כישלון שונות. נבחר $5$ מהן; נסמן את $\varphi$ כקוניונקציה שלהן. אז $Y$ (מספר הפסוקיות הלא מסופקות) מקבל ערך $1$ בדיוק כאשר ההשמה נופלת על אחת מ־$5$ נקודות הכישלון, ו־$0$ אחרת. לכן $\Pr\left(X\ge\frac{7\cdot5}{8}\right)=\Pr(Y=0)=\frac{8-5}{8}=\frac38=0.375 .$ אבל $\tfrac{4}{m+4}=\tfrac49\approx0.444>0.375$. הנוסחה $\tfrac{4}{m+4}$ נכשלת כאן. לעומת זאת החסם הכללי ממשפט 4 עומד יפה: $\tfrac1{m+1}=\tfrac16\approx0.167\le0.375$ $\checkmark$.

הערות מהשיעור

• [00:01:34] תוחלת היא מדד חלש — זו הנקודה שממנה יוצא כל השיעור. "כבר אמרתי לכם שתוחלת זה מדד מאוד חלש... ההולי גרייל זה הסתברות גבוהה." מתודולוגיה שהוצעה בפירוש: כשמנתחים אלגוריתם אקראי, בודקים קודם את התוחלת, כי אם היא לא מסתדרת כנראה שהכיוון שגוי; אבל לא עוצרים שם.
• [00:04:44] הבהרה חשובה על מדדים סטטיסטיים. שונות וסטיית תקן הן מדדי פיזור — הן לא נותנות הסתברויות. הכלי שמתרגם תוחלת (ולפעמים שונות) להסתברות הוא אי־שוויון: מרקוב, צ'בישב.
• [00:09:40] מה נדרש למבחן. מרקוב — כן, ואף מופיע במטלה. צ'בישב — לא בחומר; מספיק לדעת שהוא קיים ומה הוא נותן.
• [00:20:30] "טיוטה" מול "הוכחה". המרצה כתב את הבחירה של $a$ בתור טיוטה על הלוח והדגיש: בהוכחה כתובה מציגים את $a=\tfrac{m+4}{m}$ מוכן מראש, בלי לחשוף את חיפוש הערך. "אנחנו לא מצטטים טענות לקורא" — סדר ההצגה בהוכחה אינו סדר הגילוי.
• [00:42:56] "זה קצת רמאות". התוספת של $\tfrac12$ לסף היא תחבולה מודעת: מרקוב בסף $\tfrac m8$ בדיוק נותן את החסם הריק $1$, אז מגדילים את הסף ב"קצת" — מספיק כדי שמרקוב יהיה לא־טריוויאלי, ולא מספיק כדי לאבד ולו פסוקית אחת. אין לחצי משמעות מיוחדת; כל תוספת שאינה מגיעה לשלם הבא מתאימה.
• [00:45:37] מה נחשב "הסתברות גבוהה". שאלה מהכיתה: מה מספיק — $0.9$? $0.99$? התשובה: כל הסתברות שהיא $1/\mathrm{poly}$ מספיקה כשהטעות חד־צדדית, כי ההגברה תעלה אותה לכל רמה שנרצה במחיר פולינומי. "אם הגעתי לעשירית אני home free; אפילו אם הייתי מגיע ל־$1/m$ בעשירית — אני home free" [01:00:16].
• [00:51:08] טעות נפוצה: "קיים" מול "לכל". המאורע "אחת הריצות הצליחה" הוא כימות קיום ומתרגם ל־$\vee$; אי־תלות מתרגמת למכפלה ולכן שימושית רק ל־$\wedge$. לכן תמיד עוברים למאורע המשלים "כל הריצות נכשלו" לפני שכופלים הסתברויות. בנוסף, מאורעות ההצלחה של ריצות שונות אינם זרים ולכן אסור לחבר את הסתברויותיהם.
• [01:01:21] למה מרקוב הוא הכלי הנכון דווקא כאן. הבעיה שלנו היא "לפחות $\tfrac{7m}{8}$", כלומר טעות חד־צדדית; מרקוב הוא חסם חד־כיווני. ההתאמה אינה מקרית. אילו הייתה נדרשת תוצאה מדויקת ("בדיוק $\tfrac{7m}{8}$"), היינו יכולים לטעות לשני הכיוונים וכל המבנה — כולל ההגברה על ידי מקסימום — היה קורס.
• [01:03:58] מה קונים בדה־רנדומיזציה ומה משלמים. אותה ערובה, אותו סדר גודל של זמן ריצה, אבל בוודאות במקום בהסתברות. המחיר: האלגוריתם מסובך יותר למימוש. לעומת זאת [הקלטה 26, 00:10:06] היתרון הקלאסי של האלגוריתם האקראי הוא הפשטות הקיצונית שלו: "דוגם משהו באקראי, בודק אם זה עבד, זהו".
• [הקלטה 26, 00:04:17] הנקודה שחוזרת במבחנים. בניסוח האלגוריתם הדטרמיניסטי מופיעים "משתנה מקרי" ו"תוחלת", ובכל זאת האלגוריתם דטרמיניסטי. הסיבה: כדי לחשב תוחלת לא צריך ביטים אקראיים. "כל מה שעשינו בשיעור, גם כשכתבנו על הלוח אלגוריתמים אקראיים — החישובים עצמם היו דטרמיניסטיים."
• הקשר חיצוני (לא נאמר בהרצאה, מובא כאוריינטציה בלבד). החסם $\tfrac78$ אינו מקרי: ידוע שקירוב טוב יותר מ־$\tfrac78+\varepsilon$ ל־$\mathrm{MAX\text{-}E3SAT}$ הוא $\mathrm{NP}$־קשה. כלומר האלגוריתם הנאיבי ביותר שאפשר להעלות על הדעת הוא כבר אופטימלי מבחינת יחס הקירוב. אין להסתמך על משפט זה בבחינה בקורס הזה.

פערים בין הסיכום להקלטה

• מקור: עמוד 1–2 בסיכום, המשפט על $\Pr(Y>\tfrac m8+\tfrac12)$. הפער: הסיכום מבצע את המעבר "$Y$ שלם, ולכן $Y\le\tfrac m8+\tfrac12$ אם ורק אם $Y\le\tfrac m8$" בלי לרשום את ההנחה $8\mid m$. בהקלטה ההנחה נאמרה במפורש פעמיים [00:34:17], [00:39:43]. בלעדיה הטענה שגויה: עבור $m\equiv 5\pmod 8$ קיימת נוסחת $\mathrm{3ECNF}$ (תרגיל 3) שבה $\Pr\big(X\ge\tfrac{7m}{8}\big)=\tfrac38<\tfrac49=\tfrac{4}{m+4}$. ההכרעה: משפט 4 נוסח כאן עם ההנחה $8\mid m$ מפורשת, ובנוסף הובאה הכללה תקפה לכל $m$ (התוספת $\tfrac1{16}$ שהוצעה בהקלטה, והניסוח הנקי $\Pr\ge\tfrac1{m+1}$), ותרגיל 3 מדגים את הצורך בהנחה.
• מקור: עמוד 1 בסיכום מול ההקלטה. הפער: הסיכום פותח ב"מהשיעור הקודם" ומצטט את התוצאה $\tfrac78$ בשורה אחת בלבד, בלי החישוב שההסתברות שפסוקית נכשלת היא $\tfrac18$ ובלי ליניאריות התוחלת. ההכרעה: ההוכחה המלאה שוחזרה כאן כמשפט 1 (על בסיס ההקלטה ושיעור 19), כי כל השיעור נשען עליה ומשפט 7 משתמש בה שוב.
• מקור: ההקלטה. הפער: בהקלטה מופיעה גרסת חימום שלמה של החסם — $a=2$, $\Pr(X\ge\tfrac{3m}{4})\ge\tfrac12$, כולל דיון בהגברה $1-(\tfrac12)^t$ — שאינה בסיכום כלל. ההכרעה: נכללה כדוגמה 2, כי היא מבהירה את מנגנון הבחירה של $a$ לפני שנכנסים לחשבון המדויק.
• מקור: ההקלטה. הפער: ההסבר מדוע יש להשתמש ב"לכל $j$" ולא ב"קיים $j$" (המאורעות אינם זרים; אי־תלות משרתת רק $\wedge$) קיים בהקלטה [00:51:08] ואינו בסיכום, שבו מופיע רק המעבר הסופי. ההכרעה: נכלל בגוף ההוכחה של משפט 5.
• מקור: ההקלטה מול הסיכום. הפער: הסיכום מסתיים בעמוד 3 בחישוב האיטרציה הראשונה של הדה־רנדומיזציה בלבד; הניסוח הפורמלי של האלגוריתם, הוכחת הנכונות באינדוקציה, טיעון ה"משתנה המקרי המנוון" באיטרציה האחרונה וחשבון הזמן הריבועי הושלמו רק בפתיחת המפגש הבא. ההכרעה: הושלמו כאן ממנת ההקלטה השנייה (עד [הקלטה 26, 00:27:30]), ומסומנים בציטוט מפורש כ"הקלטה 26". מ־[00:27:36] ואילך ההקלטה עוברת למשפט $\mathrm{NP}\subseteq\mathrm{BPP}\Rightarrow\mathrm{NP}=\mathrm{P}$, שהוא חומר שיעור 21.
• מקור: ההקלטה. הפער: בסיום השיעור נשאלה שאלת מחשבה (למה מותר שהנוסחה השיורית אינה $\mathrm{3ECNF}$) שאין לה זכר בסיכום. ההכרעה: נכללה כתרגיל 2, עם התשובה שניתנה בפועל במפגש הבא.
• מקור: עמוד 1 בסיכום, ההערות בכחול בשולי אי־שוויון מרקוב. הפער: כתב היד בהערות השוליים הקצרות ליד הנוסחה קטן ולא פוענח במלואו; לפי ההקשר ולפי ההקלטה הן מוסרות את האינטואיציה ("חסם גס שאינו מניח דבר על ההתפלגות" ו"ההסתברות ש־$X$ גדול פי $a$ מהתוחלת שלו"). ההכרעה: האינטואיציה נכתבה כאן מתוך ההקלטה, שבה היא נאמרה במפורש, ולא מתוך שחזור של השוליים.
• מקור: מוסכמות הסימון. הפער: הסיכום וההרצאה כותבים את הצורה כ־$\mathrm{3ECNF}$ ("3 exact CNF"), בעוד שבספרות רווח הסימון $\mathrm{E3CNF}$; כמו כן בעיית האופטימיזציה אינה מקבלת שם בשני המקורות. ההכרעה: נשמר סימון המקור $\mathrm{3ECNF}$, ושם הבעיה $\mathrm{MAX\text{-}E3SAT}$ הובא פעם אחת ומסומן כמינוח ספרותי חיצוני.
• מקור: הסיכום וההקלטה. הפער: אין ביניהם שום סתירה מתמטית מהותית מעבר לפער ההנחה $8\mid m$ שתואר בסעיף הראשון; כל המספרים ($\tfrac{m+4}{m}$, $\tfrac{m}{m+4}$, $\tfrac{4}{m+4}$, $t=\tfrac{m+4}{4}\ln100$, $\tfrac{20}{8}$, $\tfrac{22}{8}$, $\tfrac{21}{8}$) תואמים בשני המקורות ואומתו בחישוב עצמאי. ההכרעה: confidence: high.