4מכונות טיורינג אי-דטרמיניסטיות

בקצרה

• מוסיפים למודל שינוי תחבירי אחד בלבד: פונקציית המעברים מחזירה כעת קבוצה של שלשות במקום שלשה יחידה, כלומר $\delta:Q\times\Gamma\to P(Q\times\Gamma\times\{L,R\})$. כל שאר רכיבי המכונה נשארים כשהיו.
• השינוי התחבירי הקטן הזה הורס את המושג המרכזי של המודל הקודם: אין יותר "הריצה של $M$ על $x$", יש אוסף הריצות האפשריות של $M$ על $x$. כל הסמנטיקה של השיעור נובעת מכך.
• תנאי ההכרעה אינו סימטרי, וזו הנקודה שהכי כדאי לזכור: $M$ מכריעה את $A$ באופן אי-דטרמיניסטי אם (א) בכל ריצה אפשרית ועל כל קלט היא עוצרת, (ב) אם $x\in A$ אז קיימת ריצה מקבלת, (ג) אם $x\notin A$ אז בכל ריצה היא דוחה. קבלה היא טענת קיום; דחייה ועצירה הן טענות "לכל".
• מדדי היעילות הם מקסימום על פני הריצות: $\mathrm{time}_M(x)$ נמדד בריצה אפשרית ארוכה ביותר, ו-$\mathrm{space}_M(x)$ בריצה אפשרית שכותבת בהכי הרבה תאים — ולא בהכרח באותה ריצה.
• כל הטענות מהמודל הדטרמיניסטי עוברות כמות שהן, וההוכחות משתנות רק ב"מעטפת": קודם "תהא ריצה אפשרית", מוכיחים לגביה, ואז לוקחים מקסימום. המהות של כל הטיעונים — ספירת קונפיגורציות, "בכל צעד כותבים לכל היותר בתא חדש אחד" — לא זזה.
• מקבלים את המחלקות $\mathrm{NTime}(f)$, $\mathrm{NSpace}(f)$ ומעליהן $\mathrm{NP}$, $\mathrm{NEXP}$, $NPSPACE$, $NEXPSPACE$, ואת ההכלה הקלה $P\subseteq \mathrm{NP}$ — שנובעת מכך שכל מכונה דטרמיניסטית היא מכונה אי-דטרמיניסטית שכל הקבוצות שלה יחידונים.
• המודל אינו מגדיל את כוח החישוב (מבחינת חישוביות הוא שקול למכונת טיורינג רגילה), אבל הוא עשוי לשנות מהותית את היעילות — וכאן נולדת שאלת $P$ מול $\mathrm{NP}$.
• אם אתם צריכים רק דבר אחד מהשיעור הזה: המילים "באופן אי-דטרמיניסטי" אינן קישוט. הן מסמנות שיש עוד כמת שצריך לטפל בו בכל הוכחה.

רקע ותלויות

השיעור נשען על שיעורים 1–3, ובעיקר על ההגדרות. נחזור על מה שנשתמש בו ממש.

מהשיעור 1: מכונת טיורינג דטרמיניסטית

מכונת טיורינג (חד-סרטית, סטנדרטית) היא

כאשר $Q$ קבוצת המצבים הסופית, $q_{start}\in Q$ המצב ההתחלתי, $F\subseteq Q$ קבוצת המצבים הסופיים (במכונת הכרעה $F=\{q_{accept},q_{reject}\}$), $\Sigma$ א"ב הקלט, $\Gamma\supseteq\Sigma$ א"ב העבודה הכולל את התו הריק $B$.

תיקון לסיכום. בעמוד 1 בסיכום נכתב $M=(Q,F,\Sigma,\Gamma,\delta)$ — חמישייה שאין בה מצב התחלתי. בלי $q_{start}$ אי אפשר בכלל לדבר על "הריצה של $M$ על $x$", ולכן הוספנו אותו. זו אותה השמטה שכבר תוקנה בשיעור 1 (ראו שיעור 1). בהקלטה המקבילה המרצה מנה את הרכיבים ככה: מצב התחלתי, מצב מקבל, מצב דוחה, א"ב, ופונקציית המעברים — כלומר בדיוק אותה הגדרה, בפירוק אחר של $F$ [ב׳ 00:26:23].

מהשיעור 1: מדדי הזמן והמקום

לכל מכונה $M$ וקלט $x\in\Sigma_M^*$:

• $\mathrm{time}_M(x)$ — מספר ההפעלות של פונקציית המעברים בריצת $M$ על $x$;
• $\mathrm{space}_M(x)$ — מספר התאים השונים שבהם $M$ כותבת במהלך הריצה.

שתי ההגדרות האלה מניחות שיש ריצה אחת. בדיוק זו ההנחה שתישבר היום.

מהשיעור 2: המחלקות ושתי טענות שנשתמש בהן

ובאותו אופן $\mathrm{DSpace}(f)$ עם $\mathrm{space}$. מעליהן המחלקות הגסות $P=\bigcup_{c\ge1}\mathrm{DTime}(n^c)$, $\mathrm{EXP}=\bigcup_{c\ge1}\mathrm{DTime}(2^{n^c})$, $\mathrm{PSPACE}=\bigcup_{c\ge1}\mathrm{DSpace}(n^c)$.

שתי התוצאות שנשכפל היום:

טענה (מקום חסום בזמן). לכל $M$ ולכל $x$: $\mathrm{space}_M(x)\le \mathrm{time}_M(x)$. הנימוק: בכל צעד המכונה כותבת בתא אחד לכל היותר, ותא חדש נספר פעם אחת.

טענה (זמן חסום אקספוננציאלית במקום). לכל $M$ קיים $c>0$ כך שאם $M$ עוצרת על $x$ אז $\mathrm{time}_M(x)\le 2^{\,c\cdot\mathrm{space}_M(x)}$, עם $c=\lg|Q|+\lg|\Gamma|+1$.

ההוכחה של השנייה עברה דרך ספירת קונפיגורציות: מספר הקונפיגורציות של $M$ שמשתמשות ב-$s$ תאים הוא $|Q|\cdot|\Gamma|^{s}\cdot s\le 2^{(\lg|Q|+\lg|\Gamma|+1)\cdot s}$, ומכונה שעושה יותר צעדים מזה חוזרת על קונפיגורציה ולכן אינה עוצרת. החישוב הזה לא ישתנה היום — רק העטיפה סביבו (ראו שיעור 2).

מהשיעור 3: משפטי ההיררכיה

$\mathrm{DSpace}(g)\subsetneq\mathrm{DSpace}(f)$ כאשר $g=o(f)$ ו-$f$ ישימה במקום וסופר-לינארית; ובזמן, באותם תנאים, $\mathrm{DTime}(g)\subsetneq\mathrm{DTime}(f^2)$. נשתמש בהם בתרגיל החימום שנפתח בו את סעיף הדוגמאות (ראו שיעור 3).

למה בכלל מודל כזה

השאלה הזאת לא מופיעה בסיכום, אך היא נאמרה במפורש בהקלטה המקבילה [ב׳ 00:24:19]: המחלקה $P$ נתפסת כ"מה שאפשר לפתור ביעילות", ויש המון בעיות חשובות שלא יודעים להראות עליהן שהן ב-$P$. מסתבר שברגע שמרשים למודל להיות אי-דטרמיניסטי, הרבה מאוד מהן פתאום נפתרות בזמן פולינומי. המודל האי-דטרמיניסטי הוא מודל תיאורטי לחלוטין — אף אחד לא בונה מכונה כזאת — אבל הוא בדיוק הכלי שמאפשר לנסח את השאלה "האם הבעיות האלה קשות באמת".

הגדרות

הגדרה 1: מכונת טיורינג אי-דטרמיניסטית

מכונת טיורינג אי-דטרמיניסטית היא בדיוק כמו מכונת טיורינג, פרט לפונקציית המעברים:

כאשר $P(\cdot)$ היא קבוצת החזקה. כלומר לכל $q\in Q$ ולכל $\alpha\in\Gamma$: בחישוב דטרמיניסטי $\delta(q,\alpha)$ הוא שלשה אחת, ובחישוב אי-דטרמיניסטי $\delta(q,\alpha)$ הוא קבוצה של שלשות.

אינטואיציה. במצב $q$ כשהראש קורא $\alpha$, המכונה מסתכלת בקבוצה $\delta(q,\alpha)$ ו"בוחרת" ממנה שלשה אחת ופועלת לפיה. איך היא בוחרת? אין תשובה — זה לא חלק מהמודל, ואין פה שום מנגנון פיזיקלי [ב׳ 00:28:25]. המודל רק אומר שכל בחירה כזו היא מהלך לגיטימי.

דוגמה. $\delta(q_1,1)=\{(q_1,1,R),(q_2,1,R)\}$ — שתי אפשרויות: להישאר ב-$q_1$ או לעבור ל-$q_2$, בשני המקרים לכתוב $1$ ולזוז ימינה.

אי-דוגמה. $\delta(q_1,1)=\varnothing$ היא לגיטימית לגמרי בהגדרה (הקבוצה הריקה היא איבר של קבוצת החזקה), אבל היא לא מתארת "מעבר לדחייה" — היא מתארת מצב שאין ממנו המשך. בקורס הזה נעבוד עם הקונבנציה של הסיכום: תא ריק בטבלה או חץ חסר בסרטוט פירושם מעבר ל-$q_{reject}$ [א׳ 00:15:12], [א׳ 00:41:28].

קונבנציית כתיבה. בטבלת המעברים כותבים בתאים $q_{reject}$ או $q_{accept}$ בקיצור, במקום השלשה המלאה $\{(q_{reject},\alpha,R)\}$. גם כשכותבים בתא שלשה יחידה בלי סוגריים מסולסלים — זו עדיין קבוצה בת איבר אחד [א׳ 00:14:42].

הגדרה 2: "לא דטרמיניסטי" מול "אי-דטרמיניסטי"

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

• חישוב דטרמיניסטי: תוצאת הריצה של האלגוריתם/המכונה היא פונקציה של הקלט בלבד. (המרצה עמד על הניסוח "פונקציה של הקלט" ולא "תלויה בקלט" — זה הניסוח המתמטי [א׳ 00:08:49].) שימו לב שמדובר ב"תוצאת ריצה" ולא ב"פלט", כי ייתכן שאין פלט — המכונה עלולה לא לעצור.
• not deterministic (בעברית: לא דטרמיניסטי) — כל מודל שבו תוצאת החישוב עשויה להיות תלויה בגורמים נוספים מעבר לקלט.
• non deterministic (בעברית: אי-דטרמיניסטי) — המודל הספציפי שבו בכל צעד בחישוב יכולות להיות מספר אפשרויות למעבר הבא.

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

הגדרה 3: ריצה אפשרית

בהינתן מכונה אי-דטרמיניסטית $M$ וקלט $x\in\Sigma_M^*$, ריצה אפשרית של $M$ על $x$ היא סדרה של שלשות מתוך $Q_M\times\Gamma_M\times\{L,R\}$ ה"מצייתת" לפונקציית המעברים: כל שלשה בסדרה שייכת לקבוצה שפונקציית המעברים מחזירה בצעד המתאים.

באופן מדויק: אם לפני הצעד ה-$i$ המכונה נמצאת במצב $q$ (המצב שברכיב הראשון של השלשה ה-$(i-1)$, ובצעד הראשון $q_{start}$) והראש קורא את התו $\alpha$ שנמצא כרגע בתא שמתחתיו, אז השלשה ה-$i$ חייבת להיות איבר של $\delta(q,\alpha)$. הסדרה עשויה להיות סופית — ואז היא מסתיימת במצב סופי — או אינסופית.

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

מינוח נוסף (מההקלטה המקבילה). סדרת הבחירות שהמכונה עושה במהלך הריצה נקראת תסריט ריצה, וכל תסריט ריצה מתאר ריצה אפשרית אחת [ב׳ 00:31:07]. זה שם נוח לחשוב איתו: הקלט קובע מה המכונה רואה, והתסריט קובע מה היא בוחרת.

ההבדל הסמנטי המרכזי. במודל הדטרמיניסטי, בהינתן $M$ ו-$x$, יכולתי לדבר על הריצה של $M$ על $x$ — ביידוע. עכשיו אני יכול לדבר רק על אוסף הריצות האפשריות של $M$ על $x$. זה כל ההבדל, וממנו נובע כל השאר [א׳ 00:25:29].

נקודה עדינה. חלק מהריצות האפשריות עוצרות וחלק לא — על אותו קלט עצמו. נראה את זה מיד בדוגמה 1.

הגדרה 4: הכרעה באופן אי-דטרמיניסטי

תהא $A$ שפה ותהא $M$ מכונה אי-דטרמיניסטית מעל אותו א"ב, $\Sigma_M=\Sigma_A$. נאמר כי $M$ מכריעה את $A$ באופן אי-דטרמיניסטי כאשר:

1. לכל $x\in\Sigma_M^*$ ובכל ריצה אפשרית של $M$ על $x$ — $M$ עוצרת;
2. לכל $x\in\Sigma_M^*$: אם $x\in A$ אז קיימת ריצה אפשרית של $M$ על $x$ המסתיימת במצב מקבל;
3. לכל $x\in\Sigma_M^*$: אם $x\notin A$ אז בכל ריצה אפשרית של $M$ על $x$ — $M$ דוחה.

ניסוח שקול. בהינתן תנאי 1, אפשר לאחד את 2 ו-3 לכדי

הכיוון $\Rightarrow$ הוא תנאי 2; הכיוון $\Leftarrow$ הוא הקונטרהפוזיציה של תנאי 3 (אם קיימת ריצה מקבלת, אז לא נכון שכל הריצות דוחות, ולכן $x\in A$) [א׳ 00:32:39], [ב׳ 00:43:09]. בסיכום ובהוכחות נעדיף את הפיצול לשני תנאים, כי ההוכחה ממילא מתפצלת לשני כיוונים.

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

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

מגבלת המודל. במודל האי-דטרמיניסטי נעסוק רק במכונות הכרעה. יש הגדרה גם למכונת חישוב אי-דטרמיניסטית, אבל היא מסובכת יותר ולא נעסוק בה [א׳ 00:24:53], [ב׳ 00:44:13].

הדגשה שהמרצה חזר עליה. תמיד לכתוב "מכריעה באופן אי-דטרמיניסטי", גם אם זה נשמע מיותר (מכונה אי-דטרמיניסטית ממילא לא יכולה להכריע אחרת). זה מזכיר לכם שיש בהגדרה תנאי נוסף שצריך לטפל בו [א׳ 00:27:02].

הגדרה 5: מדדי יעילות במודל האי-דטרמיניסטי

תהא $M$ מכונה אי-דטרמיניסטית ויהי $x\in\Sigma_M^*$. נגדיר:

• $\mathrm{time}_M(x)$ — מספר ההפעלות של פונקציית המעברים בריצה אפשרית ארוכה ביותר של $M$ על $x$;
• $\mathrm{space}_M(x)$ — מספר התאים השונים שבהם $M$ כותבת בריצה אפשרית שבה $M$ כותבת בהכי הרבה תאים.

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

שתי מלכודות.

1. אם על $x$ יש ריצה שעוצרת ויש ריצה שאינה עוצרת, אז $\mathrm{time}_M(x)=\infty$, כי המקסימום נלקח על פני כל הריצות [א׳ 01:00:03].
2. המקסימום בזמן והמקסימום במקום אינם בהכרח מושגים באותה ריצה. ייתכנו ריצה ארוכה שכותבת במעט תאים וריצה קצרה שכותבת בהרבה. אסור להניח שמדובר באותה ריצה [א׳ 01:22:01], [ב׳ 00:53:53].

למה מקסימום ולא ממוצע או מינימום. התשובה הכנה שניתנה בכיתה: כי כך הוגדר, ואנחנו עובדים לפי ההגדרה. הרציונל שמאחורי ההגדרה הוא התפיסה הרווחת במדעי המחשב של worst case [א׳ 01:00:34].

הגדרה 6: המחלקות $\mathrm{NTime}(f)$ ו-$\mathrm{NSpace}(f)$

תהא $f:\mathbb{N}\to\mathbb{N}$. נגדיר:

ה-$N$ הוא קיצור ל-Non deterministic, בדיוק כמו שה-$D$ ב-$\mathrm{DTime}$ הוא Deterministic [ב׳ 01:09:14].

איפה בדיוק ההבדל מההגדרה הדטרמיניסטית. ההגדרה נראית זהה, וזה בסדר — אבל שני דברים משתנים ושניהם מוסתרים [א׳ 01:17:24]:

1. "מכריעה את $A$" הוחלף ב"מכריעה את $A$ באופן אי-דטרמיניסטי", כלומר שלושת התנאים של הגדרה 4 ולא ההכרעה הדטרמיניסטית;
2. $\mathrm{time}_M(x)$ ו-$\mathrm{space}_M(x)$ מחביאים מקסימום על פני ריצות אפשריות. זה כבר לא מדד של ריצה אחת.

דוגמה. $A=\{x\in\{0,1\}^*\mid \exists y:\ x=0y1\}\in\mathrm{NTime}(n)$ — נוכיח בהמשך שהמכונה מדוגמה 2 מכריעה אותה באופן אי-דטרמיניסטי, וכל ריצה שלה אורכה $\le|x|+1$, כלומר $c=2$ ו-$f(n)=n$ מתאימים.

הגדרה 7: המחלקות הגסות האי-דטרמיניסטיות

כמו במודל הדטרמיניסטי, שייכות לאיחוד היא טענת קיום: $A\in \mathrm{NP}$ פירושו שקיים $c\ge1$ שעבורו $A\in\mathrm{NTime}(n^c)$, וכשמוכיחים שייכות ל-$\mathrm{NP}$ צריך "לקלף" קודם את הקיים הזה.

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

משפט 1: המכונה מדוגמה 1 אינה מכריעה אף שפה

תהא $M$ המכונה מדוגמה 1 (הטבלה המלאה מופיעה בסעיף הדוגמאות; הרכיב הקריטי הוא $\delta(q_2,B)=\{q_{accept},(q_2,B,R)\}$). אז אין שפה $A$ ש-$M$ מכריעה באופן אי-דטרמיניסטי.

הוכחה. די להראות שתנאי 1 בהגדרה 4 נכשל, כלומר:

ניקח $x=0001$. נתבונן בסדרה האינסופית

נבדוק שזו אכן ריצה אפשרית: השלשה הראשונה שייכת ל-$\delta(q_{start},0)=\{(q_1,0,R)\}$; שתי הבאות שייכות ל-$\delta(q_1,0)=\{(q_1,0,R)\}$; הרביעית שייכת ל-$\delta(q_1,1)=\{(q_1,1,R),(q_2,1,R)\}$; ומכאן ואילך הראש נמצא מימין לקלט וקורא $B$, והמכונה במצב $q_2$, ולכן כל שלשה שייכת ל-$\delta(q_2,B)=\{q_{accept},(q_2,B,R)\}$. אחרי כל צעד כזה הראש זז ימינה וקורא שוב $B$ והמצב נשאר $q_2$, ולכן אפשר להמשיך כך לנצח.

מצאנו קלט שעליו קיימת ריצה אפשרית שאינה עוצרת, ולכן תנאי 1 אינו מתקיים עבור אף שפה $A$. $\blacksquare$

הערה: שימו לב לניסוח המדויק, שהמרצה התעכב עליו בכיתה [א׳ 00:34:13]: קודם מציגים את הקלט ורק אחר כך את הריצה. "קיימת ריצה על קלט" בלי להציג את הקלט הוא ניסוח חסר משמעות, כי ריצה מוגדרת רק ביחס לקלט מסוים.

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

משפט 2: המכונה המתוקנת מכריעה את $A=\{0y1\}$

תהא $M$ המכונה שמתקבלת מדוגמה 1 על ידי מחיקת המעבר $(q_2,B,R)$, כלומר $\delta(q_2,B)=\{q_{accept}\}$. נסמן

— שפת כל המחרוזות מעל $\{0,1\}$ שמתחילות ב-$0$ ומסתיימות ב-$1$. אז $M$ מכריעה את $A$ באופן אי-דטרמיניסטי.

הוכחה. נבדוק את שלושת התנאים של הגדרה 4.

תנאי 1 (עצירה בכל ריצה אפשרית). יהי $x\in\Sigma_M^*$ ותהא $\rho$ ריצה אפשרית של $M$ על $x$. נבחין בשתי עובדות על המכונה:

• בכל אחת משלשות המעבר של $M$ הכיוון הוא $R$, כלומר בכל צעד הראש זז ימינה;
• כאשר הראש קורא $B$, בכל אחד משלושת המצבים $q_{start},q_1,q_2$ המכונה עוברת למצב סופי: $\delta(q_{start},B)=\{q_{reject}\}$, $\delta(q_1,B)=\{q_{reject}\}$, $\delta(q_2,B)=\{q_{accept}\}$.

מכיוון שהראש מתחיל בתא הראשון של הקלט וזז ימינה בכל צעד, אחרי $|x|$ צעדים לכל היותר הוא נמצא בתא הראשון שמימין לקלט וקורא $B$ (אם לא עצר קודם), ובצעד שאחריו המכונה נכנסת למצב סופי. לכן $\rho$ עוצרת אחרי לכל היותר $|x|+1$ צעדים. מכיוון ש-$\rho$ הייתה ריצה אפשרית שרירותית, בכל ריצה אפשרית $M$ עוצרת.

תיקון: בסיכום נכתב "לא יותר מ-$|x|$ צעדים", וגם בהרצאה נאמר "בדיוק אורך של $x$ צעדים" [א׳ 00:40:57]. זו טעות של אחד: הצעד שבו הראש קורא את התו הריק ועובר למצב סופי הוא הפעלה נוספת של $\delta$. הסיכום עצמו מדגים זאת — הריצה שלו על $x=0001$ (אפשרות 1) מונה ארבע שלשות ואז $q_{reject}$, כלומר חמש הפעלות של $\delta$ עבור $|x|=4$. החסם הנכון הוא $|x|+1$. הוא כמובן אינו משנה דבר במסקנות.

תנאי 2 ($x\in A\Rightarrow$ קיימת ריצה מקבלת). נניח $x\in A$. אז קיים $y\in\{0,1\}^*$ כך ש-$x=0y1$. נסמן $y=a_1a_2\cdots a_n$ כאשר $a_1,\dots,a_n\in\{0,1\}$ (ייתכן $n=0$, ואז $x=01$). נתבונן בסדרת השלשות

נוודא שזו ריצה אפשרית:

• הצעד הראשון: המכונה ב-$q_{start}$ והראש קורא את התו הראשון של $x$, שהוא $0$; ואכן $(q_1,0,R)\in\delta(q_{start},0)$.
• הצעדים $2,\dots,n+1$: המכונה ב-$q_1$ והראש קורא את $a_i$. אם $a_i=0$ אז $(q_1,0,R)\in\delta(q_1,0)$; ואם $a_i=1$ אז $(q_1,1,R)\in\delta(q_1,1)$, כי $\delta(q_1,1)$ מכילה שתי שלשות ואנחנו בוחרים את זו שנשארת ב-$q_1$. כאן, ורק כאן, אנחנו מנצלים את האי-דטרמיניזם.
• הצעד $n+2$: המכונה ב-$q_1$ והראש קורא את התו האחרון של $x$, שהוא $1$; בוחרים את השלשה השנייה, $(q_2,1,R)\in\delta(q_1,1)$.
• הצעד האחרון: המכונה ב-$q_2$ והראש נמצא מימין לקלט וקורא $B$; ואכן $q_{accept}\in\delta(q_2,B)$.

זו ריצה אפשרית של $M$ על $x$ המסתיימת במצב מקבל, כנדרש.

תנאי 3 ($x\notin A\Rightarrow$ כל ריצה דוחה). נניח $x\notin A$. אז $x$ אינו מתחיל ב-$0$ או $x$ אינו מסתיים ב-$1$. נפצל לשני מקרים (לא בהכרח זרים — די בכך שהם מכסים).

מקרה 1: $x$ אינו מתחיל ב-$0$. תהא $\rho$ ריצה אפשרית של $M$ על $x$. בצעד הראשון המכונה נמצאת ב-$q_{start}$ והראש קורא את התו הראשון, שהוא $1$ או $B$ (אם $x=\varepsilon$). בשני המקרים $\delta(q_{start},\cdot)=\{q_{reject}\}$, ולכן כבר בצעד הראשון $M$ דוחה את $x$.

מקרה 2: $x$ אינו מסתיים ב-$1$. תהא $\rho$ ריצה אפשרית של $M$ על $x$ (המקרה $x=\varepsilon$ כבר טופל, ולכן נניח $|x|\ge1$).

• אם $\rho$ אינה מגיעה אל $q_2$: מכיוון שבכל צעד הראש זז ימינה, בסופו של דבר הראש קורא $B$ כשהמכונה נמצאת ב-$q_{start}$ או ב-$q_1$, ובשני המצבים המעבר על $B$ הוא ל-$q_{reject}$. לכן $\rho$ מסתיימת במצב דוחה.
• אם $\rho$ מגיעה אל $q_2$: המעבר היחיד שנכנס ל-$q_2$ הוא $(q_2,1,R)\in\delta(q_1,1)$, ולכן בצעד הקודם הראש קרא $1$. מכיוון שהנחנו ש-$x$ אינו מסתיים ב-$1$, אותו $1$ אינו התו האחרון של $x$, ולכן בצעד הבא הראש אינו קורא $B$ אלא תו קלט — $0$ או $1$. מהטבלה, $\delta(q_2,0)=\delta(q_2,1)=\{q_{reject}\}$, ולכן $\rho$ מסתיימת במצב דוחה.

בשני המקרים כל ריצה אפשרית של $M$ על $x$ דוחה. משלושת התנאים נובע ש-$M$ מכריעה את $A$ באופן אי-דטרמיניסטי. $\blacksquare$

הערה על מבנה ההוכחה [א׳ 00:48:00], [א׳ 00:53:44]. שני דברים שהמרצה עמד עליהם:

1. אל תקצרו במקרה 1 בטענה "יש רק ריצה אפשרית אחת ולכן סיימנו". זה נכון אבל זו הליכה על חבל דק: ההגדרה דורשת "לכל ריצה", ולכן פותחים ב"תהא ריצה אפשרית" ומוכיחים לגביה. המבנה הוא מה ששומר עליכם מטעויות.
2. אל תניחו בשלילה כשאין צורך. סטודנט הציע להניח $x\notin A$ ובשלילה שקיימת ריצה מקבלת; המרצה השיב שאם רוצים ללכת בכיוון הזה, פשוט מוכיחים ישירות את הגרירה "קיימת ריצה מקבלת $\Rightarrow x\in A$" (הניסוח עם "אם ורק אם"), בלי לעטוף אותה בשלילה. שתי הדרכים שקולות לוגית ולגיטימיות לגמרי; בחרו את זו שנוח יותר להוכיח [א׳ 00:46:16].

משפט 3: מקום חסום בזמן במודל האי-דטרמיניסטי

לכל מכונה אי-דטרמיניסטית $M$ ולכל $x\in\Sigma_M^*$ מתקיים

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

תהא $\rho$ ריצה אפשרית כלשהי של $M$ על $x$. נסמן

• $t$ — מספר הצעדים ש-$M$ מבצעת בריצה $\rho$ על $x$;
• $s$ — מספר התאים השונים ש-$M$ כותבת בהם בריצה $\rho$ על $x$.

(היינו חייבים סימונים חדשים דווקא משום שאי אפשר להשתמש ב-$\mathrm{time}_M$ וב-$\mathrm{space}_M$ — אלה מדדים של המכונה, לא של ריצה בודדת.)

1. $s\le t$. בכל צעד בריצה $\rho$ המכונה כותבת בתא אחד לכל היותר, ולכן מספר התאים השונים שנכתבו בהם אינו עולה על מספר הצעדים. זו בדיוק ההבחנה מהמודל הדטרמיניסטי, ללא שינוי.
2. $t\le \mathrm{time}_M(x)$. לפי הגדרה 5, $\mathrm{time}_M(x)$ הוא המקסימום של מספר הצעדים על פני כל הריצות האפשריות, ו-$\rho$ היא אחת מהן.

משני אלה, $s\le\mathrm{time}_M(x)$.

הראינו זאת עבור ריצה אפשרית שרירותית $\rho$, כלומר: בכל ריצה אפשרית של $M$ על $x$, מספר התאים השונים שנכתבו בהם חסום על ידי $\mathrm{time}_M(x)$ — שהוא ביטוי שאינו תלוי ב-$\rho$. בפרט זה נכון גם עבור ריצה אפשרית שבה $M$ כותבת בהכי הרבה תאים, ומספר התאים בריצה זו הוא בדיוק $\mathrm{space}_M(x)$. לכן $\mathrm{space}_M(x)\le\mathrm{time}_M(x)$. $\blacksquare$

מה בדיוק השתנה מהמודל הדטרמיניסטי. רק המעטפת [ב׳ 01:03:32]. הליבה — "בכל צעד כותבים בתא אחד לכל היותר" — זהה מילה במילה. מה שנוסף הוא שלפני הליבה כותבים "תהא ריצה אפשרית" ונותנים סימנים למדדים של הריצה הספציפית, ואחרי הליבה לוקחים מקסימום על אי-שוויון שהאגף הימני שלו כבר לא תלוי בריצה. זה התבנית של כל ההוכחות בשיעור הזה.

משפט 4: זמן חסום אקספוננציאלית במקום

לכל מכונה אי-דטרמיניסטית $M$ קיים קבוע $c>0$ כך שלכל $x\in\Sigma_M^*$:

הקבוע הוא $c=\lg|Q|+\lg|\Gamma|+1$, כמו במודל הדטרמיניסטי.

איפה ההבדלים מהטענה המקבילה בשיעור 2 [א׳ 01:03:45]. שלושה, אחד גלוי ושניים סמויים:

1. גלוי: ההנחה היא "$M$ עוצרת בכל ריצה אפשרית" ולא "$M$ עוצרת על $x$". זו הנחה חזקה יותר, והיא הכרחית — ראו את ההערה בסוף ההוכחה.
2. סמוי: $\mathrm{time}_M(x)$ הוא מקסימום.
3. סמוי: $\mathrm{space}_M(x)$ הוא מקסימום — ולא בהכרח באותה ריצה.

הוכחה. תהא $\rho$ ריצה אפשרית כלשהי של $M$ על $x$. נסמן ב-$t$ את מספר הצעדים ש-$M$ מבצעת ב-$\rho$, וב-$s$ את מספר התאים השונים ש-$M$ כותבת בהם ב-$\rho$.

שלב א — ספירת קונפיגורציות. קונפיגורציה של $M$ מורכבת ממצב, מתוכן החלק הרלוונטי של הסרט וממיקום הראש. אם בריצה $\rho$ נכתב ב-$s$ תאים שונים, מספר הקונפיגורציות שיכולות להופיע בריצה זו הוא לכל היותר

כאשר האי-שוויון האחרון נובע מ-$\lg|Q|\le s\lg|Q|$ ומ-$\lg s\le s$ עבור $s\ge1$. זהו בדיוק החישוב משיעור 2, ללא שינוי כלשהו הנובע מאי-דטרמיניזם [א׳ 01:08:10].

שלב ב — אין חזרה על קונפיגורציה. נטען שבריצה $\rho$ אין שתי קונפיגורציות זהות. נניח בשלילה שיש: הקונפיגורציה $C$ מופיעה ב-$\rho$ בשני זמנים $i<j$. נתבונן בסדרת הבחירות (תסריט הריצה) שהובילה מ-$C$ בזמן $i$ אל $C$ בזמן $j$. מכיוון שהקונפיגורציה בשני הקצוות זהה, אותה סדרת בחירות עצמה חוקית שוב, ואפשר לחזור עליה שוב ושוב. מתקבלת ריצה אפשרית אינסופית של $M$ על $x$ — בסתירה להנחה ש-$M$ עוצרת על $x$ בכל ריצה אפשרית.

הערה: בהרצאה זה נאמר בקיצור, ואף תוקן תוך כדי [א׳ 01:09:13] — המרצה אמר תחילה "אני יודע ש-$Q$ סופית ולכן המכונה אינה חוזרת על אותה קונפיגורציה", עצר ותיקן ל"אני יודע ש-$M$ עוצרת בכל ריצה". הפירוט כאן. שימו לב שזו בדיוק הנקודה שבה ההנחה החזקה יותר משמשת: במודל הדטרמיניסטי חזרה על קונפיגורציה בריצה שלנו גוררת מיד שאותה ריצה לא תעצור, כי ההמשך נקבע יחידות. במודל האי-דטרמיניסטי חזרה על קונפיגורציה ב-$\rho$ אינה מונעת מ-$\rho$ עצמה לעצור — היא רק מוכיחה שקיימת ריצה אחרת שאינה עוצרת. לכן ההנחה חייבת להיות על כל הריצות.

שלב ג — חיבור. מכיוון שכל צעד ב-$\rho$ מוביל לקונפיגורציה חדשה, מספר הצעדים חסום על ידי מספר הקונפיגורציות האפשריות:

שלב ד — מעבר למדדים. מכיוון ש-$s$ הוא מספר התאים שנכתבו ב-$\rho$ ו-$\mathrm{space}_M(x)$ הוא המקסימום על פני כל הריצות, מתקיים $s\le\mathrm{space}_M(x)$. הפונקציה $u\mapsto 2^{cu}$ עולה, ולכן

שלב ה — מקסימום. האגף הימני אינו תלוי ב-$\rho$, והאי-שוויון הוכח עבור ריצה אפשרית שרירותית. לכן הוא נכון בפרט עבור ריצה אפשרית ארוכה ביותר, שבה מספר הצעדים הוא $\mathrm{time}_M(x)$:

מדוע דווקא הכיוון הזה הוכח בכיתה. המרצה בחר בכוונה להוכיח את האי-שוויון הקשה יותר ולהשאיר את $\mathrm{space}\le\mathrm{time}$ כתרגיל [א׳ 01:11:19]; בהקלטה המקבילה הוכח דווקא הקל (משפט 3 כאן), ולכן שני הכיוונים מופיעים בקובץ הזה במלואם.

משפט 5: יחסים בסיסיים בין המחלקות האי-דטרמיניסטיות

תהיינה $f,g:\mathbb{N}\to\mathbb{N}$. אז:

1. $\mathrm{NTime}(f)\subseteq\mathrm{NSpace}(f)$;
2. $\mathrm{NSpace}(f)\subseteq\bigcup_{d\ge1}\mathrm{NTime}\!\left(2^{\,d\cdot f}\right)$;
3. אם $f=O(g)$ אז $\mathrm{NTime}(f)\subseteq\mathrm{NTime}(g)$ וגם $\mathrm{NSpace}(f)\subseteq\mathrm{NSpace}(g)$.

הוכחה של 1. יהי $A\in\mathrm{NTime}(f)$. לפי ההגדרה קיימות מכונה אי-דטרמיניסטית $M$ וקבוע $c>0$ כך ש-$M$ מכריעה את $A$ באופן אי-דטרמיניסטי ולכל $x$ מתקיים $\mathrm{time}_M(x)\le c\cdot f(|x|)$. לפי משפט 3, לכל $x$:

אותה מכונה $M$ ואותו קבוע $c$ מעידים ש-$A\in\mathrm{NSpace}(f)$. $\blacksquare$

הוכחה של 2. יהי $A\in\mathrm{NSpace}(f)$, ותהיינה $M$ ו-$c>0$ המעידות על כך. מכיוון ש-$M$ מכריעה את $A$ באופן אי-דטרמיניסטי, מתקיים תנאי 1 של הגדרה 4: לכל $x$, בכל ריצה אפשרית $M$ עוצרת. לכן תנאי משפט 4 מתקיים, ועם הקבוע $c'=\lg|Q_M|+\lg|\Gamma_M|+1$ התלוי רק ב-$M$:

האי-שוויון האמצעי מותר כי $u\mapsto 2^{c'u}$ עולה והצבנו $\mathrm{space}_M(x)\le c\cdot f(|x|)$. לכן $M$ עם הקבוע $1$ מעידה ש-$A\in\mathrm{NTime}\!\left(2^{d\cdot f}\right)$, ובפרט $A$ שייכת לאיחוד. $\blacksquare$

הוכחה של 3. $f=O(g)$ פירושו שקיים $c_0>0$ כך שלכל $n$ מתקיים $f(n)\le c_0\cdot g(n)$. יהי $A\in\mathrm{NTime}(f)$ עם עדים $M,c$. אז לכל $x$:

ולכן $M$ עם הקבוע $c\cdot c_0$ מעידה ש-$A\in\mathrm{NTime}(g)$. ההוכחה למקום זהה מילה במילה עם החלפת $\mathrm{time}$ ב-$\mathrm{space}$. $\blacksquare$

משפט 6: כל מכונה דטרמיניסטית היא מכונה אי-דטרמיניסטית, ולכן $\mathrm{DTime}(f)\subseteq\mathrm{NTime}(f)$

לכל $f:\mathbb{N}\to\mathbb{N}$ מתקיים

הוכחה. יהי $A\in\mathrm{DTime}(f)$, ותהיינה $M=(Q,q_{start},F,\Sigma,\Gamma,\delta)$ ו-$c>0$ המעידות על כך. נגדיר מכונה אי-דטרמיניסטית $M'$ עם אותם $Q,q_{start},F,\Sigma,\Gamma$ ועם

כלומר כל קבוצה בתמונה של $\delta'$ היא יחידון.

יש בדיוק ריצה אפשרית אחת. באינדוקציה על מספר הצעדים: בכל צעד יש בדיוק שלשה אחת בקבוצה, ולכן אין בחירה. לכן לכל $x$ יש בדיוק ריצה אפשרית אחת של $M'$ על $x$, והיא זהה לריצת $M$ על $x$.

$M'$ מכריעה את $A$ באופן אי-דטרמיניסטי. נבדוק את שלושת התנאים; המפתח הוא שכאשר קבוצת הריצות האפשריות היא יחידון, "לכל ריצה" ו"קיימת ריצה" מתלכדים [א׳ 01:25:30].

1. $M$ מכריעה את $A$, ולכן היא עוצרת על כל קלט; הריצה היחידה של $M'$ היא ריצת $M$, ולכן $M'$ עוצרת בכל ריצה אפשרית.
2. אם $x\in A$ אז ריצת $M$ על $x$ מסתיימת ב-$q_{accept}$; זו ריצה אפשרית של $M'$ המסתיימת במצב מקבל, ולכן קיימת ריצה מקבלת.
3. אם $x\notin A$ אז ריצת $M$ על $x$ מסתיימת ב-$q_{reject}$; זו הריצה האפשרית היחידה של $M'$, ולכן בכל ריצה אפשרית $M'$ דוחה.

המדדים לא השתנו. $\mathrm{time}_{M'}(x)$ הוא מקסימום על פני קבוצה בת ריצה אחת, ולכן $\mathrm{time}_{M'}(x)=\mathrm{time}_M(x)\le c\cdot f(|x|)$. לכן $M'$ ו-$c$ מעידות ש-$A\in\mathrm{NTime}(f)$.

ההוכחה עבור המקום זהה. $\blacksquare$

מסקנה.

הוכחה. יהי $A\in P$. אז קיים $c\ge1$ כך ש-$A\in\mathrm{DTime}(n^c)$. לפי משפט 6, $A\in\mathrm{NTime}(n^c)\subseteq \mathrm{NP}$. $\blacksquare$

האינטואיציה בשורה אחת [א׳ 01:24:26]: כל מה שאפשר לעשות בתקציב מסוים באופן דטרמיניסטי — אותה מכונה עם אותו תקציב עושה באופן אי-דטרמיניסטי. זה מקרה פרטי, לא סימולציה.

השאלה הפתוחה. האם $P=\mathrm{NP}$? באופן שקול (כי כיוון אחד ידוע): האם $\mathrm{NP}\subseteq P$? כלומר, האם כל מה שאפשר להכריע בזמן פולינומי באופן אי-דטרמיניסטי אפשר להכריע בזמן פולינומי באופן דטרמיניסטי. זו ככל הנראה השאלה הפתוחה המפורסמת ביותר במדעי המחשב, ויש עליה פרס של מיליון דולר. לא יודעים להוכיח שכן ולא יודעים להוכיח שלא [א׳ 01:28:25], [ב׳ 01:21:54].

משפט 7 (ללא הוכחה): שקילות חישובית למודל הדטרמיניסטי

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

הטענה לא הוכחה בכיתה [א׳ 00:55:52]. הרעיון: מכונה דטרמיניסטית יכולה לעבור על כל הריצות האפשריות של $M$ על $x$ בסריקה לרוחב של עץ החישוב, ולהכריז "מקבלת" אם מצאה ענף מקבל. אם $M$ מכריעה שפה, כל ענף בעץ סופי והסתעפות העץ סופית (כי $\delta$ מחזירה קבוצות סופיות), ולכן העץ כולו סופי והסריקה מסתיימת.

מה כן משתנה — היעילות. בדיוק כמו במעבר בין מכונה רב-סרטית למכונה חד-סרטית: כוח החישוב זהה, המדדים לא. כאן ההפרש עלול להיות אקספוננציאלי, וזה ליבת שאלת $P$ מול $\mathrm{NP}$.

טענות נוספות שעוברות כמות שהן [א׳ 01:14:03], [ב׳ 01:06:39]: מכונה רב-סרטית אי-דטרמיניסטית והקשר בין המדדים שלה למכונה חד-סרטית, מכונה אוניברסלית אי-דטרמיניסטית ומדדי היעילות שלה, ומשפטי ההיררכיה. ההוכחות זהות פרט למעטפת. המרצה המליץ עליהן כתרגול טוב בדיוק משום שהמהות מוכרת וכל מה שנדרש הוא לתרגל את המעטפת.

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

דוגמה 1: המכונה מהסיכום, ושלושת הענפים על $x=0001$

$\Gamma=\{0,1,B\}$, $\Sigma=\{0,1\}$, $Q=\{q_{start},q_1,q_2,q_{accept},q_{reject}\}$. טבלת המעברים (התאים המסומנים בסיכום בהדגשה הם השורות עם יותר משלשה אחת):

באותו אופן, כדיאגרמת מצבים (מצב $q_{reject}$ וכל החצים אליו מושמטים לפי הקונבנציה):

• $q_{start}\ \xrightarrow{\ 0/0,R\ }\ q_1$
• $q_1\ \xrightarrow{\ 0/0,R\ }\ q_1$ (לולאה עצמית), $\quad q_1\ \xrightarrow{\ 1/1,R\ }\ q_1$ (לולאה עצמית)
• $q_1\ \xrightarrow{\ 1/1,R\ }\ q_2$
• $q_2\ \xrightarrow{\ B/B,R\ }\ q_2$ (לולאה עצמית), $\quad q_2\ \xrightarrow{\ B/B,R\ }\ q_{accept}$

שלוש ריצות אפשריות על $x=0001$ (כפי שהן מופיעות בסיכום):

אפשרות 1 — דוחה. $(q_1,0,R),\ (q_1,0,R),\ (q_1,0,R),\ (q_1,1,R),\ q_{reject}$ המכונה נשארת ב-$q_1$ גם כשהיא קוראת את ה-$1$ האחרון, ואז קוראת $B$ ב-$q_1$ ודוחה.

אפשרות 2 — מקבלת. $(q_1,0,R),\ (q_1,0,R),\ (q_1,0,R),\ (q_2,1,R),\ (q_2,B,R),\ q_{accept}$ כאן, כשהמכונה קוראת את ה-$1$ האחרון, היא בוחרת את השלשה השנייה ועוברת ל-$q_2$; אחר כך היא קוראת $B$, בוחרת להישאר צעד אחד ב-$q_2$, ובצעד הבא מקבלת.

אפשרות 3 — אינה עוצרת. $(q_1,0,R),\ (q_1,0,R),\ (q_1,0,R),\ (q_2,1,R),\ (q_2,B,R),\ (q_2,B,R),\ (q_2,B,R),\ \dots$ אותה התחלה, אבל המכונה בוחרת שוב ושוב להישאר ב-$q_2$ ולזוז ימינה על תווים ריקים — לנצח.

המסקנה. שלוש ריצות אפשריות על אותו קלט, עם שלוש תוצאות שונות. לפי משפט 1 המכונה הזאת אינה מכריעה אף שפה, בגלל אפשרות 3.

דוגמה 2: תיקון המכונה — מוחקים מעבר אחד

מוחקים את $(q_2,B,R)$ מהתא $\delta(q_2,B)$. עכשיו כל ריצה עוצרת אחרי $|x|+1$ צעדים לכל היותר, ולפי משפט 2 המכונה מכריעה באופן אי-דטרמיניסטי את

מעקב על שני קלטים קונקרטיים:

• $x=0001$: ריצת אפשרות 2 (בלי שלב ההשהיה ב-$q_2$) מסתיימת ב-$q_{accept}$ — ואכן $x$ מתחיל ב-$0$ ומסתיים ב-$1$. שימו לב שגם אפשרות 1, שדוחה, עדיין קיימת; זה מותר, כי לקבלה מספיק עד אחד.
• $x=0010$: כל הריצות דוחות. מי שנשאר ב-$q_1$ עד הסוף קורא $B$ ב-$q_1$ ונדחה. מי שעבר ל-$q_2$ עשה זאת בקריאת ה-$1$ שבמקום השלישי, ואז קורא $0$ ב-$q_2$ ונדחה מיד. ואכן $x\notin A$.

דוגמה 3: מכונה שנייה (מההקלטה המקבילה) — מחרוזות שמסתיימות ב-$0$

מכונה אחרת לגמרי, עם שני מצבי עבודה בלבד, $Q=\{q_{start},q_1,q_{accept},q_{reject}\}$ ו-$\Gamma=\{0,1,B\}$: