26חזרה למבחן ד׳: פתרון מטלה 4 — סגירות BPP לחיתוך, וארבעה אפיונים של המחלקות האקראיות

בקצרה

• זהו המפגש האחרון של הקורס, וכולו פתרון תרגילים: מטלה 4, שאלה 1 סעיף (ג) ושאלה 3 על כל סעיפיה. אין בו תיאוריה חדשה — רק שימוש מדויק בהגדרות של שיעורים 16–17.
• התוצאה המרכזית: $\mathrm{BPP}$ סגורה לחיתוך. ההוכחה איננה "נריץ את שתי המכונות ונחזיר AND" בלבד — הצירוף הזה מכפיל את הסתברויות ההצלחה, ו-$\left(\frac23\right)^2=\frac49$ קטן אפילו מ-$\frac12$. לכן חייבים להעצים קודם ל-$\mathrm{BPP}\!\left(\frac{9}{10},\frac{9}{10}\right)$, ורק אז $\left(\frac9{10}\right)^2=\frac{81}{100}\ge\frac23$.
• שאלה 3 נותנת ארבע מחלקות $\mathrm{C}_1,\dots,\mathrm{C}_4$ שכל אחת היא שינוי קטן בהגדרה ההסתברותית, ומבקשת להכריע לכל טענה: נכונה, שגויה, או שקולה לטענה פתוחה.
• התשובות. $\mathrm{C}_1=\mathrm{BPP}(\alpha,1)$, ולכן עבור $\alpha=\frac1{10}$ מתקיים $\mathrm{C}_1=\mathrm{RP}$ — נכונה, ישירות מהעצמה חד-צדדית. $\mathrm{C}_2=\mathrm{BPP}(\alpha,\alpha)$, ולכן עבור $\alpha=\frac1{10}$ היא מחלקת כל השפות ובפרט $\mathrm{C}_2\ne\mathrm{BPP}$ — הטענה שגויה; אבל עבור $\alpha=1$ מתקיים $\mathrm{C}_2=\mathrm{P}$ — נכונה.
• $\mathrm{C}_3$ היא $\mathrm{BPP}$ שבה המחרוזת האקראית באורך קבוע $5$. עבור $\alpha=\frac23$ מתקיים $\mathrm{C}_3=\mathrm{P}$ — נכונה: עוברים על כל $32$ המחרוזות ומצביעים רוב. שני התנאים חיוניים: $\alpha>\frac12$ (אחרת אין רוב) ואורך קבוע (אחרת זו בדיוק השאלה הפתוחה $\mathrm{P}=\mathrm{BPP}$).
• $\mathrm{C}_4$ דורשת הסתברות טעות קטנה מ-$\frac1{|\Omega|}$, ולכן קבוצת ה-$r$-ים השגויים ריקה — מכאן $\mathrm{C}_4=\mathrm{P}$, והטענה "$\mathrm{C}_4=\mathrm{NP}$" שקולה לשאלה הפתוחה $\mathrm{P}=\mathrm{NP}$.
• הרעיון החוזר בכל הסעיפים: תרגמו הסתברות לספירה. במרחב אחיד סופי $|E|=\Pr[E]\cdot|\Omega|$, וגודל של קבוצה הוא מספר שלם — זה מה שהופך "הסתברות גדולה מספיק" ל"כל האפשרויות" או ל"רוב מוחלט".
• הרבע האחרון של ההקלטה [01:19:20]–[01:27:10] הוא הנחיות המרצה לקראת המבחן; הן מרוכזות בסעיף האחרון של הקובץ.

אזהרת שמות. המחלקות $\mathrm{C}_1,\dots,\mathrm{C}_4$ של השיעור הזה הן וריאציות על ההגדרה ההסתברותית $\mathrm{BPP}(\alpha,\beta)$. הן אינן המחלקות $\mathrm{C}_1,\dots,\mathrm{C}_5$ של שיעור 24, שהן וריאציות על הגדרת ה-verifier של $\mathrm{NP}$. השמות זהים במקרה — שתי המטלות מספרו את המחלקות שלהן באותו אופן — והתוצאות אינן ניתנות להצלבה.

רקע ותלויות

כל התרגילים כאן נשענים על שיעורים 16 ו-17. להלן כל מה שנשתמש בו, במלואו, כדי שלא תצטרכו לקפוץ.

משפחת המחלקות $\mathrm{BPP}(\alpha,\beta)$ (שיעור 16, הגדרה 3). יהיו $\alpha,\beta\in[0,1]$. $A\in\mathrm{BPP}(\alpha,\beta)$ אם מתקיים אחד משני התנאים השקולים:

נוסח א (מכונה אקראית). קיימת מכונת טיורינג אקראית $M$ הרצה בזמן פולינומי בגודל הקלט כך שלכל $x$: $x\in A\ \Longrightarrow\ \Pr\big[M\text{ accepts }x\big]\ge\alpha,\qquad x\notin A\ \Longrightarrow\ \Pr\big[M\text{ rejects }x\big]\ge\beta .$

נוסח ב (מכונה דטרמיניסטית וסרט אקראי). קיימת מכונת טיורינג דטרמיניסטית $M$ הרצה בזמן פולינומי בגודל הקלט וקיים פולינום $p$ כך שלכל $x$: $x\in A\ \Longrightarrow\ \Pr_{r\in\{0,1\}^{p(|x|)}}\big[M\text{ accepts }(x,r)\big]\ge\alpha,\qquad x\notin A\ \Longrightarrow\ \Pr_{r\in\{0,1\}^{p(|x|)}}\big[M\text{ rejects }(x,r)\big]\ge\beta .$

מרחב ההסתברות. האקראיות היא אך ורק המטבעות של המכונה, כלומר $\Omega=\Omega(x)=\{0,1\}^{p(|x|)}$. הקלט $x$ אינו אקראי; הוא נתון ושרירותי. המרצה חזר על זה גם השיעור: "שים לב, אקראיות זה משהו שצריך להיכנס באופן מפורש. לא כתבתי פה שאני בוחר את $x$ באקראי" [00:20:21].

השמות (שיעור 16, הגדרה 4). $\mathrm{BPP}=\mathrm{BPP}\!\left(\tfrac23,\tfrac23\right),\qquad \mathrm{RP}=\mathrm{BPP}\!\left(\tfrac12,1\right),\qquad \mathrm{coRP}=\mathrm{BPP}\!\left(1,\tfrac12\right).$

עוד משיעור 16 שנשתמש בו: מונוטוניות המשפחה (משפט 1), $\mathrm{BPP}\subseteq\mathrm{PSPACE}$ (משפט 4), והעובדה ש-$\mathrm{BPP}\!\left(\frac12,\frac12\right)$ מכילה כל שפה (הערה שאחרי הגדרה 3).

משיעור 17: משפט ההעצמה החד-צדדית (משפט 1) ומשפט ההעצמה הדו-צדדית (משפט 2), וכן הצבעת הרוב (הגדרה 3).

משיעור 2: $\mathrm{PSPACE}$ מוגדרת דרך מכונות שמכריעות את השפה, ולכן כל שפה ב-$\mathrm{PSPACE}$ היא כריעה; $\mathrm{HALT}$ אינה כריעה, ולכן $\mathrm{HALT}\notin\mathrm{PSPACE}$ (ראו שם את אי-הדוגמה שאחרי הגדרה 1).

הגדרות

השאלה מתחילה ב-"יהי $\alpha\in[0,1]$. נגדיר את מחלקות הסיבוכיות הבאות." ארבע ההגדרות מובאות כאן כלשונן בדף המודפס, פרט לתיקון $x\mapsto(x,r)$ ב-$\mathrm{C}_3$ ו-$\mathrm{C}_4$ שהמרצה עשה בעצמו בשיעור [00:36:21] ושמופיע גם בכתב יד על גבי העמוד.

הגדרה 1: המחלקות $\mathrm{C}_1$ ו-$\mathrm{C}_2$

$\mathrm{C}_1$ היא מחלקת כל השפות $A$ עבורן קיימת מכונת טיורינג הסתברותית $M$ הרצה בזמן פולינומי בגודל הקלט, כך שלכל $x$: $x\in A\ \Longrightarrow\ \Pr\big[M\text{ accepts }x\big]\ge\alpha,\qquad x\notin A\ \Longrightarrow\ \Pr\big[M\text{ rejects }x\big]=1 .$

$\mathrm{C}_2$ היא אותה מחלקה בדיוק, אלא שהתנאי השני מוחלף ב-$\Pr\big[M\text{ rejects }x\big]\ge\alpha$.

התרגום המיידי. על גבי עמוד 3 בסיכום, בצד ההגדרות, כתוב בכתב יד בדיוק זה: $\mathrm{C}_1=\mathrm{BPP}(\alpha,1),\qquad \mathrm{C}_2=\mathrm{BPP}(\alpha,\alpha).$ זה לא קיצור דרך אלא התאמת תבנית מילולית אחד-לאחד מול נוסח א של הגדרת $\mathrm{BPP}(\alpha,\beta)$. המרצה הקדיש לזה שלב מפורש בפתרון: "השלב הראשון: ברמת ה-pattern matching אני בודק האם זה זהה להגדרה או לא, ואיפה ההבדל" [00:28:33]. עבור $\mathrm{C}_1$ ו-$\mathrm{C}_2$ אין הבדל, ולכן "אין לי מה לשחק עם זה יותר" [00:27:31].

אינטואיציה. $\mathrm{C}_1$ היא טעות חד-צדדית: על no-instance המכונה לעולם אינה טועה. $\mathrm{C}_2$ היא טעות דו-צדדית עם אותו סף בשני הצדדים.

מופע. כל שפה ב-$\mathrm{P}$ שייכת ל-$\mathrm{C}_1$ ול-$\mathrm{C}_2$ עבור כל $\alpha$: המכונה הדטרמיניסטית שמכריעה אותה היא בפרט מכונה אקראית שאינה מטילה מטבעות, וההסתברויות שלה הן $1\ge\alpha$.

אי-מופע מאלף. עבור $\alpha\le\frac12$ המחלקה $\mathrm{C}_2$ מפסיקה להיות אי-מופע של משהו — היא נהיית מחלקת כל השפות. זה בדיוק תוכן סעיף (ב) להלן.

הגדרה 2: המחלקה $\mathrm{C}_3$

$\mathrm{C}_3$ היא מחלקת כל השפות $A$ עבורן קיימת מכונת טיורינג דטרמיניסטית $M$ הרצה בזמן פולינומי בגודל הקלט, כך שלכל $x$: $x\in A\ \Longrightarrow\ \Pr_{r\in\{0,1\}^{5}}\big[M\text{ accepts }(x,r)\big]\ge\alpha,\qquad x\notin A\ \Longrightarrow\ \Pr_{r\in\{0,1\}^{5}}\big[M\text{ rejects }(x,r)\big]\ge\alpha .$

מה השתנה. זהו בדיוק נוסח ב של $\mathrm{BPP}(\alpha,\alpha)$, אלא שאורך המחרוזת האקראית אינו $p(|x|)$ עבור פולינום כלשהו אלא הקבוע $5$. לכן מרחב המדגם קבוע: $|\Omega|=2^5=32$, ללא תלות ב-$x$.

למה המכונה דטרמיניסטית. המרצה הסביר שהבחירה מכוונת: "כשאני רוצה לעבור מ-$\mathrm{C}_3$ ל-$\mathrm{P}$ אני רוצה מכונה דטרמיניסטית, אז אני מעדיף שמראש תהיה לי מכונה דטרמיניסטית — ולכן הגדרתי את $\mathrm{C}_3$ עם מכונה דטרמיניסטית. וגם היה לי חשוב להראות שהיא עם חמישה ביטים" [00:37:27].

מופע. $A=\Sigma^*$ שייכת ל-$\mathrm{C}_3$ לכל $\alpha$: המכונה שמתעלמת מ-$r$ ומקבלת תמיד נותנת הסתברות $1$.

אי-מופע. אף שפה לא כריעה אינה ב-$\mathrm{C}_3$, כי לפי סעיף (ד) $\mathrm{C}_3=\mathrm{P}$ כאשר $\alpha=\frac23$. שימו לב שזה לא נכון ל-$\mathrm{C}_2$ עם $\alpha=\frac1{10}$ — ובדיוק שם ההבדל בין השניים.

הגדרה 3: המחלקה $\mathrm{C}_4$

$\mathrm{C}_4$ היא מחלקת כל השפות $A$ עבורן קיימת מכונת טיורינג דטרמיניסטית $M$ הרצה בזמן פולינומי בגודל הקלט, כך שקיים פולינום $p$ שעבורו לכל $x$: $x\in A\ \Longrightarrow\ \Pr_{r\in\{0,1\}^{p(|x|)}}\big[M\text{ accepts }(x,r)\big]\ge1-\frac{1}{2^{p(|x|)+1}},$ $x\notin A\ \Longrightarrow\ \Pr_{r\in\{0,1\}^{p(|x|)}}\big[M\text{ rejects }(x,r)\big]\ge1-\frac{1}{2^{p(|x|)+1}} .$

הלב של ההגדרה. אותו פולינום $p$ מופיע פעמיים: פעם כאורך המחרוזת האקראית, ופעם במכנה של הסתברות הטעות. סטודנט זיהה את זה בכיתה [00:28:02]: "הפולינומים תלויים אחד בשני — הם מבוטאים אחד באמצעות השני". זה לא קישוט: $|\Omega|=2^{p(|x|)}$, והסתברות הטעות חסומה ב-$\frac{1}{2\cdot2^{p(|x|)}}=\frac{1}{2|\Omega|}$ — כלומר קטנה מ-$\frac{1}{|\Omega|}$. משם נובע הכול.

אינטואיציה. "הסתברות ההצלחה גבוהה יותר מ-$1$ פחות $1$ חלקי גודל מרחב המדגם, ולכן אין לי אפילו מספיק הסתברות כדי שיהיה $r$ אחד שעליו אני טועה" [01:20:57].

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

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

משפט 1: מונוטוניות במשפחה $\mathrm{BPP}(\alpha,\beta)$ — שיעור 16, משפט 1

ניסוח. אם $\hat\alpha\ge\alpha$ ו-$\hat\beta\ge\beta$ אז $\mathrm{BPP}(\hat\alpha,\hat\beta)\subseteq\mathrm{BPP}(\alpha,\beta)$.

ההוכחה בשורה (המלאה בשיעור 16): אותה מכונה בדיוק מקיימת את התנאי החלש יותר, כי $\Pr[\dots]\ge\hat\alpha\ge\alpha$. $\square$

משפט 2: העצמה דו-צדדית — שיעור 17, משפט 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).$

ההוכחה הכללית עוברת באי-שוויון צ'רנוף ואינה נדרשת בקורס; שיעור 17 הוכיח במלואו את המקרה הפרטי $\mathrm{BPP}=\mathrm{BPP}\!\left(\frac45,\frac45\right)$ בחישוב בינומי ידני. מותר ונדרש להשתמש במשפט הזה בשם, ואפילו במילה אחת: "אמפליפיקציה" [00:11:22].

מסקנה 2.1 — הצורה שנשתמש בה בפועל. $\boxed{\ \mathrm{BPP}=\mathrm{BPP}\!\left(\tfrac9{10},\tfrac9{10}\right)\ }$

הוכחה. נפעיל את משפט 2 עם הפולינום הקבוע $q\equiv4$ ונקבל $\mathrm{BPP}=\mathrm{BPP}\!\left(\frac{15}{16},\frac{15}{16}\right)$. כעת שרשרת שתי הכלות ממשפט 1: $\mathrm{BPP}\!\left(\tfrac{15}{16},\tfrac{15}{16}\right)\ \subseteq\ \mathrm{BPP}\!\left(\tfrac9{10},\tfrac9{10}\right)\ \subseteq\ \mathrm{BPP}\!\left(\tfrac23,\tfrac23\right)=\mathrm{BPP},$ הראשונה כי $\frac{15}{16}=0.9375\ge\frac9{10}$, והשנייה כי $\frac9{10}\ge\frac23$. האגף השמאלי ביותר שווה ל-$\mathrm{BPP}$, ולכן כל ההכלות בשרשרת הן שוויונות. $\blacksquare$

הערה: בהרצה זה נאמר בקיצור — "ממשפט מהשיעור, $A$ ו-$B$ שייכות ל-$\mathrm{BPP}$ תשע עשיריות תשע עשיריות. סתם זרקתי מספר" [00:11:22]. הפירוט כאן הוא ההצדקה למה מותר "לזרוק מספר", ולמה דווקא מספר כזה.

משפט 3: $\mathrm{HALT}\notin\mathrm{BPP}$

ניסוח. בעיית העצירה אינה שייכת ל-$\mathrm{BPP}$.

הוכחה. לפי שיעור 16, משפט 4, $\mathrm{BPP}\subseteq\mathrm{PSPACE}$. לפי הגדרת $\mathrm{PSPACE}$ (שיעור 2, הגדרות 1 ו-4), כל שפה בה מוכרעת על ידי מכונה דטרמיניסטית שעוצרת על כל קלט; בפרט כל שפה ב-$\mathrm{PSPACE}$ היא כריעה. $\mathrm{HALT}$ אינה כריעה, ולכן $\mathrm{HALT}\notin\mathrm{PSPACE}$, ולכן $\mathrm{HALT}\notin\mathrm{BPP}$. $\blacksquare$

למה $\mathrm{HALT}$ ולא משהו אחר. המרצה ציין שיש עוד המון אפשרויות — "$\mathrm{BPP}$ מוכלת ב-$\mathrm{PSPACE}$, אני יכול לקחת שפה ב-$\mathrm{EXPSPACE}$ שאינה ב-$\mathrm{PSPACE}$" — "אבל $\mathrm{HALT}$ תמיד מאוד נוחה בקטע הזה, כי אני יודע וברור שהיא לא שייכת" [00:31:07]. וכלל אצבע: "תמיד יותר קל לי להראות אי-שייכות למחלקות דטרמיניסטיות" [00:31:38].

משפט 4: העצמה חד-צדדית — שיעור 17, משפט 1

ניסוח. לכל פולינום $q$ מתקיים $\ \mathrm{RP}=\mathrm{BPP}\!\left(\frac{1}{q(n)},1\right)$.

מה המשפט אומר. בטעות חד-צדדית, הסתברות ההצלחה בצד ה-yes יכולה להיות קטנה כרצוננו — ובלבד שהיא לפחות $1/\mathrm{poly}$ — והמחלקה לא משתנה. ההוכחה המלאה בשיעור 17: מריצים $q(|x|)$ פעמים בלתי-תלויות ומקבלים אם התקבל accept ולו פעם אחת; הכלל הזה חוקי בדיוק מפני שבצד ה-no אין טעות כלל, ולכן accept אחד הוא הוכחה ולא עדות סטטיסטית.

מסקנה 4.1. עם הפולינום הקבוע $q\equiv10$: $\ \mathrm{BPP}\!\left(\frac1{10},1\right)=\mathrm{RP}$. $\square$

משפט 5: מהסתברות לספירה במרחב אחיד סופי

ניסוח. יהי $\Omega$ מרחב מדגם סופי עם התפלגות אחידה, ותהי $E\subseteq\Omega$. אזי $|E|=\Pr[E]\cdot|\Omega| .$

הוכחה. התפלגות אחידה מוגדרת על ידי $\Pr[E]=\frac{|E|}{|\Omega|}$; כפל בשני האגפים ב-$|\Omega|$ נותן את הטענה. $\blacksquare$

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

מסקנה 5.1 (הכלי שנשתמש בו פעמיים). אם $\Pr[E]<\frac{1}{|\Omega|}$ אז $E=\emptyset$. אכן, $|E|=\Pr[E]\cdot|\Omega|<1$, ו-$|E|$ הוא מספר שלם אי-שלילי, ולכן $|E|=0$. $\square$

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

תרגיל 1, סעיף (ג): לכל $A,B\in\mathrm{BPP}$ מתקיים $A\cap B\in\mathrm{BPP}$

הניסוח כפי שנתון. "הוכיחו את הטענות הבאות. (ג) לכל $A,B\in\mathrm{BPP}$ מתקיים $A\cap B\in\mathrm{BPP}$."

הניסיון הראשון, שנכשל — ולמה חשוב לראות אותו

השיעור התחיל בדיוק כמו שסטודנט היה מתחיל: פותחים את ההגדרה עם הקבועים המקוריים $\frac23$, בונים את המכונה הטבעית "הרץ את שתיהן וקבל אם שתיהן קיבלו", ואז מגיעים לניתוח הסמנטי ומקבלים $\Pr[M\text{ accepts }x]=\left(\tfrac23\right)^2=\tfrac49 .$ "זה לצערנו לא מספיק טוב. זה קטן ממש משני שליש — זה אפילו קטן מחצי" [00:10:10]. כלומר המכונה שבנינו גרועה ממטבע.

השלב הבא הוא הלקח המתודי המרכזי של השיעור [00:14:07]: חוזרים אחורה ומחפשים איפה נשארה חירות שלא נוצלה. החירות היא ההעצמה — לא היינו חייבים להתחיל מ-$\frac23$. "לא להיבהל מזה. הוכחה, כשאני מתכנן אותה, יכולה להיות הרבה קדימה ואחורה."

כמה בדיוק צריך? נדרש $\alpha^2\ge\frac23$, כלומר $\alpha\ge\sqrt{2/3}\approx0.8165$. שימו לב שאפילו $\frac45$ אינו מספיק: $\left(\frac45\right)^2=\frac{16}{25}=0.64<\frac23$ (אם כי כן גדול מ-$\frac12$). $\frac9{10}$ עובד, ובנוחות: $\left(\frac9{10}\right)^2=\frac{81}{100}=0.81\ge\frac23$.

ההוכחה המלאה

תהיינה $A,B\in\mathrm{BPP}$.

שלב 0 — העצמה. לפי מסקנה 2.1, $\mathrm{BPP}=\mathrm{BPP}\!\left(\frac9{10},\frac9{10}\right)$, ולכן $A,B\in\mathrm{BPP}\!\left(\frac9{10},\frac9{10}\right)$.

שלב 1 — פתיחת ההגדרות. לפי נוסח א, קיימת מכונה אקראית $M_A$ הרצה בזמן פולינומי בגודל הקלט, כך שלכל $x$: $x\in A\ \Longrightarrow\ \Pr\big[M_A\text{ accepts }x\big]\ge\tfrac9{10},\qquad x\notin A\ \Longrightarrow\ \Pr\big[M_A\text{ rejects }x\big]\ge\tfrac9{10}.$ כמו כן קיימת מכונה אקראית $M_B$ הרצה בזמן פולינומי בגודל הקלט, כך שלכל $x$: $x\in B\ \Longrightarrow\ \Pr\big[M_B\text{ accepts }x\big]\ge\tfrac9{10},\qquad x\notin B\ \Longrightarrow\ \Pr\big[M_B\text{ rejects }x\big]\ge\tfrac9{10}.$

שלב 2 — הבנייה. נבנה מכונה $M$ באופן הבא. על קלט $x$:

1. הרץ את $M_A$ על $x$.
2. הרץ את $M_B$ על $x$, באופן בלתי תלוי בשלב 1.
3. אם $M_A$ קיבלה את $x$ וגם $M_B$ קיבלה את $x$ — קבל; אחרת — דחה.

שלב 3 — ניתוח זמן ריצה. יהי $x$. זמן הריצה של $M_A$ על $x$ פולינומי ב-$|x|$; זמן הריצה של $M_B$ על $x$ פולינומי ב-$|x|$; שלב 3 הוא השוואה בעלות $O(1)$. סכום של שני פולינומים הוא פולינום, ולכן $\mathrm{time}_M(x)$ פולינומי ב-$|x|$.

שלב 4 — ניתוח סמנטי. יהי $x$.

מקרה א: $x\in A\cap B$. אז $x\in A$ וגם $x\in B$, ולכן $\Pr\big[M_A\text{ accepts }x\big]\ge\tfrac9{10},\qquad \Pr\big[M_B\text{ accepts }x\big]\ge\tfrac9{10}.$ לפי שלב 3 בבנייה, $M$ מקבלת את $x$ אם ורק אם $M_A$ מקבלת את $x$ וגם $M_B$ מקבלת את $x$. לכן $\Pr\big[M\text{ accepts }x\big]=\Pr\big[M_A\text{ accepts }x\ \wedge\ M_B\text{ accepts }x\big]=\Pr\big[M_A\text{ accepts }x\big]\cdot\Pr\big[M_B\text{ accepts }x\big]\ge\left(\tfrac9{10}\right)^2=\tfrac{81}{100}\ge\tfrac23 .$ המעבר האמצעי — פירוק המכפלה — חוקי בזכות שלב 2 בבנייה בלבד: שתי ההרצות משתמשות בסיביות אקראיות טריות, ולכן שני המאורעות בלתי תלויים.

חשבון תקציב הטעות, במפורש. הסתברות הטעות של $M$ על yes-instance היא $1-\frac{81}{100}=\frac{19}{100}=0.19\le\frac13$. לחלופין, בלי להיעזר באי-תלות כלל, חסם האיחוד נותן $\Pr\big[M\text{ rejects }x\big]=\Pr\big[M_A\text{ rejects }x\ \vee\ M_B\text{ rejects }x\big]\le\Pr\big[M_A\text{ rejects }x\big]+\Pr\big[M_B\text{ rejects }x\big]\le\tfrac1{10}+\tfrac1{10}=\tfrac15\le\tfrac13 .$ זה הלב הכמותי של כל הסעיף: הצירוף מכפיל את הסתברויות ההצלחה ולכן מחבר את הסתברויות הטעות. עם $\frac23$ מקבלים תקציב טעות $\frac13+\frac13=\frac23$ — יותר מהכול, ולכן שום דבר. עם $\frac9{10}$ מקבלים תקציב $\frac15$, ונשאר מרווח. ההעצמה היא בדיוק הכלי שקונה את המרווח הזה.

מקרה ב: $x\notin A\cap B$. אז $x\notin A$ או $x\notin B$. זו טענת "או", והיא משרה את החלוקה למקרים.

מקרה ב.1: $x\notin A$. אז $\Pr\big[M_A\text{ rejects }x\big]\ge\frac9{10}$. לפי שלב 3 בבנייה ולפי דה-מורגן, $M$ דוחה את $x$ אם ורק אם $M_A$ דוחה את $x$ או $M_B$ דוחה את $x$. לכן $\Pr\big[M\text{ rejects }x\big]=\Pr\big[M_A\text{ rejects }x\ \vee\ M_B\text{ rejects }x\big]\ \ge\ \Pr\big[M_A\text{ rejects }x\big]\ \ge\ \tfrac9{10}\ \ge\ \tfrac23 .$ אי-השוויון הראשון הוא מונוטוניות ההסתברות: המאורע $\{M_A\text{ rejects }x\}$ מוכל במאורע $\{M_A\text{ rejects }x\vee M_B\text{ rejects }x\}$, ואם $E\subseteq F$ אז $\Pr[E]\le\Pr[F]$. במקרה הזה אין צורך באי-תלות כלל.

מקרה ב.2: $x\notin B$. בדומה, בהחלפת התפקידים $A\leftrightarrow B$ ו-$M_A\leftrightarrow M_B$ בלבד: $\Pr\big[M\text{ rejects }x\big]\ \ge\ \Pr\big[M_B\text{ rejects }x\big]\ \ge\ \tfrac9{10}\ \ge\ \tfrac23 .$

בשני המקרים $\Pr[M\text{ rejects }x]\ge\frac23$.

מסקנה. $M$ היא מכונה אקראית פולינומית שמקיימת את שני תנאי $\mathrm{BPP}\!\left(\frac23,\frac23\right)$ עבור $A\cap B$, ולכן $A\cap B\in\mathrm{BPP}$. $\blacksquare$

שלוש הערות שנולדו משאלות בכיתה

(1) "מי אמר שאין תלות?" [00:08:29]. אי-תלות אינה מתנה — צריך לבנות אותה ולציין אותה. התשובה: "תמיד אפשר, כי אני פשוט לוקח source של אקראיות ומושך ממנו מחדש" [00:09:04]. ולכן המילים "באופן בלתי תלוי" בשלב 2 אינן קישוט; בלעדיהן שלב הכפל בניתוח הסמנטי אינו מוצדק.

(2) למה רק בשלב 2 כתוב "באופן בלתי תלוי"? [00:16:44]. כי $M_A$ רצה ראשונה ואין לה במה להיות תלויה. המודל שהמרצה נתן: "תחשבו על האקראיות כאילו יש לי מטבעות. האלגוריתם כל פעם מטיל מטבע, ואני אומר ל-$M_B$: תתעלמי מכל המטבעות שהוטלו עד עכשיו — צריכה מטבע? תטילי מטבע חדש" [00:17:15]. מבחינה הסתברותית התמונה סימטרית, אבל מבחינה אלגוריתמית יש סדר ביצוע, וההערה שייכת למקום שבו התלות הייתה יכולה להיווצר.

(3) הווריאציה עם קיצור דרך. סטודנט הציע לנסח את המכונה כ-"הרץ את $M_A$; אם דחתה — דחה; אחרת הרץ את $M_B$ והחזר את תשובתה" [00:14:07]. המרצה: "בעיקרון הניתוח יעבוד, אבל אתה צודק שהייתי מעדיף לעשות ככה." ההצדקה: אפשר לחשוב שתיאורטית מריצים את שתיהן מראש, והמכונה פשוט לא משתמשת בהרצה השנייה — ההתפלגות אינה משתנה. "זה לא באמת משפיע על הניתוח ההסתברותי, אבל יותר קשה לראות את זה" [00:15:42]. המסקנה המעשית: במבחן, נסחו את הבנייה בצורה שהניתוח שלה מיידי.

(4) "אפשר במקום להעצים פשוט להריץ הרבה פעמים?" [00:15:42]. אפשר — אבל אז אתם מוכיחים את משפט ההעצמה מחדש בידיים. "אני מעדיף להימנע, אם יש לי את זה כבר מוכן. זה בעצם השלב שהכנסתי לתוך קופסה שחורה" [00:16:14].

תרגיל 3: פתיחה — איך ניגשים לארבע המחלקות

לפני כל סעיף, המרצה עשה שלב שהוא שווה תרגיל בפני עצמו: סריקה של ארבע ההגדרות מול ההגדרות המוכרות, בלי לטעון דבר [00:27:01]–[00:29:05].

"עכשיו אני יודע ש-$\mathrm{C}_3$ ו-$\mathrm{C}_4$ אינן זהות להגדרות של $\mathrm{BPP}$ בשום צורה ועם שום הסתברויות, ואני יודע גם איפה ההבדל. עכשיו השאלה מה אני יכול להגיד על זה" [00:29:05].

תרגיל 3, סעיף (א): אם $\alpha=\frac1{10}$ אז $\mathrm{C}_1=\mathrm{RP}$ — נכונה

פתרון. לפי הגדרה 1, $\mathrm{C}_1=\mathrm{BPP}\!\left(\frac1{10},1\right)$. לפי משפט 4 (שיעור 17, משפט 1) עם הפולינום הקבוע $q\equiv10$: $\mathrm{BPP}\!\left(\tfrac1{10},1\right)=\mathrm{RP}. \qquad\blacksquare$

זהו כל הפתרון. "הטענה נכונה. למה? כי הוכחנו אותה בשיעור. במילה אחת: אמפליפיקציה" [00:29:36]. סעיף זה נפתר בעל פה בלבד ואינו בסיכום.

ההרחבה שהמרצה נתן. בטעות חד-צדדית אפשר להעצים גם מהסתברות הצלחה זעירה: "אם זה היה $\mathrm{BPP}\!\left(\frac1n,1\right)$ זה עדיין היה $\mathrm{RP}$, כי הטעות חד-צדדית" [00:30:07]. לעומת זאת בטעות דו-צדדית נדרש ששני הצדדים יהיו גדולים מ-$\frac12$ באופן משמעותי — "חצי ועוד $1$ חלקי פולינום; זה לא יכול להיות חצי ועוד $\frac{1}{2^n}$" [00:30:07]. ההבדל הזה הוא בדיוק ההבדל בין משפט 4 למשפט 2, והוא הנקודה שהסעיפים (א) ו-(ב) בונים עליה יחד.

תרגיל 3, סעיף (ב): אם $\alpha=\frac1{10}$ אז $\mathrm{C}_2=\mathrm{BPP}$ — שגויה

זהו הסעיף הראשון שנפתר בכתב, בעמוד 3 בסיכום.

מה צריך להראות. אי-שוויון בין קבוצות, כלומר: שפה השייכת לאחת ולא לשנייה [00:31:07]. הכיוון הנוח הוא למצוא שפה ב-$\mathrm{C}_2$ שאינה ב-$\mathrm{BPP}$.

נתבונן ב-$\mathrm{HALT}$.

חלק ראשון: $\mathrm{HALT}\notin\mathrm{BPP}$. זה משפט 3 לעיל: $\mathrm{HALT}\notin\mathrm{PSPACE}$ ולכן $\mathrm{HALT}\notin\mathrm{BPP}$.

חלק שני: $\mathrm{HALT}\in\mathrm{C}_2$. נגדיר מכונה אקראית $M$ באופן הבא. על קלט $x$:

1. הגרל $r\in\{0,1\}$ באופן אחיד.
2. אם $r=1$ — קבל; אחרת — דחה.

זמן ריצה. $M$ מטילה מטבע אחד ומחליטה; זמן הריצה שלה קבוע, ובפרט פולינומי ב-$|x|$.

ניתוח סמנטי. יהי $x$.

• אם $x\in\mathrm{HALT}$: $\ \Pr\big[M\text{ accepts }x\big]=\frac12\ge\frac1{10}$.
• אם $x\notin\mathrm{HALT}$: $\ \Pr\big[M\text{ rejects }x\big]=\frac12\ge\frac1{10}$.

שני התנאים של $\mathrm{C}_2$ עם $\alpha=\frac1{10}$ מתקיימים, ולכן $\mathrm{HALT}\in\mathrm{C}_2$.

מסקנה. $\mathrm{HALT}\in\mathrm{C}_2\setminus\mathrm{BPP}$, ולכן $\mathrm{C}_2\ne\mathrm{BPP}$. הטענה שגויה. $\blacksquare$

מה באמת קרה כאן. המכונה $M$ אפילו לא מסתכלת בקלט. הניסוח של המרצה: "אם הסתברות ההצלחה היא סך הכול גדולה שווה עשירית — I might as well flip a coin" [00:34:48]. למעשה ההוכחה מראה יותר מהנדרש: לכל שפה $A$ (ולא רק $\mathrm{HALT}$) אותה מכונה מוכיחה $A\in\mathrm{C}_2$, ולכן עבור כל $\alpha\le\frac12$ המחלקה $\mathrm{C}_2=\mathrm{BPP}(\alpha,\alpha)$ היא מחלקת כל השפות — בדיוק כפי ששיעור 16 ציין עבור $\mathrm{BPP}\!\left(\frac12,\frac12\right)$.

הערה על אנלוגיה שהמרצה הזכיר. ב-[00:34:48] הוא ציין ש"זה מאוד מזכיר את מה שעשינו עם $\mathrm{NP}$ בפעם הקודמת, עם ה'קיים וקיים'" — שם גם כן מחלקה שנראתה כמו $\mathrm{NP}$ התגלתה כמחלקת כל השפות, ו-$\mathrm{HALT}$ שימשה כעד. זו אנלוגיה מתודית בלבד; המחלקה ההיא (שיעור 24) היא אובייקט אחר לגמרי, ואין להצליב את התוצאות.

תרגיל 3, סעיף (ג): אם $\alpha=1$ אז $\mathrm{C}_2=\mathrm{P}$ — נכונה

סעיף זה נפתר בעל פה [00:35:19]–[00:36:21] ואינו בסיכום. $\mathrm{C}_2=\mathrm{BPP}(1,1)$.

כיוון $\mathrm{C}_2\subseteq\mathrm{P}$. תהא $A\in\mathrm{BPP}(1,1)$. לפי נוסח ב קיימת מכונה דטרמיניסטית $M_A$ הרצה בזמן פולינומי וקיים פולינום $p$ כך שלכל $x$: $x\in A\Longrightarrow\Pr_{r\in\{0,1\}^{p(|x|)}}\big[M_A\text{ accepts }(x,r)\big]\ge1,\qquad x\notin A\Longrightarrow\Pr_{r\in\{0,1\}^{p(|x|)}}\big[M_A\text{ rejects }(x,r)\big]\ge1 .$ הסתברות אינה עולה על $1$, ולכן אלה שוויונות. במרחב אחיד סופי, מאורע בהסתברות $1$ הוא כל המרחב (משפט 5 עם המשלים): קבוצת ה-$r$-ים שעליהם המכונה טועה היא בגודל $0\cdot2^{p(|x|)}=0$, כלומר ריקה. לכן לכל $r\in\{0,1\}^{p(|x|)}$ המכונה $M_A$ עונה נכון על $(x,r)$.

נבנה מכונה דטרמיניסטית $M$. על קלט $x$:

1. חשב $p(|x|)$ וכתוב $r=0^{p(|x|)}$.
2. הרץ את $M_A$ על $(x,r)$ והחזר את תשובתה.

זמן ריצה. $p$ פולינום קבוע וניתן לחישוב בזמן פולינומי, וכתיבת $0^{p(|x|)}$ אורכת $O(p(|x|))$; הרצת $M_A$ על $(x,r)$ פולינומית ב-$|x|+p(|x|)$, שהוא פולינומי ב-$|x|$. לכן $\mathrm{time}_M(x)$ פולינומי ב-$|x|$.

ניתוח סמנטי. לפי הקודם $M_A$ צודקת על כל $r$, ובפרט על $r=0^{p(|x|)}$. לכן $M$ מקבלת את $x$ אם ורק אם $x\in A$, כלומר $M$ מכריעה את $A$ בזמן פולינומי, ולכן $A\in\mathrm{P}$. $\square$

כיוון $\mathrm{P}\subseteq\mathrm{C}_2$. תהא $A\in\mathrm{P}$ ותהי $M_A$ מכונה דטרמיניסטית פולינומית שמכריעה אותה. $M_A$ היא בפרט מכונה אקראית שאינה מטילה אף מטבע, ולכן לכל $x$: אם $x\in A$ אז $\Pr[M_A\text{ accepts }x]=1$, ואם $x\notin A$ אז $\Pr[M_A\text{ rejects }x]=1$. שני התנאים של $\mathrm{BPP}(1,1)$ מתקיימים, ולכן $A\in\mathrm{C}_2$. $\square$

מכאן $\mathrm{C}_2=\mathrm{P}$. $\blacksquare$

הניסוח של המרצה [00:36:21]: "אם הסתברות ההצלחה היא אחת, גם בדחייה וגם בקבלה — היא תמיד צודקת. איך אני מראה שזה $\mathrm{P}$? אני בונה מכונה דטרמיניסטית שפשוט מכניסה למכונה האקראית מחרוזת אקראית קבועה, ובגלל שהסתברות ההצלחה היא אחת אני יודע שזה יחזיר את התשובה הנכונה."

תרגיל 3, סעיף (ד): אם $\alpha=\frac23$ אז $\mathrm{C}_3=\mathrm{P}$ — נכונה

זהו הסעיף הארוך בסיכום (עמודים 4–5) ובהקלטה [00:45:18]–[01:10:14].

כיוון ראשון: $\mathrm{C}_3\subseteq\mathrm{P}$

תהא $A\in\mathrm{C}_3$. אזי קיימת מכונת טיורינג דטרמיניסטית $M_A$ הרצה בזמן פולינומי בגודל הקלט, כך שלכל $x$: $x\in A\ \Longrightarrow\ \Pr_{r\in\{0,1\}^5}\big[M_A\text{ accepts }(x,r)\big]\ge\tfrac23,\qquad x\notin A\ \Longrightarrow\ \Pr_{r\in\{0,1\}^5}\big[M_A\text{ rejects }(x,r)\big]\ge\tfrac23 .$

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

1. לכל $r\in\{0,1\}^5$: 1.1. הרץ את $M_A$ על $(x,r)$.
2. החזר את התשובה של $M_A$ שחזרה על עצמה הכי הרבה פעמים (הצבעת רוב).

ניתוח זמן ריצה. בהרצת $M$ על $x$, מספר האיטרציות בלולאה הוא $|\{0,1\}^5|=2^5=32$ — קבוע, שאינו תלוי ב-$x$, כי אורך $r$ קבוע. זמן הריצה של כל איטרציה: $M_A$ רצה על $(x,r)$ שאורכו $|x|+5$, ולכן פולינומי ב-$|x|$. ניהול שני המונים עולה $O(1)$ לאיטרציה. לכן $\mathrm{time}_M(x)\ \le\ 32\cdot\mathrm{poly}(|x|)+O(1)\ =\ \mathrm{poly}(|x|).$

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

ניתוח סמנטי. יהי $x$.

מקרה א: $x\in A$. אז $\Pr_{r\in\{0,1\}^5}\big[M_A\text{ accepts }(x,r)\big]\ge\frac23$. כאן עוברים מהסתברות לקומבינטוריקה (משפט 5), כי $r$ נדגם אחיד ממרחב בגודל $32$: $\Big|\big\{r\in\{0,1\}^5\ :\ M_A\text{ accepts }(x,r)\big\}\Big|\ =\ \Pr_r\big[M_A\text{ accepts }(x,r)\big]\cdot32\ \ge\ \tfrac23\cdot32\ =\ \tfrac{64}{3}\ >\ 16 .$ בסך הכול יש $32$ מחרוזות, ויותר מ-$16$ מהן מובילות ל-accept; לכן accept היא הרוב המוחלט, ולכן $M$ מקבלת את $x$.

מקרה ב: $x\notin A$. בדומה, בהחלפת accept ב-reject: $\Big|\big\{r\in\{0,1\}^5\ :\ M_A\text{ rejects }(x,r)\big\}\Big|\ \ge\ \tfrac23\cdot32\ >\ 16 ,$ ולכן reject היא הרוב המוחלט ו-$M$ דוחה את $x$.

לכן $M$ מכריעה את $A$ בזמן פולינומי, כלומר $A\in\mathrm{P}$. $\square$

כיוון שני: $\mathrm{P}\subseteq\mathrm{C}_3$

תהא $A\in\mathrm{P}$. אזי קיימת מכונה דטרמיניסטית $M_A$ שמכריעה את $A$ בזמן פולינומי בגודל הקלט.

נבנה מכונה דטרמיניסטית $M$ שהקלט שלה הוא הזוג $(x,r)$:

1. הרץ את $M_A$ על $x$ והחזר את אותה תשובה (התעלם מ-$r$).

ניתוח זמן ריצה. בריצתה על $(x,r)$, $M$ מריצה את $M_A$ על $x$; זמן הריצה פולינומי ב-$|x|$, ובפרט פולינומי ב-$|(x,r)|=|x|+5$.

ניתוח סמנטי. יהי $x$.

• אם $x\in A$: $M_A$ מקבלת את $x$, ולכן $M$ מקבלת את $(x,r)$ עבור כל $r$, ומכאן $\ \Pr_{r\in\{0,1\}^5}\big[M\text{ accepts }(x,r)\big]=1\ge\frac23$.
• אם $x\notin A$: $M_A$ דוחה את $x$, ולכן $M$ דוחה את $(x,r)$ עבור כל $r$, ומכאן $\ \Pr_{r\in\{0,1\}^5}\big[M\text{ rejects }(x,r)\big]=1\ge\frac23$.

לכן $A\in\mathrm{C}_3$. $\square$

משני הכיוונים: $\mathrm{C}_3=\mathrm{P}$. $\blacksquare$

ארבע מלכודות בסעיף הזה, כולן מההקלטה

(1) הממשק — המלכודת המרכזית [01:04:12], [01:05:19]. בכיוון $\mathrm{P}\subseteq\mathrm{C}_3$ מפתה לכתוב "נתבונן ב-$M_A$ עצמה". זה שגוי. "האינטרפייס שלה עם העולם הוא לא האינטרפייס הנכון. אני חייב מכונה שהקלט שלה הוא הזוג" — הגדרת $\mathrm{C}_3$ מדברת על $\Pr_r[M\text{ accepts }(x,r)]$, ולכן $M$ חייבת לקבל $(x,r)$. "הקלט של $M$ צריך להיות $x$ ו-$r$. זה החזות של המחלקה הזאת. על זה לא ליפול."

(2) "יהי $x$" ולא "יהי $(x,r)$" [01:07:32]. בניתוח הסמנטי של הכיוון השני, מה הכמת הראשון? "תשימו לב להגדרה של $\mathrm{C}_3$: כתוב לכל $x$. אז אם אני רוצה להוכיח ש-$A\in\mathrm{C}_3$ אני אתחיל ב'יהי $x$' ולא ב'יהי $x$ ו-$r$'. בסופו של דבר הכול חוזר להגדרה; השאלה היא רק על איזו הגדרה להסתכל."

(3) למה $\alpha>\frac12$ הכרחי [00:42:41]–[00:45:18]. סטודנט שאל אם ל-$\alpha$ יש בכלל משמעות. יש — הוא חייב להיות גדול מחצי, אחרת אין רוב. נניח $\alpha=\frac1{10}$: כל מה שנתון הוא שהתשובה הנכונה חוזרת לפחות ב-$\frac1{10}$ מהמקרים. "היא יכולה להיות עשירית, היא יכולה להיות שלושת רבעי — אני לא יודע. אני לא יודע אם היא יותר מחצי או פחות מחצי." ולכן:

• כלל "קבל אם קיים $r$ אחד שמקבל" אינו עובד בטעות דו-צדדית: גם על $x\notin A$ קיימת הסתברות חיובית ש-$M_A$ תקבל, ואז תיפול על אותו $r$ ותטעה.
• כלל הרוב עובד רק כאשר $\alpha>\frac12$: אז "התשובה הנכונה תחזור על עצמה לפחות שני שלישים מהפעמים, ולכן היא בהכרח תהיה התשובה שחזרה הכי הרבה פעמים."
• הערה מעניינת [00:45:18]: אילו היה נתון ש-ההסתברות שווה בדיוק $\frac1{10}$, אפשר היה לקחת את התשובה שחזרה הכי מעט פעמים — כלומר לעשות flip — ולקבל הסתברות הצלחה $\frac9{10}$. "בשוויון, ה-$1$ פחות נשאר עם שוויון; ב-'גדול שווה' ה-$1$ פחות הופך ל-'קטן שווה'." זה בדיוק המקום שבו כמת $\ge$ הורס את הטיעון.

(4) למה אורך $r$ הקבוע הכרחי, ומה בדיוק הגבול [00:51:24]–[00:52:59]. שאלת סטודנט: מה היה קורה אילו $|r|$ לא היה קבוע?

• אם $|r|=p(|x|)$ פולינומי: מספר האיטרציות הוא $2^{p(|x|)}$ — מעריכי, וההוכחה קורסת. ולא במקרה: זו בדיוק הוכחת $\mathrm{BPP}\subseteq\mathrm{PSPACE}$ משיעור 16, ו-"$\mathrm{P}=\mathrm{BPP}$? זו שאלה פתוחה."
• אם $|r|=c\cdot\log|x|$: אז מספר האיטרציות הוא $2^{c\log|x|}=|x|^c$ — פולינומי. מכפלה של פולינום (מספר איטרציות) בפולינום (זמן לאיטרציה) היא פולינום. ההוכחה עדיין עוברת, ולכן גם עם אורך אקראיות לוגריתמי המחלקה שווה ל-$\mathrm{P}$.

(5) "קבוע הוא פולינום, אז אפשר להגיד מיד $\mathrm{C}_3\subseteq\mathrm{BPP}$?" [00:55:43]–[00:56:44]. כן, ובצדק: $5$ הוא פולינום קבוע, ולכן לפי נוסח ב מתקיים $\mathrm{C}_3\subseteq\mathrm{BPP}$ ישירות מההגדרה. אבל "כל קבוע הוא פולינום; לא כל פולינום הוא קבוע", ולכן ההכלה היא בכיוון אחד בלבד והיא לא הדוקה. "הקבוע נותן לי אקסטרה אינפורמציה, ולכן אני יכול להוכיח משהו יותר חזק" — והמשהו החזק הוא $\mathrm{C}_3=\mathrm{P}$.

(6) קאונטר מפורש מול "רוב" [00:59:31]–[01:01:36]. בשיעור מוקדם יותר בסמסטר, בהוכחה מקבילה, המרצה כתב במפורש מונה והשווה ל-$\frac23\cdot2^{p(|x|)}$; כאן הוא כתב פשוט "החזר את התשובה שחזרה הכי הרבה פעמים". שתי הצורות נכונות. הנימוק להבדל: "אז היה שלב מוקדם יותר בסמסטר ורציתי להדגיש איך אני עושה את זה; שם המספר היה $2^{p(|x|)}$ ורציתי על הדרך להזכיר לכם שאני צריך להיות מסוגל לחשב את $p(|x|)$ בזמן ובמקום. עכשיו אנחנו גדולים יותר ואפשר לעשות את זה טיפה יותר אימפליציטית." הכלל שנשאר: כל פונקציה מספרית שאתם מחשבים בתוך בנייה — ודאו שהיא ישימה בזמן ובמקום, ואמרו את זה כשזה מהותי. כאן זה לא: $16$ הוא קבוע.

תרגיל 3, סעיף (ה): $\mathrm{C}_4=\mathrm{NP}$ — שקולה לטענה פתוחה

סעיף זה נפתר בעל פה [01:10:48]–[01:19:20] ואינו בסיכום.

הטענה שנוכיח. $\mathrm{C}_4=\mathrm{P}$.

כיוון ראשון: $\mathrm{C}_4\subseteq\mathrm{P}$

תהא $A\in\mathrm{C}_4$ עם מכונה דטרמיניסטית פולינומית $M_A$ ופולינום $p$ כבהגדרה 3. יהי $x$, ונסמן $\Omega=\{0,1\}^{p(|x|)},\qquad |\Omega|=2^{p(|x|)},$ ותהי $E\subseteq\Omega$ קבוצת ה-$r$-ים שעליהם $M_A$ טועה — כלומר דוחה את $(x,r)$ כאשר $x\in A$, או מקבלת את $(x,r)$ כאשר $x\notin A$. הקלט $x$ קבוע, ולכן "מקבלת" ו"דוחה" הם מאורעות משלימים באותו מרחב (שיעור 16, ההערה שאחרי הגדרה 3), ולכן בשני המקרים $\Pr_{r\in\Omega}[r\in E]\ \le\ 1-\left(1-\frac{1}{2^{p(|x|)+1}}\right)\ =\ \frac{1}{2^{p(|x|)+1}} .$ לפי משפט 5: $|E|\ =\ \Pr[E]\cdot|\Omega|\ \le\ \frac{1}{2^{p(|x|)+1}}\cdot2^{p(|x|)}\ =\ \frac12 .$ $|E|$ הוא מספר שלם אי-שלילי שקטן או שווה ל-$\frac12$, ולכן $|E|=0$ (מסקנה 5.1). כלומר: $M_A$ צודקת על כל $r\in\Omega$, ללא יוצא מן הכלל.

לכן נבנה מכונה דטרמיניסטית $M$. על קלט $x$:

1. חשב $p(|x|)$ וכתוב $r=0^{p(|x|)}$.
2. הרץ את $M_A$ על $(x,r)$ והחזר את תשובתה.

זמן ריצה. כמו בסעיף (ג): חישוב $p(|x|)$ וכתיבת המחרוזת פולינומיים, והרצת $M_A$ על קלט באורך $|x|+p(|x|)$ פולינומית ב-$|x|$.

ניתוח סמנטי. מהחלק הקודם, $M_A$ צודקת על $(x,r)$ עבור כל $r$, ובפרט עבור $r=0^{p(|x|)}$. לכן $M$ מכריעה את $A$, ומכאן $A\in\mathrm{P}$. $\square$

כיוון שני: $\mathrm{P}\subseteq\mathrm{C}_4$

תהא $A\in\mathrm{P}$ עם מכונה דטרמיניסטית פולינומית $M_A$ שמכריעה אותה. נבחר $p(n)=1$ ונגדיר מכונה $M$ שעל קלט $(x,r)$ מריצה את $M_A$ על $x$ ומחזירה את תשובתה. אז לכל $x$, הסתברות התשובה הנכונה היא $1$, ובוודאי $1\ \ge\ 1-\frac{1}{2^{p(|x|)+1}} .$ לכן $A\in\mathrm{C}_4$. $\square$

מכאן $\mathrm{C}_4=\mathrm{P}$.

ומכאן ההכרעה של הטענה

הטענה "$\mathrm{C}_4=\mathrm{NP}$" שקולה לטענה "$\mathrm{P}=\mathrm{NP}$", שהיא בעיה פתוחה. לכן התשובה בסעיף היא: שקולה לטענה פתוחה. $\blacksquare$

מה זה לא שקול לו [01:19:54]–[01:20:26]. סטודנט הציע שאולי אפשר לקשור את זה ל-$\mathrm{P}=\mathrm{BPP}$. המרצה: "לא. $\mathrm{C}_4$ הוא $\mathrm{P}$ — אין קשר ל-$\mathrm{BPP}$. אתה לא תצליח להראות שזה שקול בלי להראות ש-$\mathrm{P}=\mathrm{BPP}$, ואת זה אני לא יודע." כלומר: ברגע שהראינו $\mathrm{C}_4=\mathrm{P}$, כל שאלה על $\mathrm{C}_4$ מול מחלקה $\mathcal{D}$ מתורגמת לשאלה "$\mathrm{P}=\mathcal{D}$?" — ולכן צריך לבחור את הבעיה הפתוחה הנכונה.

דוגמה: תרגיל הצעצוע שהמרצה הוציא מהחישוב

כדי לבודד את הרעיון של סעיף (ה) מהפרמטרים, המרצה נתן את המקרה הבא [01:14:04]–[01:18:19].

הנתון. תהי $A\subseteq\{1,2,\dots,10\}$ קבוצה שרירותית — לא ידוע עליה דבר, והיא אינה אקראית. נתון שאם דוגמים $x$ אחיד מ-$\{1,\dots,10\}$ אז $\Pr[x\in A]\ \ge\ \tfrac{19}{20}.$