17Error Amplification for BPP and RP

בקצרה

• הסף שמופיע בהגדרת המחלקות ההסתברותיות אינו חלק מהתוכן: כל סף סביר נותן בדיוק את אותה מחלקה. זו כל התוצאה של השיעור.
• בטעות חד-צדדית (one-sided error), ההעצמה חזקה במיוחד: גם הסתברות הצלחה זעירה של $1/q(n)$ מספיקה — $\mathrm{RP}=\mathrm{BPP}\!\left(\frac{1}{q(n)},1\right)$ לכל פולינום $q$. מריצים $q(|x|)$ פעמים בלתי-תלויות ומקבלים אם לפחות פעם אחת התקבל "כן".
• בטעות דו-צדדית (two-sided error) אין תשובה שאפשר לסמוך עליה, ולכן מצביעים רוב. כאן חייב להיות פער של $1/\mathrm{poly}$ מעל $\frac12$ — סף של בדיוק $\frac12$ חסר-תוכן לגמרי, וסף של $\frac12+\frac{1}{2^{q(n)}}$ אינו ידוע כניתן להעצמה.
• הכלי המתמטי הוא ריכוז (concentration): משתנה בינומי מרוכז סביב התוחלת שלו. בקורס לא מוכיחים את זה בצ'רנוף אלא מחשבים בידיים זנב בינומי אחד קונקרטי.
• ההוכחה המלאה שנעשתה בכיתה: $\mathrm{BPP}=\mathrm{BPP}\!\left(\frac45,\frac45\right)$, על ידי $7$ הרצות והצבעת רוב, עם חישוב מפורש של $\sum_{k=4}^{7}\binom{7}{k}\left(\frac23\right)^k\left(\frac13\right)^{7-k}=\frac{1808}{2187}$.
• מה שמניע את כל החשבון הוא אי-התלות בין ההרצות: היא זו שמאפשרת את המעבר מהסתברות של "וגם" למכפלה ואת נוסחת ההתפלגות הבינומית.
• בסוף השיעור נפתחה בעיית החתך המינימלי ואלגוריתם הכיווץ האקראי; הניתוח שלו נדחה לשיעור 18.

רקע ותלויות

השיעור הזה יושב ישירות על שיעור 16, ולא ניתן לקרוא אותו בלעדיו. נזכיר במפורש את מה שנשתמש בו.

המודל. מכונת טיורינג הסתברותית $M$ הרצה בזמן פולינומי. בשיעור 16 ראינו שתי דרכים שקולות למדל אותה: מכונה דטרמיניסטית $M(x,r)$ המקבלת מחרוזת אקראית $r$ באורך $p(|x|)$ כקלט נוסף, או מכונה שבכל צעד מטילה מטבע. בשיעור זה המרצה עובד במודל האקראי (המכונה בוחרת בחירות אקראיות בעצמה), ולא במודל הדטרמיניסטי עם $r$ — במפורש ומסיבה מוצהרת: ההוכחה יוצאת קצרה יותר, וההדגמה שהמחרוזת האקראית גדלה כבר נעשתה בשיעור הקודם [00:12:48].

המשפחה $\mathrm{BPP}(\alpha,\beta)$. בשיעור 16 הוגדרה משפחת מחלקות שהמחלקות המוכרות הן מקרים פרטיים שלה [00:00:01]. נזכיר אותה בהגדרה 1 להלן, כי כל ניסוחי השיעור כתובים בה.

שתי זהויות מוסכמות (שיעור 16): $\mathrm{BPP}=\mathrm{BPP}\!\left(\tfrac23,\tfrac23\right),\qquad \mathrm{RP}=\mathrm{BPP}\!\left(\tfrac12,1\right)$

התוצאה שכבר הוכחה בשיעור 16 ואינה חוזרת כאן. ראו שיעור 16: לכל פולינום $q$ מתקיים $\mathrm{RP}=\mathrm{BPP}\!\left(1-\tfrac{1}{q(n)},1\right)$ כלומר, בטעות חד-צדדית אפשר להעלות את הסתברות ההצלחה מ-$\frac12$ עד קרוב מאוד ל-$1$. השיעור הנוכחי הולך לכיוון ההפוך ולכן המפתיע יותר: להתחיל מהסתברות הצלחה זעירה ולהגיע ל-$\frac12$ [00:02:41]. אלה שני חצאים משלימים של אותה טענה, והצירוף שלהם הוא שנותן ש-$\mathrm{RP}$ עמידה לכל שינוי סביר של הסף.

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

התקדים מהשיעורים הקודמים. ראו שיעור 15: באלגוריתם של Freivalds לאימות מכפלת מטריצות ($\mathrm{MATMUL}$) התחלנו מאלגוריתם עם טעות חד-צדדית והסתברות הצלחה $\frac12$, והגברנו אותה בדיוק באותה שיטה — הרצות חוזרות בלתי-תלויות ו"קבל רק אם התקבל לפחות פעם אחת" [00:36:02]. השיעור הנוכחי הוא ההכללה של אותו טריק לרמת המחלקה.

מה נדרש מהסתברות. אי-תלות של מאורעות, הסתברות של איחוד מאורעות זרים בזוגות, והתפלגות בינומית. שונות ואי-שוויוני ריכוז אינם נלמדים בקורס [00:45:04], ולכן המשפט הכללי יינתן ללא הוכחה.

הגדרות

הגדרה 1: המחלקה $\mathrm{BPP}(\alpha,\beta)$

תהיינה $\alpha,\beta$ פונקציות של $n$ (או קבועים). שפה $A$ שייכת ל-$\mathrm{BPP}(\alpha,\beta)$ אם קיימת מכונת טיורינג הסתברותית $M$ הרצה בזמן פולינומי כך שלכל קלט $x$, כאשר $n=|x|$:

$x\in A\ \Longrightarrow\ \Pr[M \text{ accepts } x]\ \ge\ \alpha(n)$ $x\notin A\ \Longrightarrow\ \Pr[M \text{ rejects } x]\ \ge\ \beta(n)$

ההסתברות היא על פני המטבעות שהמכונה מטילה, ולא על פני הקלט. הקלט אינו אקראי — הוא נתון וקבוע, ואי-הוודאות היא כולה של האלגוריתם.

אינטואיציה. $\alpha$ הוא ה"ביטחון" שהאלגוריתם נותן על yes-instances ו-$\beta$ הביטחון שהוא נותן על no-instances. שני הפרמטרים נפרדים, ולכן אפשר לתאר גם מצב א-סימטרי שבו לצד אחד יש ודאות מלאה ולצד השני כמעט כלום.

מופע. $\mathrm{BPP}=\mathrm{BPP}\!\left(\frac23,\frac23\right)$ — סימטרי, טעות דו-צדדית.

מופע גבולי חשוב. $\mathrm{BPP}\!\left(\frac12,\frac12\right)$ מכילה כל שפה שהיא, ולכן היא חסרת תוכן: המכונה "הטל מטבע, על עץ החזר accept ועל פלי החזר reject" מקיימת את שתי הדרישות בשוויון עבור כל שפה, בלי להסתכל על הקלט בכלל [00:05:18]. זהו בדיוק ה-non-instance שממחיש למה בטעות דו-צדדית חייבים לדרוש יותר מ-$\frac12$, ולא רק $\frac12$.

הערה: אזהרה על המונוטוניות — $\mathrm{BPP}(\alpha,\beta)\subseteq\mathrm{BPP}(\alpha',\beta')$ כאשר $\alpha'\le\alpha$ ו-$\beta'\le\beta$, כלומר ההכלה היא לכיוון הדרישה החלשה יותר. מכאן גם הטריק המעשי שהמרצה מלמד [00:48:45]: אם נתונה מכונה עם ערבויות א-סימטריות, למשל $\mathrm{BPP}\!\left(\frac23,\frac{9}{10}\right)$, אפשר תמיד "לרדת" לערך הקטן משניהם ולעבוד עם $\mathrm{BPP}\!\left(\frac23,\frac23\right)$.

הגדרה 2: $\mathrm{RP}$ וטעות חד-צדדית

$\mathrm{RP}=\mathrm{BPP}\!\left(\tfrac12,1\right)$

כלומר: על $x\notin A$ המכונה דוחה בהסתברות $1$ — לעולם אינה טועה; על $x\in A$ היא מקבלת בהסתברות $\ge\frac12$.

האינטואיציה, ולמה היא מבלבלת. המרצה חוזר על כך שוב ושוב שהוא בעצמו מתבלבל כאן, ובונה טבלת בלבול (confusion matrix) על הלוח [00:20:46]. הכיוון הנכון לקרוא אותה:

ב-$\mathrm{RP}$ אין false positives: על no-instance המכונה דוחה בוודאות. מכאן המסקנה התפעולית — אם המכונה החזירה accept, אפשר להאמין לה בוודאות. הטעות היחידה האפשרית היא false negative: yes-instance שנדחה [00:22:21]. ב-$\mathrm{coRP}$ המצב הפוך בדיוק.

מופע. האלגוריתם של Freivalds ל-$\mathrm{MATMUL}$ (שיעור 15) — אם המכפלה שגויה הוא תמיד מזהה, ואם היא נכונה הוא עלול "לפספס"; זהו בדיוק המבנה החד-צדדי.

הגדרה 3: הצבעת רוב (majority vote)

בהינתן $t$ הרצות בלתי-תלויות של $M$ על אותו קלט $x$, שכל אחת מחזירה accept או reject, הצבעת רוב מחזירה את התשובה שהתקבלה במספר הרצות גדול ממש מ-$t/2$.

למה $t$ חייב להיות אי-זוגי. אם $t$ אי-זוגי, לא ייתכן תיקו, ולכן ה"רוב" מוגדר היטב תמיד ואין צורך בכלל שבירת-שוויון [00:55:19]. אם $t=2m$ זוגי, המאורע $m$ מול $m$ אפשרי, "רוב" אינו מוגדר, ויש להוסיף כלל שרירותי. בסעיף הדוגמאות נראה בחשבון שהמחיר איננו רק אסתטי: $t$ זוגי עם שבירת תיקו במטבע הוגן נותן בדיוק את אותה הסתברות הצלחה כמו $t-1$ הרצות, כלומר ההרצה הזוגית האחרונה מבוזבזת לגמרי.

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

הערה: המרצה מקדיש לכך דיון שלם [00:30:48] כי סטודנטית בלבלה בין מאורעות זרים למאורעות בלתי-תלויים. ההגדרה של אי-תלות היא $\Pr[X\cap Y]=\Pr[X]\cdot\Pr[Y]$, ולא $X\cap Y=\emptyset$. למעשה, שני מאורעות זרים בעלי הסתברות חיובית הם תלויים מאוד: $\Pr[X\cap Y]=0\ne\Pr[X]\Pr[Y]$, ואינטואיטיבית — אם אחד קרה, ידוע בוודאות שהשני לא. הכלל המעשי: אי-תלות עובדת טוב עם "וגם", זרות עובדת טוב עם "או".

הגדרה 4: בעיית החתך המינימלי (MIN CUT)

קלט: גרף $G=(V,E)$ (פשוט, לא מכוון). מטרה: למצוא חלוקה של הצמתים לשתי קבוצות $(U,\bar U)$ עם $\emptyset\subsetneq U\subsetneq V$, כך שגודל החתך — מספר הקשתות שקצה אחד שלהן ב-$U$ והשני ב-$\bar U$ — יהיה מינימלי.

מדוע התנאי $\emptyset\subsetneq U\subsetneq V$ הכרחי. בלעדיו הפתרון $U=\emptyset$ (או $U=V$) הוא טריוויאלי ונותן חתך בגודל $0$ תמיד [01:12:37]. אנחנו דורשים חתך לא-מנוון.

מופע. בגרף מעגל על $4$ צמתים, כל חתך לא-מנוון גוזר לפחות $2$ קשתות, והמינימום הוא $2$.

הערת סיווג. הבעיה אינה NP-קשה: היא ניתנת לפתרון בזמן פולינומי דטרמיניסטי, אך האלגוריתם הידוע מסובך, איטי וקשה למימוש [01:14:08]. זו בדיוק המוטיבציה לאלגוריתם האקראי הפשוט שלהלן.

הגדרה 5: כיווץ קשת (contraction)

בהינתן גרף $G$ וקשת $\{x,y\}\in E$, כיווץ הקשת מייצר גרף חדש שבו $x$ ו-$y$ מוחלפים בצומת יחיד חדש, וכל הקשתות שהיו מחוברות ל-$x$ או ל-$y$ מחוברות עכשיו לצומת החדש. כל שאר הקשתות נשמרות.

התוצאה היא בדרך כלל מולטי-גרף: אם צומת $z$ היה שכן של $x$ וגם של $y$, יש עכשיו שתי קשתות מקבילות בין $z$ לצומת החדש, ומספר הקשתות נשמר. הקשת המכווצת עצמה הופכת ללולאה עצמית; אפשר למחוק אותה או להשאיר אותה — היא אינה משפיעה על אף חתך, כי שני קצותיה יימצאו לעולם באותו צד [00:07:36 בהקלטה העוקבת].

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

משפט 1: העצמה בטעות חד-צדדית מהסתברות זניחה

טענה. לכל פולינום $q$: $\mathrm{BPP}\!\left(\tfrac12,1\right)\ =\ \mathrm{RP}\ =\ \mathrm{BPP}\!\left(\tfrac{1}{q(n)},1\right)$

זו התוצאה המרכזית של השיעור, והמרצה מציין שהיא מפתיעה יותר מזו של השיעור הקודם: הסתברות ההצלחה ההתחלתית זניחה לחלוטין — למשל $1/n^{50}$ — ובכל זאת אפשר להעלות אותה ל-$\frac12$, ומשם (לפי שיעור 16) עד $1-\frac{1}{q'(n)}$ [00:02:41]. כל זה מסתמך באופן חזק ביותר על החד-צדדיות.

הכיוון הקל: $\mathrm{RP}\subseteq\mathrm{BPP}\!\left(\frac{1}{q(n)},1\right)$

זהו הכיוון של הדרישה החלשה. מכונה המקיימת $\Pr[M \text{ accepts } x]\ge\frac12$ על yes-instances מקיימת בפרט $\Pr[M \text{ accepts } x]\ge\frac{1}{q(n)}$, כי $\frac12\ge\frac{1}{q(n)}$; דרישת ה-no-instances זהה בשתי המחלקות. $\square$

הערה: בהרצאה נאמר "עבור קלטים מגודל מסוים" [00:08:32] וזה נכון ומחייב פירוט. אי-השוויון $\frac12\ge\frac1{q(n)}$ מתקיים רק כאשר $q(n)\ge2$, ופולינום עשוי לקבל ערכים קטנים מ-$2$ עבור מספר סופי של קלטים קטנים. את הקלטים האלה מטפלים כרגיל: מקודדים לתוך המכונה טבלה סופית עם התשובה הנכונה לכל אחד מהם. טבלה סופית אינה משנה לא את הזמן האסימפטוטי ולא את הפולינומיות.

הכיוון העיקרי: $\mathrm{BPP}\!\left(\frac{1}{q(n)},1\right)\subseteq\mathrm{RP}$

יהי $q$ פולינום ותהי $A\in\mathrm{BPP}\!\left(\frac{1}{q(n)},1\right)$. לפי ההגדרה קיימת מכונה הסתברותית $M$ הרצה בזמן פולינומי כך שלכל $x$:

$x\in A\ \Longrightarrow\ \Pr[M \text{ accepts } x]\ \ge\ \frac{1}{q(n)}$ $x\notin A\ \Longrightarrow\ \Pr[M \text{ rejects } x]\ \ge\ 1$

(השורה השנייה אומרת כמובן שההסתברות שווה $1$; היא נכתבת עם $\ge$ רק כדי להתאים לתבנית ההגדרה [00:29:17].)

האלגוריתם. נגדיר מכונה הסתברותית $\hat M$ באופן הבא. על קלט $x$:

1. $\hat M$ תחשב את $q(|x|)$.
2. $\hat M$ תריץ את $M$ על $x$ באופן בלתי-תלוי $q(|x|)$ פעמים.
3. $\hat M$ תקבל אם ורק אם $M$ קיבלה לפחות פעם אחת.

הערה: שלב 1 נראה מיותר אך נכתב במפורש בכוונה [00:16:32]: כדי להריץ משהו $q(|x|)$ פעמים צריך קודם כל לחשב את המספר הזה, וזהו שלב חישובי שיש להצדיק את זמנו.

הערה: מדוע דווקא "לפחות פעם אחת" ולא "רוב הפעמים"? זו בדיוק הנקודה שבה החד-צדדיות נכנסת [00:18:40]. אילו היינו דורשים רוב, לא היינו יכולים להתמודד עם הסתברות התחלתית $1/q(n)$ בכלל, כי הרוב המצופה הוא reject. אבל מכיוון שאין false positives, תשובת accept בודדת היא הוכחה חותכת ש-$x\in A$, ולכן די בה. המרצה מציין שגם אם לא יודעים מראש כמה פעמים צריך להריץ, נכון להתחיל עם פרמטר $t$ פתוח, לנתח, ורק בסוף לקבוע אותו — ולא להיתקע בבחירה [00:17:36].

ניתוח זמן ריצה. $q$ פולינום, ולכן:

• חישוב $q(|x|)$ (שלב 1) מתבצע בזמן פולינומי — חישוב ערך של פולינום על מספר בגודל $|x|$ הוא פולינומי.
• $\hat M$ מריצה את $M$ מספר פולינומי של פעמים, וכל הרצה בודדת של $M$ רצה בזמן פולינומי.
• מכפלה של פולינום בפולינום היא פולינום, ולכן סך הכל $\hat M$ רצה בזמן פולינומי. $\square$

הערה: הסגירות הזו — של הפולינומים לחיבור, לכפל ולהרכבה — היא כל ה"קסם" של המשפט, וכדאי לומר זאת במפורש [00:01:35]. אנחנו כן משלמים מחיר: אם $M$ רצה בזמן $n^2$, $\hat M$ עשויה לרוץ בזמן $n^{50}$. פשוט הרזולוציה שבה אנחנו מסתכלים על זמן ריצה — "פולינומי או לא" — גסה מכדי לראות את ההפרש. במודל הדטרמיניסטי עם מחרוזת אקראית מפורשת (שיעור 16), המחיר נראה גם באורך המחרוזת: אם $M$ צרכה $p(n)$ סיביות אקראיות, $\hat M$ צורכת $p(n)\cdot q(n)$ [00:09:39].

ניתוח הסתברותי. יהי $x$ קלט, ונסמן $n=|x|$.

מקרה א': $x\notin A$. בכל הרצה בודדת של $M$ על $x$, המכונה $M$ דוחה בהסתברות $1$. לכן בכל $q(n)$ ההרצות התקבל reject, ולכן $\hat M$ דוחה: $\Pr[\hat M \text{ rejects } x]\ =\ 1\ \ge\ 1$ כלומר $\hat M$ שומרת על החד-צדדיות — אין לה false positives, כפי שנדרש עבור $\mathrm{RP}$.

מקרה ב': $x\in A$. כאן מתחיל החשבון. המאורע "$\hat M$ מקבלת" הוא "קיימת הרצה $j$ שבה $M$ קיבלה". אי-תלות אינה מתמשקת יפה עם "קיים"/"או", אלא עם "לכל"/"וגם", ולכן עוברים למאורע המשלים [00:35:00]:

$\hat M \text{ rejects } x\quad\Longleftrightarrow\quad \text{in every iteration } j\in\{1,\dots,q(n)\},\ M \text{ rejects } x$

מכיוון שקבוצת האיטרציות סופית, הכמת "לכל" מתורגם לשרשרת סופית של "וגם" — בדיוק כפי שעשינו בבעיית שמונה המלכות ובמשפט Cook–Levin [00:34:27]. עכשיו אפשר להפעיל אי-תלות:

$\Pr[\hat M \text{ rejects } x]\ =\ \Pr\!\left[\bigwedge_{j=1}^{q(|x|)} M \text{ rejects } x \text{ in iteration } j\right]\ \overset{\text{independence}}{=}\ \prod_{j=1}^{q(|x|)}\Pr[M \text{ rejects } x \text{ in iteration } j]$

נחסום כל גורם. ידוע ש-$\Pr[M \text{ accepts } x]\ge\frac{1}{q(|x|)}$, ולכן על המאורע המשלים: $\Pr[M \text{ rejects } x \text{ in iteration } j]\ \le\ 1-\frac{1}{q(|x|)}$

הערה: המעבר הזה חשוב מספיק כדי לומר אותו במפורש [00:38:39]: אם $\Pr[B]\ge\alpha$ אז $\Pr[\bar B]\le1-\alpha$ — אי-השוויון מתהפך במעבר למשלים. אנו מבצעים את ההיפוך פעמיים: פעם כאן כדי לחסום מלמעלה את הסתברות הדחייה, ופעם בסוף כדי לחזור לחסם מלמטה על הסתברות הקבלה. הסיבה שהחסם מלמעלה על הדחייה הוא ה"טוב" עבורנו היא שאותו אנחנו יודעים לפרק למכפלה.

מכיוון שכל הגורמים אי-שליליים, אפשר להציב את החסם בכל אחד מהם: $\prod_{j=1}^{q(|x|)}\Pr[M \text{ rejects } x \text{ in iteration } j]\ \le\ \left(1-\frac{1}{q(|x|)}\right)^{q(|x|)}$

הלמה האנליטית. לכל $x\in\mathbb{R}$ מתקיים $1+x\le e^{x}$.

הערה: בהרצאה זה נאמר כעובדה מוכרת "בת מאתיים שנה" [00:40:24]; הנה ההצדקה. נגדיר $f(x)=e^{x}-1-x$. אז $f'(x)=e^{x}-1$, ולכן $f'(x)<0$ עבור $x<0$ ו-$f'(x)>0$ עבור $x>0$; מכאן ש-$f$ יורדת ואז עולה, ומקבלת מינימום גלובלי ב-$x=0$, שם $f(0)=0$. לכן $f(x)\ge0$ לכל $x$, כלומר $1+x\le e^x$. שקילות: זהו בדיוק אי-השוויון האומר שהגרף של $e^x$ נמצא מעל המשיק שלו בנקודה $0$ (קמירות).

נציב $x=-\frac{1}{q(|x|)}$ ונקבל $1-\frac{1}{q(|x|)}\le e^{-1/q(|x|)}$. שני האגפים אי-שליליים (עבור $q(|x|)\ge1$), ולכן מותר להעלות בחזקה חיובית ולשמור על הכיוון:

$\left(1-\frac{1}{q(|x|)}\right)^{q(|x|)}\ \le\ \left(e^{-\frac{1}{q(|x|)}}\right)^{q(|x|)}\ =\ e^{-1}\ =\ \frac{1}{e}\ \le\ \frac12$

המעבר האחרון נכון כי $e>2$.

לסיכום, עבור $x\in A$: $\Pr[\hat M \text{ rejects } x]\ \le\ \frac12\qquad\Longrightarrow\qquad \Pr[\hat M \text{ accepts } x]\ \ge\ \frac12$

יחד עם מקרה א', $\hat M$ היא מכונה הסתברותית פולינומית עם $\Pr[\text{accept}]\ge\frac12$ על yes-instances ו-$\Pr[\text{reject}]=1$ על no-instances, כלומר $A\in\mathrm{BPP}\!\left(\frac12,1\right)=\mathrm{RP}$. $\blacksquare$

מדוע הבחירה $q(|x|)$ ולא משהו אחר

המרצה מדגיש שהמספר הזה אינו קדוש [00:27:36]: ההוכחה עוברת בדיוק באותו אופן עבור $q(|x|)^2$, $2q(|x|)$, $q(|x|)+3$ וכן הלאה — כל דבר פולינומי ב-$|x|$ עובד, כי ניתוח זמן הריצה תלוי רק בפולינומיות, וניתוח ההסתברות רק משתפר. מה שכן קריטי הוא שהמספר יהיה פולינומי — כאן זה בדיוק המקום שבו נשבר הגבול.

מדוע $\mathrm{BPP}\!\left(\frac{1}{2^{q(n)}},1\right)$ אינה ניתנת להעצמה

זו הערה חשובה שנאמרה בכיתה [00:04:15] ואינה מופיעה בסיכום. שימו לב שהסף $\frac{1}{q(n)}$ גדול מהסף $\frac{1}{2^{q(n)}}$, כי מעריכי גדול מפולינומי; כלומר $\mathrm{BPP}\!\left(\frac{1}{2^{q(n)}},1\right)$ היא מחלקה גדולה יותר או שווה. עבורה אין לנו הוכחה שהיא שווה ל-$\mathrm{RP}$.

הסיבה נראית מיד מהחשבון: כדי להוריד את הסתברות השגיאה מתחת ל-$\frac12$ אנחנו צריכים בערך $t$ הרצות עם $t\cdot\alpha\approx1$, כלומר $t\approx1/\alpha$. עם $\alpha=\frac{1}{q(n)}$ זה $q(n)$ הרצות — פולינומי, מצוין. עם $\alpha=\frac{1}{2^{q(n)}}$ זה $2^{q(n)}$ הרצות — מעריכי, ו-$\hat M$ כבר אינה רצה בזמן פולינומי. הפולינומיות של מספר החזרות היא המשאב שההוכחה צורכת, ומספר החזרות הדרוש הוא הופכי לסף.

משפט 2 (ללא הוכחה): העצמה בטעות דו-צדדית

טענה. לכל פולינום $q$: $\mathrm{BPP}\ =\ \mathrm{BPP}\!\left(1-\frac{1}{2^{q(n)}},\,1-\frac{1}{2^{q(n)}}\right)\ =\ \mathrm{BPP}\!\left(\frac12+\frac{1}{q(n)},\,\frac12+\frac{1}{q(n)}\right)$

שתי השוויונות ביחד אומרות: כל סף בטווח שבין "מעט יותר מחצי בפער פולינומי" לבין "אחד פחות משהו זניח מעריכית" מגדיר את אותה מחלקה בדיוק, $\mathrm{BPP}$.

מדוע זה נראה שונה מהמקרה החד-צדדי. בטעות דו-צדדית אין אף תשובה שאפשר לסמוך עליה בוודאות: גם accept עלול להיות שגוי וגם reject [00:46:04]. לכן הכלל "קבל אם התקבל accept ולו פעם אחת" חסר משמעות, ובמקומו יש להצביע רוב. ומכיוון שהחלטת הרוב היא סטטיסטית ולא לוגית, היא זקוקה לכך שרוב ההרצות באמת יהיו נכונות — כלומר להטיה של ממש מעל $\frac12$.

שני גבולות שאסור לחצות:

1. סף של בדיוק $\frac12$ חסר תוכן. ראו הגדרה 1: $\mathrm{BPP}\!\left(\frac12,\frac12\right)$ מכילה כל שפה, כי מטבע הוגן משיג את הסף בלי לחשב דבר [00:05:18]. אין שום מה להעצים כאשר האלגוריתם אינו מכיל אפילו טיפת אינפורמציה.
2. פער זניח מעריכית אינו מספיק. $\mathrm{BPP}\!\left(\frac12+\frac{1}{2^{q(n)}},\frac12+\frac{1}{2^{q(n)}}\right)$ אינה ידועה כשווה ל-$\mathrm{BPP}$ [00:48:15]. הניסוח שהמרצה נתן: הפער מ-$\frac12$ מותר להיות זניח, אבל לא זניח מדי — הוא חייב להיות $1/\mathrm{poly}$, ולא $1/\exp$.

זהו הניגוד המדויק למקרה החד-צדדי: שם מותר היה לסף עצמו להיות זעיר ($1/q(n)$), כאן מותר רק לפער מהחצי להיות זעיר.

מדוע אין הוכחה כאן. ההוכחה הכללית עוברת דרך אי-שוויון ריכוז — אי-שוויון צ'רנוף (Chernoff) — שאינו נלמד בקורס ההסתברות של הסטודנטים ולא בקורס הזה [00:50:56]. המרצה הבהיר במפורש את גבולות הדרישה: את הטענה צריך לדעת, צריך לדעת להשתמש בה, וצריך לדעת שהיא נכונה — אך לא להוכיח אותה [00:51:59]. במקום ההוכחה, נעשה בכיתה מקרה פרטי מחושב בידיים, והוא משפט 3.

הסיבה שזה עובד, בשורה אחת. משתנה מקרי בינומי מרוכז סביב התוחלת שלו [01:08:48]. אם מריצים $t$ ניסויים בלתי-תלויים עם הסתברות הצלחה $\frac23$, התוחלת של מספר ההצלחות היא $\frac23 t$ — שהיא מעל $\frac{t}{2}$ — וההסתברות לסטות ממנה כלפי מטה עד מתחת ל-$\frac{t}{2}$ דועכת מעריכית ב-$t$. זה מסביר גם את הצורה של המשפט: הפער בין $\frac23$ (או $\frac12+\frac{1}{q}$) לבין $\frac12$ הוא בדיוק מרחק הסטייה שהריכוז צריך לכסות, ולכן הוא מה שההוכחה "אוכלת".

משפט 3: $\mathrm{BPP}=\mathrm{BPP}\!\left(\frac45,\frac45\right)$ — המקרה המוכח

זו גרסת הצעצוע של משפט 2 [01:08:18], והיא ההוכחה המלאה היחידה של העצמה דו-צדדית בקורס. המטרה צנועה: להעלות את $\frac23$ ל-$\frac45$ בלבד.

הכיוון הקל

$\mathrm{BPP}\!\left(\frac45,\frac45\right)\subseteq\mathrm{BPP}$, כי $\frac45\ge\frac23$ ולכן הדרישה חזקה יותר (הגדרה 1). $\square$

הכיוון העיקרי: $\mathrm{BPP}\subseteq\mathrm{BPP}\!\left(\frac45,\frac45\right)$

תהי $A\in\mathrm{BPP}$. קיימת מכונה הסתברותית $M$ הרצה בזמן פולינומי כך שלכל $x$: $x\in A\ \Longrightarrow\ \Pr[M \text{ accepts } x]\ \ge\ \tfrac23,\qquad x\notin A\ \Longrightarrow\ \Pr[M \text{ rejects } x]\ \ge\ \tfrac23$

האלגוריתם. נגדיר $\hat M$: על קלט $x$,

1. $\hat M$ תריץ את $M$ על $x$ שבע פעמים, באופן בלתי-תלוי.
2. $\hat M$ תחזיר את התשובה שהתקבלה הכי הרבה פעמים (רוב מבין $7$).

מדוע $7$ אי-זוגי. ראו הגדרה 3: $7$ אי-זוגי, ולכן קיים תמיד רוב חד-משמעי ($\ge4$ מול $\le3$) ואין צורך בכלל שבירת-תיקו [00:55:19].

מדוע דווקא $7$ ולא $5$. המרצה סיפר במפורש שניסה $5$ וזה לא עבד — ושבשנה קודמת הוא עשה את החישוב עם $5$ על הלוח, טעה בחשבון, וחשב בטעות שקיבל $\ge\frac45$ [00:56:27]. בסעיף הדוגמאות מובא החשבון שמראה בדיוק היכן $5$ נופל.

זמן ריצה. $\hat M$ מריצה את $M$ מספר קבוע של פעמים ($7$), וכל הרצה פולינומית; לכן $\hat M$ פולינומית. אין כאן אפילו צורך בחישוב מקדים של מספר החזרות כמו במשפט 1, כי $7$ קבוע [00:56:58]. $\square$

ניתוח הסתברותי. יהי $x$. היתרון של הטעות הדו-צדדית הוא הסימטריה [00:57:33]: שני המקרים ($x\in A$ ו-$x\notin A$) זהים לחלוטין, ולכן די להוכיח אחד מהם.

נניח $x\in A$, ונסמן ב-$p=p_x=\Pr[M \text{ accepts } x]$ את הסתברות ההצלחה האמיתית של $M$ על הקלט הזה; ידוע ש-$p\ge\frac23$.

$\hat M$ מקבלת בדיוק כאשר $M$ קיבלה לפחות $4$ פעמים מתוך $7$. שימו לב שכאן, בניגוד למשפט 1, אין טעם לעבור למאורע המשלים: אין כאן "קיים" שצריך להפוך ל"לכל", אלא ספירה [00:58:42].

$\Pr[\hat M \text{ accepts } x]\ =\ \Pr[M \text{ accepted at least } 4 \text{ times}]\ =\ \sum_{k=4}^{7}\Pr[M \text{ accepted exactly } k \text{ times}]$

המעבר האחרון תקף כי המאורעות "בדיוק $4$", "בדיוק $5$", "בדיוק $6$", "בדיוק $7$" הם זרים בזוגות — לא ייתכן שהמכונה קיבלה בדיוק $4$ פעמים וגם בדיוק $5$ פעמים — ולכן הסתברות האיחוד היא סכום ההסתברויות [00:59:53]. (כאן זרות היא הכלי, ולא אי-תלות; ראו ההערה בהגדרה 3.)

חישוב האיבר הבודד. מהי ההסתברות ש-$M$ קיבלה בדיוק $k$ פעמים? זו התפלגות בינומית, אבל המרצה גוזר אותה מאפס [01:00:54]:

• ראשית בוחרים באילו $k$ מתוך $7$ ההרצות תהיה הצלחה: $\binom{7}{k}$ אפשרויות.
• באותן $k$ הרצות שנבחרו נדרשת הצלחה: מכיוון שההרצות בלתי-תלויות, ההסתברות המשותפת היא מכפלה — $p^{k}$.
• בשאר $7-k$ ההרצות נדרש כישלון: $(1-p)^{7-k}$.

$\Pr[M \text{ accepted exactly } k \text{ times}]\ =\ \binom{7}{k}p^{k}(1-p)^{7-k}$

ולכן $\Pr[\hat M \text{ accepts } x]\ =\ \sum_{k=4}^{7}\binom{7}{k}p^{k}(1-p)^{7-k}\ =\ \Pr\!\left[\mathrm{Bin}(7,p)\ge4\right]$

המעבר ל-$p=\frac23$. אנחנו רוצים לחסום מלמטה באמצעות $p=\frac23$: $\Pr\!\left[\mathrm{Bin}(7,p)\ge4\right]\ \ge\ \sum_{k=4}^{7}\binom{7}{k}\left(\tfrac23\right)^{k}\left(\tfrac13\right)^{7-k}$

הערה: בהרצאה [01:03:02] ובסיכום ההצדקה שניתנה היא "כי הסתברות ההצלחה גדולה שווה $\frac23$", והיא נאמרה כאילו היא פועלת איבר-איבר. איבר-איבר זה לא נכון, וזו נקודה שכדאי לשים אליה לב: עבור $k=4$ למשל, הפונקציה $p^4(1-p)^3$ מתאפסת ב-$p=1$, ולכן היא בהחלט אינה מונוטונית עולה ב-$p$. מה שנכון הוא אי-השוויון על הסכום, כלומר על זנב ההתפלגות. הנה ההצדקה המלאה, בשיטת הצמדה (coupling): יהיו $U_1,\dots,U_7$ משתנים בלתי-תלויים אחידים על $[0,1]$, ונגדיר "הצלחה $i$ ברמה $p$" כמאורע $U_i\le p$. אז מספר ההצלחות ברמה $p$ מתפלג $\mathrm{Bin}(7,p)$, ואם $p\le p'$ אז כל הצלחה ברמה $p$ היא גם הצלחה ברמה $p'$, ולכן מספר ההצלחות ברמה $p'$ גדול או שווה נקודתית. מכאן $\Pr[\mathrm{Bin}(7,p')\ge4]\ge\Pr[\mathrm{Bin}(7,p)\ge4]$, כלומר זנב בינומי הוא מונוטוני עולה ב-$p$. הצבת $p\ge\frac23$ נותנת בדיוק את אי-השוויון שרצינו.

החשבון. (הפירוט המספרי המלא של כל ארבעת האיברים מובא בסעיף הדוגמאות.) $\sum_{k=4}^{7}\binom{7}{k}\left(\tfrac23\right)^{k}\left(\tfrac13\right)^{7-k}\ =\ \frac{560+672+448+128}{2187}\ =\ \frac{1808}{2187}\ \approx\ 0.8267\ \ge\ \frac45$

(אכן $\frac45\cdot2187=1749.6\le1808$.)

לכן עבור $x\in A$ מתקיים $\Pr[\hat M \text{ accepts } x]\ge\frac45$.

המקרה $x\notin A$. באופן זהה לחלוטין, בהחלפת התפקידים של accept ו-reject: $\Pr[M \text{ rejects } x]\ge\frac23$, $\hat M$ דוחה בדיוק כאשר $M$ דחתה לפחות $4$ פעמים מתוך $7$, ואותו חשבון בדיוק נותן $\Pr[\hat M \text{ rejects } x]\ge\frac45$.

הערה: בהרצאה נכתב כאן "באופן דומה" [01:09:20], והמרצה עצמו העיר בבדיחות שהוא נמנע מזה בדרך כלל. במקרה הזה ההצדקה אמיתית ומלאה: המבנה של $\mathrm{BPP}(\alpha,\alpha)$ סימטרי לחלוטין תחת החלפת accept ב-reject ו-$A$ במשלים שלה, ואף לא צעד אחד בחישוב משתמש בזהות של הצד. זהו בדיוק ההבדל ממשפט 1, שם המקרים היו א-סימטריים לגמרי.

מכאן $A\in\mathrm{BPP}\!\left(\frac45,\frac45\right)$. $\blacksquare$

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

דוגמה 1: החשבון הבינומי המלא של משפט 3

זהו החישוב שהמרצה הכין מראש בבית והעתיק ללוח [00:55:53]. נחשב תחילה $3^7=2187$, ונרשום את כל האיברים על מכנה משותף זה.

האיבר $k=4$: $\binom{7}{4}\left(\frac23\right)^{4}\left(\frac13\right)^{3}=\frac{7!}{4!\,3!}\cdot\frac{16}{81}\cdot\frac{1}{27}=35\cdot\frac{16}{2187}=\frac{560}{2187}$

האיבר $k=5$: $\binom{7}{5}\left(\frac23\right)^{5}\left(\frac13\right)^{2}=21\cdot\frac{32}{243}\cdot\frac{1}{9}=\frac{21\cdot32}{2187}=\frac{672}{2187}$

האיבר $k=6$: $\binom{7}{6}\left(\frac23\right)^{6}\left(\frac13\right)^{1}=7\cdot\frac{64}{729}\cdot\frac13=\frac{7\cdot64}{2187}=\frac{448}{2187}$

האיבר $k=7$: $\binom{7}{7}\left(\frac23\right)^{7}=\frac{128}{2187}$

הסכום: $\frac{560+672+448+128}{2187}=\frac{1808}{2187}\approx0.8267\ \ge\ 0.8=\frac45$

הערות חשבון שהמרצה ביצע בכיתה: $\binom74=\frac{7!}{4!\,3!}=\frac{7\cdot6\cdot5}{6}=35$; $\binom75=21$; $\binom76=7$; $81\cdot27=2187$; $35\cdot16=560$.

דוגמה 2: מדוע $5$ הרצות לא מספיקות

זו הדוגמה שהמרצה סיפר עליה כטעות של שנה שעברה [00:56:27], אך לא חישב על הלוח. הנה החשבון. עם $5$ הרצות, רוב הוא $\ge3$, והמכנה הוא $3^5=243$:

$\binom{5}{3}\left(\frac23\right)^{3}\left(\frac13\right)^{2}=10\cdot\frac{8}{27}\cdot\frac19=\frac{80}{243}$ $\binom{5}{4}\left(\frac23\right)^{4}\left(\frac13\right)^{1}=5\cdot\frac{16}{81}\cdot\frac13=\frac{80}{243}$ $\binom{5}{5}\left(\frac23\right)^{5}=\frac{32}{243}$ סה"כ:

$\frac{80+80+32}{243}=\frac{192}{243}\approx0.7901$

ואכן $0.7901<0.8$ — חסר, בהפרש קטן מאוד. זה ממחיש היטב עד כמה ההעצמה איטית כשעובדים בידיים, ולמה בפועל משתמשים באי-שוויון צ'רנוף.

דוגמה 3: מדוע מספר זוגי של הרצות מבוזבז

נניח שהיינו מריצים $6$ פעמים. אז $3^6=729$, ורוב הוא $\ge4$: $\binom{6}{4}\left(\tfrac23\right)^4\left(\tfrac13\right)^2=15\cdot\frac{16}{81}\cdot\frac19=\frac{240}{729},\quad \binom{6}{5}\left(\tfrac23\right)^5\left(\tfrac13\right)=6\cdot\frac{32}{243}\cdot\frac13=\frac{192}{729},\quad \binom{6}{6}\left(\tfrac23\right)^6=\frac{64}{729}$ סכום: $\frac{496}{729}\approx0.680$ — פחות אפילו מ-$5$ הרצות. הבעיה: המאורע "תיקו $3$ מול $3$" קיבל הסתברות $\binom63\left(\frac23\right)^3\left(\frac13\right)^3=\frac{160}{729}$ ואינו נספר.

אם נשבור את התיקו במטבע הוגן, נקבל $\frac{496}{729}+\frac12\cdot\frac{160}{729}=\frac{496+80}{729}=\frac{576}{729}=\frac{192}{243}\approx0.7901$ כלומר בדיוק התוצאה של $5$ הרצות. ההרצה השישית לא תרמה דבר. זה מנמק את הבחירה במספר אי-זוגי לא רק כנוחות סימונית אלא כהימנעות מבזבוז ממשי.

דוגמה 4: חשבון הסיביות האקראיות במשפט 1

נניח ש-$M$ המקורית משתמשת ב-$p(n)=n^2$ סיביות אקראיות ורצה בזמן $O(n^2)$, ונניח $q(n)=n^3$ (כלומר הסתברות ההצלחה ההתחלתית היא $1/n^3$). אז $\hat M$:

• מריצה את $M$ בדיוק $n^3$ פעמים,
• זמן ריצה $O(n^3\cdot n^2)=O(n^5)$ — פולינומי,
• צורכת $n^3\cdot n^2=n^5$ סיביות אקראיות — פולינומי [00:09:39],
• והסתברות הכישלון שלה על yes-instance היא לכל היותר $\left(1-\frac{1}{n^3}\right)^{n^3}\le\frac1e<0.37$.

לעומת זאת, אילו הסתברות ההצלחה ההתחלתית הייתה $2^{-n}$, היינו צריכים $2^{n}$ הרצות — ומיד יוצאים מהזמן הפולינומי. זה הקיר שתואר בסוף משפט 1.

דוגמה 5: אלגוריתם הכיווץ האקראי לחתך מינימלי (פתיחה בלבד)

בשלושים הדקות האחרונות נפתחה הבעיה הבאה, כמעבר לנושא של השיטה ההסתברותית [01:10:54]. הסיכום מקדיש לה את עמוד 3.

האלגוריתם. קלט: גרף $G=(V,E)$ לא מכוון (אפשר להניח שהוא קשיר; אחרת רכיב קשירות לא-טריוויאלי נותן חתך בגודל $0$ ואפשר להחזירו מיד לאחר BFS [01:15:17]).

1. כל עוד יש בגרף יותר משני קודקודים:
   1. בחר קשת באקראי, בהתפלגות אחידה, מבין הקשתות של הגרף הנוכחי (זה שמתעדכן תוך כדי).
   2. כווץ את הקשת שנבחרה (הגדרה 5).
2. החזר את גודל החתך בין שני הקודקודים שנותרו.

מעקב אחר מופע. נניח $V=\{1,2,3,4,5\}$ עם הקשתות $\{1,2\},\{2,3\},\{1,3\},\{1,5\},\{2,4\},\{4,5\}$, ונניח שנבחרה לכיווץ הקשת $\{1,3\}$. אחרי הכיווץ מתקבל צומת חדש $\{1,3\}$, ו:

• ל-$2$ יש עכשיו שתי קשתות מקבילות אל הצומת החדש (אחת מ-$\{1,2\}$ ואחת מ-$\{2,3\}$),
• קשת אחת מהצומת החדש אל $5$ (מ-$\{1,5\}$),
• הקשת $\{1,3\}$ עצמה הפכה ללולאה עצמית — אפשר להתעלם ממנה,
• והקשתות $\{2,4\},\{4,5\}$ נשארות כפי שהיו.

הגרף החדש הוא מולטי-גרף על $4$ צמתים. בכל איטרציה מספר הצמתים יורד בדיוק באחד, ולכן האלגוריתם עוצר אחרי $|V|-2$ איטרציות.

מה שהמרצה כבר גילה (spoiler מוצהר). האלגוריתם מצליח בהסתברות "לא משהו" — נמוכה — אבל חוזרים עליו הרבה פעמים באופן בלתי-תלוי וזה עובד טוב [01:20:06]. כלומר, בדיוק אותה טכניקת ההעצמה שהוכחנו בשיעור הזה תופעל שם. הניתוח המלא — כולל ההסתברות המדויקת להצלחה בהרצה בודדת וזמן הריצה — נעשה בשיעור 18; ראו שיעור 18.

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

• [00:01:04] המחיר של ההעצמה אינו אפס. "זה לא קסם." זמן הריצה אכן גדל, ואיתו גם מספר הסיביות האקראיות. פשוט הרשת שבה אנחנו מודדים — פולינומי מול לא-פולינומי — גסה מדי מכדי לראות את ההפרש. אם המחלקות היו מוגדרות לפי זמן $O(n^2)$ מדויק, המשפט היה שגוי.
• [00:06:22] "אני אף פעם לא זוכר את זה." המרצה חוזר שלוש פעמים על כך שהוא בעצמו מתבלבל בין false positive ל-false negative, ותמיד עוצר לצייר את טבלת הבלבול. ההמלצה המפורשת: אל תעשו את זה מהראש במבחן.
• [00:17:36] אסטרטגיה לכתיבת הוכחה. אם אינכם יודעים כמה פעמים להריץ — כתבו $t$ (המרצה הציע: באדום), המשיכו בניתוח, וקבעו את $t$ בסוף כשהחשבון יגיד לכם. "אתם לא יכולים לראות איך זה ייגמר במעמד תחילת השאלה. לא לצפות לזה, לא לכוון לזה."
• [00:27:05] נסו לשחרר את הקבוע. אחרי שההוכחה עובדת, שאלו את עצמכם על מה היא באמת נשענת. כאן: לא על הערך $q(|x|)$ אלא רק על כך שהוא פולינומי.
• [00:30:48] מלכודת: זרים $\ne$ בלתי-תלויים. שאלת סטודנטית שחשפה סוגיה אמיתית. שני מאורעות זרים בעלי הסתברות חיובית הם תלויים מאוד, כי התרחשות אחד שוללת את השני. אי-תלות היא $\Pr[X\cap Y]=\Pr[X]\Pr[Y]$.
• [00:33:54] מתי הופכים למאורע המשלים. כלל אצבע שנאמר במפורש: אי-תלות מתמשקת עם "וגם"; לכן אם המאורע שלכם הוא "קיים"/"או", הפכו למשלים כדי לקבל "לכל"/"וגם", חסמו, וחזרו. במשפט 1 עושים את ההיפוך פעמיים.
• [00:35:32] "קיים" בקבוצה סופית. מכיוון שמספר האיטרציות סופי, אין צורך בכמת בכלל — פורסים אותו לשרשרת סופית של "או". באלגוריתמים אמיתיים מספר האיטרציות תמיד סופי, בניגוד למה שהיה בקורס חישוביות.
• [00:48:45] טריק שימושי מאוד לתרגילים. אם נתונה מחלקה עם שני ספים שונים, למשל $\mathrm{BPP}\!\left(\frac23,\frac{9}{10}\right)$, אפשר תמיד להכיל אותה במחלקה הסימטרית עם הסף הקטן מבין השניים, ולעבוד עם זה. תמיד עובד, לכל כיוון שצריך.
• [00:50:26] "אני עושה הצבעה." שאלת סטודנט: "האם הרוב בהכרח נכון?" תשובה: אין "בהכרח" — יש רק הסתברות. הרוב אינו מבטיח דבר; הוא רק מגדיל את ההסתברות.
• [00:51:28] גבולות החומר. את הטענה הכללית (משפט 2) צריך לדעת, צריך לדעת להשתמש בה, וצריך לדעת שהיא נכונה. את החישוב הבינומי של משפט 3 צריך להבין ולדעת לשחזר בעיקרון, אך לא לייצר מאפס תחת לחץ זמן במבחן.
• [00:56:27] "המבוכה הייתה קשה." המרצה סיפר שבשנה שעברה עשה את החישוב עם $5$ הרצות בכיתה, טעה, וחשב שקיבל $\ge\frac45$. הלקח המעשי: בחישובים בינומיים בידיים, בדקו את הסכום עד הסוף.
• [00:45:04] מה לא בקורס. שונות ואי-שוויוני ריכוז אינם נלמדים; אינדיקטורים ולינאריות התוחלת יגיעו בשיעור הבא (שיעור 18) ויידרשו לניתוח אלגוריתם החתך.
• [00:41:26] הערת עידוד. "מקדם חיכוך קינטי תמיד קטן ממקדם חיכוך סטטי" — כלומר, במבחן עדיף לבחור ערך ולהתקדם מאשר להיתקע בשאלה מה הערך הנכון.

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

• מקור: הסיכום, עמוד 2, החישוב של האיבר $k=4$. הפער: נכתב $\frac{16}{31}$ במקום $\frac{16}{81}$ (שכן $\left(\frac23\right)^4=\frac{16}{81}$). ההכרעה: שגיאת כתיב; תוקן ל-$\frac{16}{81}$. התוצאה שהסיכום ממשיך אליה, $\frac{560}{2187}$, נכונה ומאשרת שזו שגיאת העתקה בלבד.
• מקור: ההקלטה, [00:55:19]. הפער: התמלול אומר "מספר זוגי של פעמים", אך מיד נבחר $7$ והנימוק שניתן הוא "שתמיד יהיה רוב". ההכרעה: התמלול האוטומטי החסיר את השלילה; הכוונה למספר אי-זוגי. הסיכום ($7$) מכריע. נוסף כאן חישוב מפורש (דוגמה 3) המראה שמספר זוגי מבזבז הרצה.
• מקור: שני המקורות, המעבר $\Pr[\mathrm{Bin}(7,p)\ge4]\ge\sum_{k\ge4}\binom{7}{k}\left(\frac23\right)^k\left(\frac13\right)^{7-k}$. הפער: ההצדקה נאמרה בסגנון איבר-איבר ("כי הסתברות ההצלחה $\ge\frac23$"), וזה אינו נכון איבר-איבר — $p^4(1-p)^3$ אינה עולה ב-$p$. ההכרעה: אי-השוויון עצמו נכון (על הסכום, כלומר על הזנב); נוספה כאן הצדקה מלאה במונוטוניות זנב בינומי בשיטת coupling, ומצוין במפורש שהניסוח איבר-איבר שגוי.
• מקור: ההקלטה בלבד, [00:04:15]–[00:04:46]. הפער: הדיון מדוע $\mathrm{BPP}\!\left(\frac{1}{2^{q(n)}},1\right)$ אינה ידועה כשווה ל-$\mathrm{RP}$ אינו מופיע כלל בסיכום. ההכרעה: נכלל כאן כתת-סעיף של משפט 1, עם החשבון שמסביר למה (מספר החזרות הדרוש הוא הופכי לסף).
• מקור: ההקלטה בלבד, [00:05:18] ו-[00:48:45]. הפער: ההסבר מדוע סף של בדיוק $\frac12$ בטעות דו-צדדית חסר תוכן (מטבע הוגן פותר כל שפה), והטריק של "ירידה לסף הקטן" — אינם בסיכום. ההכרעה: נכללו, הראשון כ-non-instance בהגדרה 1 והשני כהערה שם.
• מקור: ההקלטה בלבד, [00:20:46]. הפער: טבלת הבלבול המלאה (false positive / false negative מול yes/no-instance) הוצגה על הלוח והוקדשו לה כחמש דקות; בסיכום אין לה זכר. ההכרעה: נכללה כטבלה בהגדרה 2.
• מקור: ההקלטה בלבד, [00:30:48]–[00:35:32]. הפער: הדיון על אי-תלות מול זרות, ועל תרגום "קיים" ל"או" בקבוצה סופית, הוא כחמש דקות של שיעור ואינו בסיכום כלל (בסיכום מופיעה רק המילה "אי תלות" בכחול מתחת לסימן השוויון). ההכרעה: נכלל בהגדרה 3 ובהוכחת משפט 1.
• מקור: ההקלטה בלבד, [00:09:39]. הפער: ההערה שההעצמה מגדילה את המחרוזת האקראית מ-$p(n)$ ל-$p(n)\cdot q(n)$, ושבשיעור 16 זה הודגם במפורש במודל הדטרמיניסטי, אינה בסיכום. ההכרעה: נכללה כהערה בניתוח זמן הריצה ובדוגמה 4.
• מקור: ההקלטה בלבד, [00:50:56] ו-[01:08:48]. הפער: השם "אי-שוויון צ'רנוף" (בתמלול: "אי שוויון שרנו") וההסבר שהמנגנון הוא ריכוז של משתנה בינומי סביב תוחלתו — אינם בסיכום. ההכרעה: נכללו במשפט 2, יחד עם ההצהרה המפורשת שהמשפט אינו מוכח בקורס.
• מקור: ההקלטה, [01:10:54]–[01:20:37] מול עמוד 3 בסיכום. הפער: עמוד 3 מכיל רק את הגדרת בעיית החתך המינימלי ואת פסאודו-הקוד של אלגוריתם הכיווץ, בעוד שבהקלטה ניתנה גם הדגמה מצוירת של כיווץ, ההנחה שהגרף קשיר, וההערה שהבעיה פתירה בזמן פולינומי דטרמיניסטי אך האלגוריתם מסובך. ההכרעה: נכלל בהגדרות 4–5 ובדוגמה 5, בקיצור בכוונה — הניתוח שייך לשיעור 18.
• מקור: הנחיות הפרויקט מול המקורות. הפער: לא נמצאה בשני המקורות שום התייחסות לשאלה מדוע ל-$\mathrm{BPP}$ אין בעיה שלמה ידועה, או מדוע טכניקת ההעצמה אינה חלה על $\mathrm{NP}$. ההכרעה: לא הומצא דיון כזה; מצוין ב-open_questions.
• מקור: מוסכמות הסימון של הפרויקט. הפער: הסיכום כותב שמות מחלקות ללא \mathrm{} ומכניס עברית לתוך סוגריי ה-$\Pr$. ההכרעה: שמות המחלקות והבעיות נכתבו כאן ב-\mathrm{} לפי §2a; מאורעות בתוך $\Pr$ נכתבו באנגלית (accepts/rejects) כדי לא לשלב עברית בתוך בלוק מתמטי. אותיות המשתנים ($q$, $\hat M$, $x$, $k$, $j$) נשמרו בדיוק כפי שהן בסיכום.

סיכום ונקודות למבחן

התוצאות שחייבים לזכור בעל פה:

1. לכל פולינום $q$: $\ \mathrm{RP}=\mathrm{BPP}\!\left(\frac12,1\right)=\mathrm{BPP}\!\left(\frac{1}{q(n)},1\right)=\mathrm{BPP}\!\left(1-\frac{1}{q(n)},1\right)$ (השוויון האחרון משיעור 16).
2. לכל פולינום $q$: $\ \mathrm{BPP}=\mathrm{BPP}\!\left(\frac12+\frac{1}{q(n)},\frac12+\frac{1}{q(n)}\right)=\mathrm{BPP}\!\left(1-\frac{1}{2^{q(n)}},1-\frac{1}{2^{q(n)}}\right)$.
3. $\mathrm{BPP}\!\left(\frac12,\frac12\right)$ = כל השפות. חסר תוכן.
4. אי-השוויון $1+x\le e^{x}$ ומסקנתו $\left(1-\frac1t\right)^{t}\le\frac1e<\frac12$.

המלכודות הסטנדרטיות:

• בלבול כיוון ההכלה. דרישת הסתברות גבוהה יותר $\Rightarrow$ מחלקה קטנה יותר. תמיד בדקו "לאן קשה יותר להיכנס", אל תסמכו על הזיכרון.
• בלבול false positive / false negative. ב-$\mathrm{RP}$ אין false positives, ולכן accept הוא אמין לחלוטין ו-reject אינו.
• החלפת "לפחות פעם אחת" ב"רוב" (או להפך). "לפחות פעם אחת" חוקי רק בטעות חד-צדדית. "רוב" נדרש בטעות דו-צדדית, ואז חייבים מספר חזרות אי-זוגי.
• שכחת אי-התלות. בלי לומר "בלתי-תלוי" במפורש בהגדרת האלגוריתם, המעבר למכפלה ולנוסחה הבינומית אינו מוצדק ואיבדתם את ההוכחה.
• זרים במקום בלתי-תלויים. לפירוק "או" לסכום צריך זרות; לפירוק "וגם" למכפלה צריך אי-תלות. שני כלים שונים, ובשיעור הזה משתמשים בשניהם — במשפט 1 באי-תלות, במשפט 3 בשניהם.
• ניסיון להעצים סף מעריכי. $\frac{1}{2^{q(n)}}$ (בחד-צדדית) או $\frac12+\frac{1}{2^{q(n)}}$ (בדו-צדדית) — אין לנו העצמה, כי מספר החזרות היה יוצא מעריכי.
• שכחת ניתוח זמן הריצה. ההעצמה אינה שלמה בלי להראות שהמכונה החדשה עדיין פולינומית, כולל חישוב $q(|x|)$ עצמו.

צ'ק-ליסט: בסוף השיעור אתם אמורים לדעת

• לכתוב מהזיכרון את שני משפטי ההעצמה בסימון $\mathrm{BPP}(\alpha,\beta)$.
• להוכיח במלואו את $\mathrm{BPP}\!\left(\frac{1}{q(n)},1\right)\subseteq\mathrm{RP}$: אלגוריתם, זמן ריצה, שני מקרי ההסתברות, ואי-השוויון $1+x\le e^x$.
• להסביר בדיוק היכן נכנסת החד-צדדיות ולמה בלעדיה ההוכחה קורסת.
• לחשב זנב בינומי כמו $\sum_{k=4}^{7}\binom{7}{k}\left(\frac23\right)^k\left(\frac13\right)^{7-k}$ ולהצדיק את שני המעברים בו (זרות לסכום, מונוטוניות ב-$p$).
• לנמק מדוע מספר החזרות חייב להיות אי-זוגי, ומה עולה שימוש במספר זוגי.
• להסביר במשפט אחד למה סף של בדיוק $\frac12$ אינו ניתן להעצמה ולמה פער של $1/\mathrm{poly}$ כן.
• להשתמש בטענות ההעצמה כ"קופסה שחורה" בתרגיל אחר — זה השימוש הצפוי במבחן.