16Randomized Turing Machines: the Formal Model, RP, coRP and BPP

בקצרה

• עד עכשיו האקראיות בקורס הייתה תכונה של אלגוריתם ("נדגום וקטור באקראי"), ולא של מודל חישוב. השיעור הזה סוגר את הפער ומגדיר מכונת טיורינג אקראית באופן פורמלי, בשתי צורות שקולות: אקראיות בתוך המכונה, או מכונה דטרמיניסטית שקוראת סרט אקראי מבחוץ.
• ההבחנה המרכזית של השיעור: מכונה אקראית היא מודל לא דטרמיניסטי (הקלט אינו קובע ביחידות את הפלט), אבל היא אינה מכונה אי-דטרמיניסטית. באי-דטרמיניזם המכונה "בוחרת" ואיננו יודעים איך; באקראיות אנחנו יודעים בדיוק איך — הטלת מטבע הוגן. זה כל ההבדל, והוא מהותי.
• מגדירים משפחת מחלקות אחת, $\mathrm{BPP}(\alpha,\beta)$, שממנה נגזרות שלוש מחלקות בשמות מוכרים: $\mathrm{BPP}=\mathrm{BPP}(\frac23,\frac23)$, $\mathrm{RP}=\mathrm{BPP}(\frac12,1)$, $\mathrm{coRP}=\mathrm{BPP}(1,\frac12)$.
• ההסתברות היא תמיד ורק על מטבעות המכונה, עבור כל קלט קבוע בנפרד. אין כאן שום התפלגות על הקלטים. זו הנקודה שבה נופלים הכי הרבה, ובגללה $\Pr[\text{accept}]$ ו-$\Pr[\text{reject}]$ אינם מאורעות משלימים כשמדובר בקלטים שונים — אבל כן משלימים כשהקלט קבוע.
• מוכיחים שלוש תוצאות: מונוטוניות ההכלה במשפחה $\mathrm{BPP}(\alpha,\beta)$; $\mathrm{RP}\subseteq\mathrm{NP}$ (המחרוזת האקראית משמשת כ-witness); ו-$\mathrm{BPP}\subseteq\mathrm{PSPACE}$ (מריצים את המכונה על כל המחרוזות האקראיות, וסופרים).
• מוכיחים את ההעצמה החד-צדדית: לכל פולינום $q$, $\ \mathrm{RP}=\mathrm{BPP}\!\left(1-\frac{1}{2^{q(n)}},1\right)$ — ולכן בפרט גם $\mathrm{RP}=\mathrm{BPP}\!\left(1-\frac{1}{q(n)},1\right)$. הסף $\frac12$ בהגדרת $\mathrm{RP}$ אינו חלק מהתוכן.
• מסדרים סופית את מה שנשאר פתוח בשיעור 15: בעיית וידוא כפל המטריצות ($\mathrm{MATMUL}$) שייכת ל-$\mathrm{coRP}$, וההוכחה היא בדיוק התאמה בין הערבויות של Freivalds לבין ההגדרה של $\mathrm{BPP}(1,\frac12)$.

רקע ותלויות

מודלים לא דטרמיניסטיים (ראו שיעור 4). מכונת טיורינג אי-דטרמיניסטית היא שישייה $M=(Q,q_{start},F,\Sigma,\Gamma,\delta)$ שבה פונקציית המעברים מחזירה קבוצה של אפשרויות, $\delta(q,\alpha)\subseteq Q\times\Gamma\times\{L,R\}$, כך שממצב וקריאה נתונים ייתכנו כמה צעדים המשך. המכונה מקבלת את $x$ אם קיימת ריצה מקבלת. חשוב לזכור את השישייה כולה, כולל $q_{start}$ — בלעדיו אין בכלל מושג "הריצה של $M$ על $x$".

למת הנרמול הבינארי (ראו שיעור 6, משפט 3). לכל מכונה אי-דטרמיניסטית $N$ קיימת מכונה אי-דטרמיניסטית שקולה $\hat N$ שבה $|\hat\delta(q,\alpha)|\le 2$ לכל $q,\alpha$, וזמן הריצה גדל רק בפקטור קבוע $2|Q||\Gamma|$. המשמעות: אפשר להניח שבכל צעד ההחלטה היא בינארית, ולכן ריצה שלמה מתוארת על ידי ביט אחד לכל צעד. זה בדיוק מה שיאפשר לנו להחליף "בחירה" ב"הטלת מטבע הוגן".

ההגדרה השקולה של $\mathrm{NP}$ (ראו שיעור 6, משפט 4). $A\in\mathrm{NP}$ אם ורק אם קיימים פולינומים $p,q$ ומכונה דטרמיניסטית $M$ כך ש-$\mathrm{time}_M(a)\le p(|a|)$ לכל קלט $a$, ולכל $x$ $x\in A \iff \exists\, w\in\{0,1\}^{q(|x|)}\ \text{ s.t. } M \text{ accepts } (x,w).$ בכיוון ה-yes יש קיום של עד, ובכיוון ה-no יש לכל — כל עד נדחה. השלד הזה הוא בדיוק מה שנחפש כשנוכיח $\mathrm{RP}\subseteq\mathrm{NP}$.

אלגוריתמים אקראיים (ראו שיעור 15). שם ראינו שני אלגוריתמים — בעיית המזכיר ואלגוריתם Freivalds לווידוא כפל מטריצות ($\mathrm{MATMUL}$) — אבל, כדברי המרצה בפתיחה, "לא הגדרנו במדויק את המודל... נתנו אלגוריתם ואמרנו שהוא יכול לדגום באקראי" [00:00:00]–[00:01:34]. נזכיר את הערבות שהוכחה שם ונשתמש בה כלשונה: על קלט $A,B,C$ מסדר $n\times n$, האלגוריתם הדוגם $r\in\{0,1\}^n$ באופן אחיד ובודק אם $A\cdot(B\cdot r)=C\cdot r$ רץ בזמן $O(n^2)$ ומקיים

1. אם $A\cdot B=C$ אז הוא מקבל בהסתברות $1$ (למעשה לכל $r$ בלי יוצא מן הכלל);
2. אם $A\cdot B\ne C$ אז הוא דוחה בהסתברות לפחות $\frac12$.

שיעור 15 ציין שהבעיה "שייכת ל-$\mathrm{coRP}$" ודחה את ההצדקה הפורמלית לכאן; משפט 3 להלן הוא ההצדקה.

הכלים ההסתברותיים. מרחב מדגם סופי עם התפלגות אחידה; מונוטוניות ההסתברות; אי-תלות של מאורעות ($\Pr[\bigcap E_i]=\prod\Pr[E_i]$); והתרגום היסודי שהמרצה חזר עליו במפורש [00:51:42]–[00:54:30]: כשההתפלגות אחידה, הסתברות היא קומבינטוריקה, כלומר "רצוי חלקי הכול", ולכן $|\{\text{good outcomes}\}| \;=\; \Pr[\text{good}]\cdot|\Omega| .$

סגירות הפולינומים. משתמשים בזה לאורך כל הקורס וגם כאן: הפולינומים סגורים לחיבור, לכפל ולהרכבה. לכן אם $|r|$ פולינומי ב-$|x|$ אז $|(x,r)|$ פולינומי ב-$|x|$, ומכונה שרצה בזמן פולינומי באורך הקלט שלה רצה בזמן פולינומי ב-$|x|$. המרצה הדגיש שזו תכונה שהפונקציות המעריכיות אינן מקיימות [01:19:41].

הגדרות

הגדרה 1: מכונת טיורינג אקראית — המודל הפנימי

ניסוח. מכונת טיורינג אקראית היא שישייה $M=(Q,q_{start},F,\Sigma,\Gamma,\delta)$ שבה, בהינתן מצב $q$ ותו נקרא $\alpha$, יש שתי אפשרויות לצעד הבא: $\delta(q,\alpha)=\{(q_1,\beta_1,d_1),\,(q_2,\beta_2,d_2)\},$ והבחירה ביניהן נעשית על ידי הטלת מטבע הוגן — כל אפשרות בהסתברות $\frac12$, בלתי תלוי בכל שאר ההטלות בריצה. אם $|\delta(q,\alpha)|=1$ הצעד דטרמיניסטי לגמרי.

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

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

האזהרה המרכזית של השיעור [00:05:05]–[00:06:43]. יש להבחין בין שני מונחים שקל לבלבל ביניהם:

• מודל לא דטרמיניסטי (non-deterministic במובן הרחב) הוא כל מודל שבו הקלט אינו קובע ביחידות את הפלט. מכונה אי-דטרמיניסטית היא כזו; מכונה אקראית היא כזו.
• מודל אי-דטרמיניסטי (nondeterministic במובן הצר של שיעור 4) הוא מודל ספציפי שבו המכונה "מחליטה" ואין לנו שום תיאור של איך.

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

מופע. האלגוריתם של Freivalds משיעור 15, כשמממשים אותו כמכונה: בכל אחד מ-$n$ הצעדים שבהם נבחרת קואורדינטה של הווקטור $r$, המכונה מטילה מטבע.

אי-מופע. המכונה האי-דטרמיניסטית של שיעור 6 שמכריעה את $\mathrm{SAT}$ על ידי ניחוש השמה אינה מכונה אקראית — לא כי המבנה שלה שונה, אלא כי המשמעות שאנחנו נותנים ל-$\delta$ רב-ערכי שונה. אם נקרא אותה כמכונה אקראית, היא כבר לא מכריעה את $\mathrm{SAT}$: על נוסחה ספיקה עם השמה מספקת יחידה מתוך $2^n$, ההסתברות שהיא תקבל היא $2^{-n}$ ולא $1$.

הגדרה 2: מכונת טיורינג אקראית — מודל הסרט האקראי

ניסוח. מכונת טיורינג אקראית היא מכונה דו-סרטית $M$ שבה:

• סרט $1$ הוא סרט עבודה רגיל (עליו מגיע הקלט, ועליו המכונה קוראת וכותבת חופשית);
• סרט $2$ מכיל מחרוזת אינסופית של ביטים; המכונה יכולה רק לקרוא ממנו, ולא לכתוב, והראש עליו זז רק ימינה;
• סרט $2$ נקרא הסרט האקראי.

המכונה עצמה דטרמיניסטית לחלוטין: ברגע שקבענו את $x$ ואת תוכן הסרט האקראי, כל הריצה נקבעת.

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

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

הצורה שנשתמש בה. אם המכונה רצה בזמן פולינומי, היא קוראת לכל היותר פולינום ביטים מהסרט האקראי (קריאת ביט עולה צעד). לכן נסמן: קיים פולינום $p$ כך שבריצה על $x$ המכונה קוראת לכל היותר $p(|x|)$ ביטים, נסמן אותם $r\in\{0,1\}^{p(|x|)}$, ונכתוב $M(x,r)$. שאר הביטים על הסרט אינם משפיעים כלל, ולכן אפשר להגריל רק את $p(|x|)$ הראשונים [00:27:17].

מתי משתמשים בכל מודל — זו נקודת המפתח של השיעור.

• מודל 1 (אקראיות בפנים) נוח כשרוצים להציג אלגוריתם ולהראות תוצאה חיובית. "זה מודל שיותר נוח לתכנת בו, פשוט ככה" [00:10:57].
• מודל 2 (סרט אקראי, מכונה דטרמיניסטית) נוח כשרוצים לדבר על קשר בין מחלקות — למשל להראות שמחלקה אקראית מוכלת במחלקה דטרמיניסטית. "תמיד נוח לי לעבוד עם מכונות דטרמיניסטיות... המעברים הרבה יותר קלים כשהמכונה היא מראש דטרמיניסטית" [00:11:28]–[00:13:07].

בקורס לא מוכיחים את שקילות שני המודלים [00:10:26]; היא מונחת. אנחנו נשתמש בכל אחד מהם היכן שנוח, בדיוק כפי שנעשה בשיעור עם $\mathrm{NP}$ מול $\mathrm{NP}'$ (ראו שיעור 6) — וזו הייתה ההקבלה המפורשת שהמרצה בנה עליה את כל המבנה [00:02:22]–[00:02:55].

הגדרה 3: משפחת המחלקות $\mathrm{BPP}(\alpha,\beta)$

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

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

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

מרחב ההסתברות — לקרוא לאט. בנוסח א האקראיות היא המטבעות שהמכונה מטילה; בנוסח ב היא המחרוזת $r$, הנדגמת אחידה מתוך $\{0,1\}^{p(|x|)}$. בשני המקרים:

$\Omega \;=\; \Omega(x) \;=\; \{0,1\}^{p(|x|)}, \qquad |\Omega|=2^{p(|x|)} .$

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

המסקנה החשובה מכך (שאלת סטודנטית, [00:21:01] ו-[00:29:23]). אסור לחשוב על "$x\in A$" ועל "$x\notin A$" כעל מאורעות משלימים, ואסור לצפות ש-$\alpha+\beta$ יסתכם ל-$1$. אלה שני תרחישים שונים לגמרי, עם שני קלטים שונים, ולכן עם שני מרחבי מדגם שונים — ואם $p(|x_1|)\ne p(|x_2|)$ אז אפילו גודל מרחב המדגם שונה. אבל — וזה הצד השני של אותו מטבע — ברגע שקיבענו $x$ אחד, המאורעות "$M$ מקבלת את $(x,r)$" ו-"$M$ דוחה את $(x,r)$" הם כן מאורעות משלימים באותו מרחב, כי המכונה דטרמיניסטית ועוצרת, ולכן $\Pr_r\big[M \text{ accepts } (x,r)\big] \;=\; 1-\Pr_r\big[M \text{ rejects } (x,r)\big].$ בהוכחת משפט 4 נשתמש בעובדה הזו במפורש, ובדיוק שם היא נחוצה [01:23:54]–[01:24:56].

איך לזכור את ההגדרה. "אני תמיד בודק מה ההסתברות שהמכונה צודקת, ואני רוצה לחסום אותה מלמטה" [00:28:51]. על yes-instance להיות צודק פירושו לקבל; על no-instance פירושו לדחות. לכן שני התנאים נראים שונים אך אומרים אותו דבר.

מופע. $A=\emptyset$ שייכת ל-$\mathrm{BPP}(\alpha,1)$ לכל $\alpha$: המכונה "דחה תמיד" עונה על התנאי השני בשוויון $1$, והתנאי הראשון ריק.

אי-מופע מאלף. $\mathrm{BPP}(\frac12,\frac12)$ מכילה כל שפה: המכונה שמטילה מטבע אחד ומקבלת על "עץ" מקיימת את שני התנאים בשוויון עבור כל $A$, בלי להסתכל בכלל בקלט. כלומר סף של בדיוק $\frac12$ בשני הצדדים הוא חסר תוכן לחלוטין. באותו אופן $\mathrm{BPP}(0,1)$ מכילה כל שפה (המכונה "דחה תמיד"), ו-$\mathrm{BPP}(1,0)$ מכילה כל שפה (המכונה "קבל תמיד"). לכן הערכים בסוגריים אינם קישוט: הם כל התוכן.

הגדרה 4: המחלקות בשמותיהן, והסף המדויק בכל אחת

$\boxed{\ \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)\ }$

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

$\mathrm{BPP}$ — טעות דו-צדדית (bounded-error probabilistic polynomial time). קיימת מכונה אקראית פולינומית $M$ כך שלכל $x$: אם $x\in A$ אז $\Pr[\text{accept}]\ge\frac23$, ואם $x\notin A$ אז $\Pr[\text{reject}]\ge\frac23$. הטעות אפשרית משני הכיוונים, ולכן שום תשובה יחידה של המכונה אינה אמינה במאת האחוזים. הפירוש של השם, כפי שהמרצה שחזר אותו בכיתה [00:42:01]: ה-$\mathrm{P}$ הראשונה — probabilistic, השנייה — polynomial, וה-$\mathrm{B}$ — bounded, כי הסתברות הטעות חסומה משני הכיוונים.

למה $\frac23$? משום שכל קבוע בין $\frac12$ ל-$1$ נותן את אותה מחלקה בדיוק — זה בדיוק תוכנו של שיעור 17 — ולכן בוחרים ערך נוח לכתיבה. מה נשבר בערך אחר? אם מורידים ל-$\frac12$ בדיוק מקבלים את המחלקה חסרת התוכן שראינו לעיל, שמכילה כל שפה. אם מעלים ל-$1$ מקבלים את $\mathrm{P}$ (מכונה שצודקת בהסתברות $1$ על מרחב מדגם סופי צודקת לכל $r$, ואפשר להריץ אותה עם $r=0^{p(|x|)}$). ואם מסתפקים בפער אקספוננציאלית קטן, $\frac12+\frac{1}{2^{q(n)}}$, לא ידוע שההעצמה עובדת.

$\mathrm{RP}$ — טעות חד-צדדית, הצד ה"בטוח" הוא ה-no. קיימת מכונה אקראית פולינומית $M$ כך שלכל $x$: אם $x\in A$ אז $\Pr[\text{accept}]\ge\frac12$; ואם $x\notin A$ אז $\Pr[\text{reject}]\ge 1$, כלומר שווה $1$, כלומר לכל $r$ בלי יוצא מן הכלל המכונה דוחה. במילים: אין תשובות "כן" שגויות. אם המכונה אמרה "כן" — $x\in A$ בוודאות; אם אמרה "לא" — ייתכן שהיא טועה, בהסתברות עד $\frac12$.

למה $\frac12$? אותה סיבה — משפט 5 להלן מראה שאפשר להעלות עד $1-\frac{1}{2^{q(n)}}$, ושיעור 17 מראה שאפשר גם להתחיל מ-$\frac{1}{q(n)}$ זעיר. מה נשבר בערך אחר? $\alpha=0$ הורס הכול: $\mathrm{BPP}(0,1)$ מכילה כל שפה. לעומת זאת אסור לוותר על ה-$1$ בצד ה-no — זה מה שהופך את המחלקה לחד-צדדית, וזה מה שמאפשר את כל ההעצמות הפשוטות.

$\mathrm{coRP}$ — טעות חד-צדדית, הצד ה"בטוח" הוא ה-yes. לכל $x$: אם $x\in A$ אז $\Pr[\text{accept}]=1$; אם $x\notin A$ אז $\Pr[\text{reject}]\ge\frac12$. אין תשובות "לא" שגויות. שקול לכך ש-$\overline{A}\in\mathrm{RP}$, ומכאן השם.

אזהרה על השם "co" [00:42:34]–[00:43:40]. $\mathrm{coRP}$ אינה המשלימה של $\mathrm{RP}$ כקבוצת שפות; היא קבוצת המשלימות של שפות ב-$\mathrm{RP}$. שתי המחלקות אינן זרות (כל שפה ב-$\mathrm{P}$ שייכת לשתיהן) ואינן ממצות את הכול. סטודנט ביקש דוגמה לשפה שבוודאות אינה ב-$\mathrm{RP}$, והתשובה: בעיית העצירה — כי כל המחלקות שאנחנו מסתכלים עליהן כאן מורכבות משפות כריעות, ובעיית העצירה אינה כריעה.

למה דווקא ה-yes קיבל את הצד ה"לא ודאי" ב-$\mathrm{RP}$? [00:58:48]–[01:00:24]. סטודנט שאל, והמרצה נתן תשובה מבנית: זו אותה חוסר-סימטריה שכבר הייתה ב-$\mathrm{NP}$. שם $x\in A$ פירושו קיים עד, ו-$x\notin A$ פירושו שלכל עד המכונה דוחה. הבעיות הקומבינטוריות "המעניינות" מנוסחות היסטורית עם קיום (קיימת השמה מספקת, קיימת קליקה בגודל $k$), ולכן המחלקות נבנו סביב הצורה הזו, ו-$\mathrm{RP}$ ירשה את המבנה. משפט 2 להלן מראה שההקבלה אינה רק אסתטית — היא הוכחה.

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

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

ניסוח. יהיו $\alpha,\beta,\hat\alpha,\hat\beta\in[0,1]$ ונניח $\hat\alpha\ge\alpha$ וגם $\hat\beta\ge\beta$. אזי $\mathrm{BPP}(\hat\alpha,\hat\beta)\ \subseteq\ \mathrm{BPP}(\alpha,\beta).$

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

איך לזכור את כיוון ההכלה [01:34:25]. המרצה הדגיש שהוא לעולם אינו זוכר בעל פה מי מוכל במי, אלא שואל: לאן קשה יותר להיכנס? דרישת הצלחה גדולה יותר היא דרישה חמורה יותר, ולכן היא מגדירה מחלקה מצומצמת יותר, שמוכלת במחלקה עם הדרישה הרפויה. זה בדיוק מה שמאפשר לקבל "חינם" את הכיוון הקל בכל אחת משתי טענות ההעצמה.

שימוש מיידי. $\mathrm{RP}=\mathrm{BPP}(\frac12,1)\subseteq\mathrm{BPP}(\frac12,\frac12)$ ו-$\mathrm{coRP}\subseteq\mathrm{BPP}(\frac12,\frac12)$ — אך זו הכלה חסרת ערך, כי אגף ימין הוא כל השפות. לעומת זאת $\mathrm{RP}\subseteq\mathrm{BPP}(\frac12,\frac23)$ אינה נובעת מהמשפט (הכיוון הפוך), ואכן היא אינה טענה טריוויאלית.

משפט 2: $\mathrm{RP}\subseteq\mathrm{NP}$

ניסוח. כל שפה ב-$\mathrm{RP}$ שייכת ל-$\mathrm{NP}$.

מדוע ההוכחה בנויה כך. אנחנו רוצים לסיים עם השלד של $\mathrm{NP}'$ (שיעור 6): מכונה דטרמיניסטית שמקבלת זוג $(x,w)$, כמת קיום בכיוון אחד וכמת "לכל" בכיוון השני. לכן כדאי להתחיל כבר עם נוסח ב של הגדרה 3 — המכונה שם דטרמיניסטית ומקבלת זוג $(x,r)$, כלומר בדיוק אותו ממשק. "לעבור מאקראית לאי-דטרמיניסטית — אני לא בטוח; אבל אם אני עובד עם מכונה דטרמיניסטית פה ומכונה דטרמיניסטית שם, לפחות את המכונות אני יודע איך להתאים" [00:45:10]–[00:45:42]. זה לקח מתודי כללי בשיעור: בוחרים את הנוסח לפי הממשק שאליו רוצים להגיע.

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

נתבונן ב-$M$; היא כבר מכונה דטרמיניסטית פולינומית המקבלת זוג, ולא נבנה מכונה חדשה. יהי $x$ קלט.

מקרה $x\in A$. מרחב המדגם $\{0,1\}^{p(|x|)}$ סופי והתפלגותו אחידה, ולכן הסתברות היא "רצוי חלקי הכול". נבודד את המונה: $\Big|\big\{r\in\{0,1\}^{p(|x|)}\ :\ M \text{ accepts } (x,r)\big\}\Big| \;=\; \Pr_r\big[M \text{ accepts } (x,r)\big]\cdot 2^{p(|x|)} \;\ge\; \tfrac12\cdot 2^{p(|x|)} \;=\; 2^{\,p(|x|)-1} \;\ge\; 1 .$ המעבר האחרון דורש $p(|x|)\ge 1$. זה מתקיים לכל $x$ ארוך מספיק, שכן $p$ פולינום שאינו זהותית אפס ולכן שואף לאינסוף; ומספר הקלטים $x$ שעבורם $p(|x|)<1$ הוא סופי, ואפשר לצרוב את התשובות עליהם בטבלה בתוך המכונה [00:57:44]–[00:58:16]. לכן קיים $r$ שעבורו $M$ מקבלת את $(x,r)$.

מקרה $x\notin A$. הסתברות הדחייה היא $1$, ומכיוון שמרחב המדגם סופי ואחיד פירוש הדבר שהמאורע הוא כל המרחב: $\Big|\big\{r\in\{0,1\}^{p(|x|)}\ :\ M \text{ rejects } (x,r)\big\}\Big| \;=\; 2^{p(|x|)},$ כלומר לכל $r\in\{0,1\}^{p(|x|)}$ המכונה $M$ דוחה את $(x,r)$.

חיברנו: קיימת מכונה דטרמיניסטית $M$ הרצה בזמן פולינומי, וקיים פולינום $p$, כך שלכל $x$ $x\in A \iff \exists\, r\in\{0,1\}^{p(|x|)}\ \text{ s.t. } M \text{ accepts } (x,r),$ וזו בדיוק ההגדרה של $\mathrm{NP}'$ (שיעור 6, הגדרה 1), שהיא לפי משפט 4 שם שקולה ל-$\mathrm{NP}$. לכן $A\in\mathrm{NP}$. $\blacksquare$

הערה: בהרצאה זה נאמר בקיצור — "לכן קיים $r$" — והמרצה עצר במכוון וביקש לעבור דרך שלב הספירה [00:50:59]–[00:54:30], כדי להדגיש שההסתברות מתורגמת לקומבינטוריקה. גם הטיפול ב-$x$-ים הקצרים נאמר רק בעל פה בתשובה לשאלה; הפירוט כאן.

מה תופס את מקומו של מה. המרצה שאל את הכיתה ישירות [00:55:00]: "ה-$r$ הזה תופס את התפקיד של מי?" התשובה — של ה-witness. המחרוזת האקראית ב-$\mathrm{RP}$ היא בדיוק העד ב-$\mathrm{NP}$: היא מגיעה מבחוץ, אורכה פולינומי, והמכונה רק מאמתת בעזרתה. ההבדל היחיד הוא שב-$\mathrm{NP}$ די בכך שקיים עד אחד, ואילו ב-$\mathrm{RP}$ נדרש שלפחות מחצית מהמחרוזות יהיו עדים. זו דרישה חזקה יותר, ולכן ההכלה היא בכיוון הזה ולא בהפוך.

מסקנה 2.1. $\ \mathrm{coRP}\subseteq\mathrm{coNP}$. אכן, $A\in\mathrm{coRP}$ פירושו $\overline{A}\in\mathrm{RP}\subseteq\mathrm{NP}$, ולכן $A\in\mathrm{coNP}$ לפי ההגדרה של $\mathrm{coNP}$.

משפט 3: $\mathrm{MATMUL}\in\mathrm{coRP}$

ניסוח. תהא $\mathrm{MATMUL}=\big\{\langle A,B,C\rangle\ :\ A,B,C \text{ are } n\times n \text{ matrices and } A\cdot B=C\big\}.$ אזי $\mathrm{MATMUL}\in\mathrm{coRP}$.

הוכחה. לפי הגדרה 4, $\mathrm{coRP}=\mathrm{BPP}(1,\frac12)$, ולכן צריך מכונה אקראית פולינומית שמקבלת כל yes-instance בהסתברות $1$ ודוחה כל no-instance בהסתברות לפחות $\frac12$.

ניקח את אלגוריתם Freivalds של שיעור 15 ונכתוב אותו בנוסח ב. תהא $M$ המכונה הדטרמיניסטית שעל קלט $\langle A,B,C\rangle$ ומחרוזת אקראית $r$:

1. קוראת $n$ ביטים מהמחרוזת האקראית ומפרשת אותם כווקטור $r\in\{0,1\}^n$;
2. מחשבת $A\cdot(B\cdot r)$ ואת $C\cdot r$;
3. מקבלת אם שני הווקטורים שווים, ודוחה אחרת.

הפולינום של הביטים. $p(|x|)=n$. הקלט $x=\langle A,B,C\rangle$ מקודד $3n^2$ ערכים, ולכן $n\le|x|$, ובפרט $p$ פולינום ב-$|x|$ כנדרש.

זמן הריצה. שיעור 15, משפט 3: $O(n^2)$ פעולות אריתמטיות, ולכן פולינומי ב-$|x|$.

תנאי ה-yes ($\alpha=1$). אם $\langle A,B,C\rangle\in\mathrm{MATMUL}$, כלומר $A\cdot B=C$, אז לפי האסוציאטיביות לכל $r$ בלי יוצא מן הכלל $A\cdot(B\cdot r)=(A\cdot B)\cdot r=C\cdot r$, ולכן $M$ מקבלת. המאורע הוא כל מרחב המדגם, ולכן $\Pr_r[M \text{ accepts } (x,r)]=1\ge\alpha=1$.

תנאי ה-no ($\beta=\frac12$). אם $A\cdot B\ne C$, שיעור 15 משפט 3 נותן $\Pr_r[M \text{ accepts } (x,r)]\le\frac12$. מכיוון שהקלט $x$ קבוע, המאורעות "מקבלת" ו"דוחה" משלימים באותו מרחב מדגם, ולכן $\Pr_r\big[M \text{ rejects } (x,r)\big] \;=\; 1-\Pr_r\big[M \text{ accepts } (x,r)\big] \;\ge\; 1-\tfrac12 \;=\; \tfrac12 \;=\;\beta .$ שני התנאים מתקיימים, ולכן $\mathrm{MATMUL}\in\mathrm{BPP}(1,\frac12)=\mathrm{coRP}$. $\blacksquare$

הערה: בהקלטה [00:41:30] המרצה רק שאל את הכיתה "כפל מטריצות — לאן היא שייכת?", קיבל את התשובה "$\mathrm{coRP}$", ונימק במשפט: "אם היה yes-instance תמיד החזרתי כן, ואם לא — האלגוריתם צדק בהסתברות לפחות חצי". ההתאמה המלאה לנוסח ב, כולל חשבון הביטים ומעבר המשלים, היא הפירוט כאן.

למה זה $\mathrm{coRP}$ ולא $\mathrm{RP}$ — מלכודת. התשובה תלויה בשאלה איך ניסחנו את השפה. אם היינו מגדירים את השפה כ-$\{\langle A,B,C\rangle : A\cdot B\ne C\}$ היינו מקבלים $\mathrm{RP}$. הכיוון שבו יש ודאות הוא הכיוון שבו האלגוריתם לא יכול לטעות, וזה תמיד הכיוון שבו הזהות מתקיימת פוינטווייז.

משפט 4: $\mathrm{BPP}\subseteq\mathrm{PSPACE}$

ניסוח. כל שפה ב-$\mathrm{BPP}$ מוכרעת על ידי מכונה דטרמיניסטית במקום פולינומי.

מדוע ההוכחה בנויה כך. כדי להוכיח שייכות ל-$\mathrm{PSPACE}$ צריך מכונה דטרמיניסטית שמכריעה את השפה במקום פולינומי — הכרעה רגילה, כמו בחישוביות [01:08:44]. הממשק של מכונה כזו מקבל רק את $x$. לכן שוב מתחילים מנוסח ב, אבל כאן יש קושי נוסף: המכונה שבידינו מקבלת זוג $(x,r)$ והמכונה שנבנה תקבל רק $x$. סטודנט הציע לשרשר, $x$ ואחריו $r$ — והמרצה פסל מיד [01:06:38]: "הקלט שקיבלתי הוא הקלט שאני צריך לבדוק אם הוא שייך; אני לא יכול לשרשר לו שום דבר". הפתרון היחיד הוא לא להגריל את $r$ בכלל, אלא לעבור על כולם.

ההוכחה. תהא $A\in\mathrm{BPP}=\mathrm{BPP}(\frac23,\frac23)$. לפי נוסח ב קיימת מכונה דטרמיניסטית $M$ הרצה בזמן פולינומי בגודל הקלט וקיים פולינום $p$ כך שלכל $x$: