6An Equivalent Definition of NP: Verification, Witnesses and Certificates

בקצרה

• מסיימים את הטיפול במכונה האי‑דטרמיניסטית שמכריעה את $\mathrm{SAT}$: היא אכן מכריעה את $\mathrm{SAT}$ באופן אי‑דטרמיניסטי, וכמכונה חד‑סרטית זמן הריצה שלה חסום ב‑$O(|\langle\varphi\rangle|^3)$.
• עושים את אותו תרגיל מקצה לקצה על שפת המספרים הפריקים: אלגוריתם דטרמיניסטי נאיבי דורש זמן אקספוננציאלי באורך הקלט, ואילו מכונה אי‑דטרמיניסטית מכריעה אותה ב‑$O(|x|^3)$ — הדגמה חדה של מה הכוח האי‑דטרמיניסטי קונה לנו.
• שתי המכונות האלה חולקות מבנה אחד: האי‑דטרמיניזם מרוכז כולו בשלב אחד — כתיבת ההשמה, או כתיבת שני הגורמים. אם מישהו חיצוני היה נותן לנו את האובייקט הזה, כל השאר היה דטרמיניסטי ופולינומי.
• המשפט המרכזי: $A\in \mathrm{NP}$ אם ורק אם קיימים פולינומים $p,q$ ומכונה דטרמיניסטית $M$ הרצה בזמן $p$, כך שלכל $x$ מתקיים $x\in A \iff \exists w\in\{0,1\}^{q(|x|)}$ שעבורו $M$ מקבלת את $(x,w)$. המרצה בהקלטה המקבילה קורא למחלקה המוגדרת כך $\mathrm{NP}'$, ומוכיח $\mathrm{NP}=\mathrm{NP}'$.
• ה‑$w$ נקרא עד (witness) או אישור (certificate), והמכונה $M$ נקראת מוודא (verifier). שימו לב: $M$ אינה מכריעה את $A$ — היא אפילו לא מקבלת את $x$ לבדו כקלט.
• ההוכחה דו‑כיוונית ובנייתית: מ‑verifier בונים NTM שכותבת את $w$ באופן אי‑דטרמיניסטי ואז מריצה את $M$; מ‑NTM בונים verifier שהעד שלו הוא רצף הבחירות האי‑דטרמיניסטיות לאורך ענף מקבל. בדרך מוכיחים למת עזר: אפשר להניח שלכל מעבר יש לכל היותר שתי אפשרויות, ואז די בביט אחד לכל צעד.
• שני החסמים הכרחיים: אורך העד חייב להיות פולינומי, וגם זמן האימות חייב להיות פולינומי. ויתור על הראשון מוריד את ההגדרה עד כדי אפיון של $\mathrm{RE}$ מקורס החישוביות; ויתור על השני מנפח את המחלקה מעל $\mathrm{EXP}$.
• המשמעות שכדאי לקחת: $x$ הוא טענה, $w$ הוא הוכחה, $M$ הוא בודק ההוכחות. השאלה $\mathrm{P}$ מול $\mathrm{NP}$ הופכת לשאלה "האם קשה יותר להוכיח מאשר לבדוק הוכחה" — או, בניסוח של ההרצאה, האם קל יותר לפתור מבחן או לבדוק אותו.

רקע ותלויות

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

(א) מודל המכונה (ראו שיעורים 1–2). מכונת טיורינג נכתבת כרביעייה‑שישייה $M=(Q,q_{start},F,\Sigma,\Gamma,\delta),$ כאשר $Q$ קבוצת המצבים, $q_{start}$ מצב ההתחלה, $F\subseteq Q$ קבוצת המצבים המקבלים, $\Sigma$ אלפבית הקלט, $\Gamma\supseteq\Sigma$ אלפבית הסרט, ו‑$\delta$ פונקציית (או יחס) המעברים. במכונה דטרמיניסטית $\delta(q,\alpha)$ הוא איבר יחיד; במכונה אי‑דטרמיניסטית $\delta(q,\alpha)\subseteq Q\times\Gamma\times\{L,R\}$ היא קבוצה, ובכל צעד המכונה בוחרת אחד מאיבריה.

(ב) מעבר בין מספר סרטים (ראו שיעורים 1–2). עבור מכונה רב‑סרטית $M$ קיימת מכונה חד‑סרטית שקולה סמנטית $\hat M$ שעבורה $\mathrm{time}_{\hat M}(x) \;\le\; O\big(\mathrm{time}_{M}(x)\cdot \mathrm{space}_{M}(x)\big).$ מכיוון שתמיד $\mathrm{space}\le\mathrm{time}$, נובע מכאן גם החסם המוכר $O(\mathrm{time}^2)$ — אבל כשידוע לנו משהו על המקום, הגרסה הראשונה הדוקה יותר. שתי המסירות של השיעור משתמשות בדיוק בנקודה הזו, וכל אחת מקבלת בזכותה חסם $O(n^3)$ במקום $O(n^4)$.

(ג) הכרעה באופן אי‑דטרמיניסטי (ראו שיעור 4). מכונה אי‑דטרמיניסטית $N$ מכריעה שפה $A$ באופן אי‑דטרמיניסטי אם מתקיימים שני תנאים: (i) לכל $x$, כל ריצה אפשרית של $N$ על $x$ עוצרת — אין ריצות אינסופיות; (ii) $x\in A$ אם ורק אם קיימת ריצה אפשרית של $N$ על $x$ שבה היא מקבלת. שקול לנסח את (ii) כשני תנאים נפרדים: אם $x\in A$ אז קיימת ריצה מקבלת, ואם $x\notin A$ אז בכל ריצה אפשרית $N$ דוחה. שימו לב לאסימטריה: קבלה נקבעת על ידי כמת "קיים", דחייה על ידי כמת "לכל". בפרט ייתכן בהחלט שעל קלט ששייך לשפה נריץ את המכונה ונקבל דחייה — הדרישה היא רק שתהיה אפשרות לבחור נכון.

(ד) מדדי יעילות אי‑דטרמיניסטיים והמחלקות (ראו שיעור 4). $\mathrm{time}_N(x)$ מוגדר כמספר הצעדים בריצה הארוכה ביותר מבין כל הריצות האפשריות על $x$; $\mathrm{space}_N(x)$ הוא מספר התאים השונים שנכתבים בריצה הבזבזנית ביותר — ולא בהכרח באותה ריצה. $\mathrm{NTime}(f)$ היא מחלקת השפות שניתן להכריע אי‑דטרמיניסטית בזמן $O(f)$, ובאופן דומה $\mathrm{NSpace}(f)$. המחלקה שמעניינת אותנו היא $\mathrm{NP}=\bigcup_{c\ge 1}\mathrm{NTime}(n^c).$

(ה) $\mathrm{SAT}$ ו‑CNF (ראו שיעור 5). נוסחת CNF היא קוניונקציה של פסוקיות, וכל פסוקית היא דיסיונקציה של ליטרלים. $\mathrm{SAT}=\{\langle\varphi\rangle \mid \varphi \text{ CNF, satisfiable}\}$. בסוף שיעור 5 הוגדרה מכונה דו‑סרטית אי‑דטרמיניסטית $M$ שעל קלט $\langle\varphi\rangle$:

1. סורקת את $\varphi$ וסופרת את מספר המשתנים $n$ — באופן דטרמיניסטי;
2. כותבת על הסרט השני מחרוזת $v\in\{0,1\}^n$ — באופן אי‑דטרמיניסטי;
3. בודקת האם ההשמה המקודדת ב‑$v$ מספקת את $\varphi$, ומקבלת אם ורק אם כן — באופן דטרמיניסטי.

הפרשנות של שלב 2: כל מחרוזת בינרית באורך מספר המשתנים נחשבת לתיאור של השמה — הביט ה‑$i$ הוא הערך שההשמה נותנת למשתנה $x_i$. זו התשובה לשאלה של סטודנט: ההשמה $v$ אמנם מוגדרת פורמלית כפונקציה שמקבלת משתנה יחיד ומחזירה $\mathrm{true}/\mathrm{false}$, אבל הקידוד שלה על הסרט הוא מחרוזת אחת באורך $n$ (‏[00:07:39], מסירה 11).

על ציטוט המקורות בקובץ זה. לשיעור יש שתי הקלטות של שתי מסירות מקבילות לשתי קוהורטות. חותמות זמן מסומנות כאן [hh:mm:ss] עם ציון המסירה: מסירה 10 = zcCQY3oT40Y (הקוהורטה שעבדה על המספרים הפריקים), מסירה 11 = U3Sy9Qr1Me0 (הקוהורטה שהמשיכה מ‑$\mathrm{SAT}$).

הגדרות

הגדרה 1: מוודא (verifier), עד (witness / certificate), והמחלקה $\mathrm{NP}'$

תהא $A$ שפה. נאמר ש‑$A\in \mathrm{NP}'$ אם קיימים פולינומים $p,q$ ומכונת טיורינג דטרמיניסטית $M$ כך ש:

1. לכל קלט $a$ מתקיים $\ \mathrm{time}_M(a)\le p(|a|)$;
2. לכל $x$ מתקיים $x\in A \iff \exists\, w\in\{0,1\}^{q(|x|)} \ \text{ s.t. } M \text{ accepts } (x,w).$

המחרוזת $w$ נקראת עד (witness) או אישור (certificate) לשייכות $x\in A$, והמכונה $M$ נקראת מוודא (verifier). באופן שקול: $A=\Big\{x\in\Sigma^*\ \Big|\ \exists w\in\{0,1\}^{q(|x|)}:\ M \text{ accepts } (x,w)\Big\}.$

השם $\mathrm{NP}'$ הוא הסימון שבו השתמש המרצה במסירה 10 (‏[00:39:10]) כדי להדגיש שזו לכאורה מחלקה אחרת, שהוגדרה בלי שום התייחסות לאי‑דטרמיניזם; משפט 4 יוכיח ש‑$\mathrm{NP}=\mathrm{NP}'$.

אינטואיציה. חשבו על $x$ בתור טענה ועל $w$ בתור הוכחה לטענה. המוודא אינו מנסה להוכיח בעצמו — הוא מקבל טענה והוכחה, וכל תפקידו הוא להגיד אם ההוכחה משכנעת (‏[00:42:22]–[00:43:23], מסירה 10). זה ההבדל בין לפתור מבחן לבין לבדוק מבחן (‏[00:16:07], מסירה 11; ‏[00:46:01], מסירה 10). ותנאי (2) הוא בדיוק הדרישה שהמערכת תהיה נאותה ושלמה: לכל טענה נכונה יש הוכחה משכנעת, ולשום טענה שגויה אין הוכחה משכנעת.

בגלל זה חשוב להדגיש: $M$ אינה מכריעה את $A$, ולא רק מסיבה חישובית אלא כבר מסיבה תחבירית — הקלט שלה הוא הזוג $(x,w)$ ולא $x$ (‏[00:20:28], מסירה 11; ‏[00:41:50], מסירה 10). לכן היא נקראת מוודא ולא מכונת הכרעה.

שני הפרמטרים בהגדרה הם שני חסמים נפרדים: $q$ חוסם את אורך העזרה שמותר לקבל מבחוץ, ו‑$p$ חוסם את זמן הבדיקה. כדברי המרצה במסירה 10 (‏[00:16:57]): "אני רוצה להימנע ממקרה שיש איזו עדות, אבל היא כל כך ארוכה שרק לקרוא אותה ייקח לי זמן אקספוננציאלי". במשפט 5 נראה שאף אחד מהחסמים אינו מיותר.

מופע. $A=\mathrm{SAT}$. העד ל‑$\langle\varphi\rangle\in \mathrm{SAT}$ הוא השמה מספקת, מקודדת כמחרוזת בינרית באורך מספר המשתנים; האימות הוא הצבה וחישוב ערך אמת — פולינומי.

מופע נוסף. $\mathrm{COMPOSITES}=\{x\in\{0,1\}^*\mid x \text{ encodes a composite number in binary}\}$. אם אני טוען בפניכם ש‑8 פריק, אתם לא מוכנים להאמין לי סתם — פירוק לגורמים הוא יקר. אבל אם אני מוסר לכם את הזוג $(2,4)$, כל מה שנשאר לכם הוא כפל, שהוא זול חישובית. העד הוא הזוג, האימות הוא הכפל (‏[00:23:14], מסירה 11; ‏[00:48:41], מסירה 10).

אי‑מופע — למה זו לא סתם "כל שפה". קחו את $\overline{\mathrm{SAT}}$ (נוסחאות CNF שאינן ספיקות). מהו העד? השמה בודדת אינה עוזרת — כדי לשכנע ש‑$\varphi$ אינה ספיקה צריך משהו שמכסה את כל ההשמות, ולא ידוע לאיש עד קצר כזה. ההגדרה אינה מספקת את עצמה אוטומטית.

הגדרה 2: תסריט ריצה (run script)

תהא $N$ מכונה אי‑דטרמיניסטית. בכל צעד $N$ מחליטה על שלושה דברים: המצב הבא, התו שייכתב, וכיוון הזזת הראש. לכן כל ריצה של $N$ על קלט $x$ ניתנת לתיאור על ידי סדרה סופית של שלשות $(q,\beta,d)\in Q\times\Gamma\times\{L,R\},$ באורך מספר הצעדים בריצה. מחרוזת המקודדת סדרה כזו נקראת תסריט ריצה של $N$ על $x$. מספר הביטים לתיאור שלשה אחת הוא $\lceil \lg|Q|\rceil+\lceil \lg|\Gamma|\rceil+1,$ כי לציון אחד מ‑$|Q|$ מצבים דרושים $\lceil\lg|Q|\rceil$ ביטים, לציון אחד מ‑$|\Gamma|$ תווים דרושים $\lceil\lg|\Gamma|\rceil$ ביטים, וכיוון ההזזה הוא ביט יחיד. $|Q|$ ו‑$|\Gamma|$ הם קבועים של המכונה ואינם תלויים בקלט.

אינטואיציה — המבוך (‏[00:40:43]–[00:43:31], מסירה 11). חשבו על מכונה אי‑דטרמיניסטית כעל מי שפותר מבוך: בכל התפצלות הוא בוחר לאן לפנות, והמבוך "פתיר" אם ורק אם קיימת סדרת בחירות שמוציאה החוצה. איזו עזרה מינימלית אני צריך לקבל לפני הכניסה כדי לוודא שאפשר לצאת? לא מצפן — אני לא יודע איפה היציאה. לא שלטים — הם כבר בפנים. מפה תספיק, אבל היא נותנת יותר מדי: היא מאפשרת לי לפתור את המבוך, לא רק לוודא פתרון. המינימום הנדרש הוא רשימת הפניות: "בצומת הראשון שמאלה, בשני ישר, בשלישי ימינה…". תסריט ריצה הוא בדיוק רשימת הפניות הזו.

הגדרה 3: מכונה אי‑דטרמיניסטית מנורמלת (בינארית)

מכונה אי‑דטרמיניסטית $N$ תיקרא מנורמלת אם לכל $q\in Q$ ולכל $\alpha\in\Gamma$ מתקיים $|\delta(q,\alpha)|\le 2$ — כלומר בכל מעבר יש לכל היותר שתי אפשרויות בחירה.

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

מופע. המכונה למספרים פריקים (משפט 2) כפי שנכתבה במסירה 10 היא כמעט מנורמלת: בשלב כתיבת המספר יש לה בדיוק שלוש אפשרויות בכל צעד — לכתוב $0$, לכתוב $1$, או לסיים ולעבור לשלב הבא. אי‑מופע: מכונה שבמעבר מסוים מפצלת ל‑10 אפשרויות אינה מנורמלת; משפט 3 מראה איך להחליף אותה בשקולה מנורמלת.

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

משפט 1: המכונה מכריעה את $\mathrm{SAT}$ באופן אי‑דטרמיניסטי, בזמן $O(|\langle\varphi\rangle|^3)$

טענה. המכונה $M$ שתוארה בסעיף (ה) של הרקע מכריעה את $\mathrm{SAT}$ באופן אי‑דטרמיניסטי.

הוכחה. תהא $\varphi$ נוסחה מצורת CNF.

מקרה $\langle\varphi\rangle\in \mathrm{SAT}$. אזי קיימת השמה $v$ המספקת את $\varphi$. נסמן ב‑$n$ את מספר המשתנים; $v$ מקודדת כמחרוזת בת $n$ ביטים. בשלב 2 המכונה כותבת מחרוזת שרירותית באורך $n$ באופן אי‑דטרמיניסטי, ולכן קיימת ריצה אפשרית של $M$ שבה היא כותבת בדיוק את הקידוד של $v$. בריצה זו שלב 3 — דטרמיניסטי — בודק את $v$ על $\varphi$, מוצא שהיא מספקת, ולכן $M$ מקבלת.

מקרה $\langle\varphi\rangle\notin \mathrm{SAT}$. אזי אף השמה אינה מספקת את $\varphi$. תהא ריצה אפשרית כלשהי, ותהא $v$ ההשמה שנכתבה בה בשלב 2. מכיוון ש‑$v$ אינה מספקת, שלב 3 מסיים בדחייה. זה נכון לכל ריצה אפשרית.

לפי הגדרת ההכרעה האי‑דטרמיניסטית, $M$ מכריעה את $\mathrm{SAT}$ באופן אי‑דטרמיניסטי. $\blacksquare$

הרעיון בלב ההוכחה (‏[00:04:20], מסירה 11). בכל הוכחת הכרעה אי‑דטרמיניסטית התבנית זהה: בכיוון החיובי מספיק להצביע על אפשרות אחת לבחור נכון; בכיוון השלילי צריך לכסות את כל האפשרויות.

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

בהינתן $\langle\varphi\rangle$, על המכונה הדו‑סרטית:

• ספירת המשתנים — מעבר ליניארי אחד: $O(|\langle\varphi\rangle|)$ צעדים.
• כתיבת ההשמה — $n\le|\langle\varphi\rangle|$ ביטים: $O(|\langle\varphi\rangle|)$ צעדים.
• בדיקת הסיפוק — $O(|\langle\varphi\rangle|^2)$. הנימוק: עוברים על הנוסחה ליטרל אחר ליטרל, ולכל מופע של משתנה יש לגשת לתא המתאים בהשמה שעל הסרט השני. במקרה הגרוע המופעים מסודרים כך שהראש נאלץ לחצות את כל ההשמה בין מופע למופע (מופע של המשתנה הראשון, אחריו של האחרון, אחריו שוב של הראשון). מכפלת מספר המופעים ב‑אורך ההשמה נותנת $O(n^2)$.

סך הכל $\mathrm{time}_M(\langle\varphi\rangle)=O(|\langle\varphi\rangle|^2)$, ו‑$\mathrm{space}_M(\langle\varphi\rangle)=O(|\langle\varphi\rangle|)$ — המכונה כותבת רק את ההשמה.

מעבר לחד‑סרטית. למה בכלל חישבנו מקום? כי אנחנו רוצים חסם על מכונה חד‑סרטית, ולפי סעיף (ב) ברקע (‏[00:10:47], מסירה 11): $\mathrm{time}_{\hat M}\ \le\ O\big(\mathrm{time}_M\cdot \mathrm{space}_M\big)\ =\ O\big(|\langle\varphi\rangle|^2\cdot|\langle\varphi\rangle|\big)\ =\ O\big(|\langle\varphi\rangle|^3\big).$

מסקנה. קיימת מכונה חד‑סרטית אי‑דטרמיניסטית $\hat M$ המכריעה את $\mathrm{SAT}$ באופן אי‑דטרמיניסטי, ולכל נוסחת CNF‏ $\varphi$ מתקיים $\mathrm{time}_{\hat M}(\langle\varphi\rangle)\le O(|\langle\varphi\rangle|^3)$. בפרט $\mathrm{SAT}\in\mathrm{NTime}(n^3)\subseteq\mathrm{NP}$. $\blacksquare$

הערה: בהרצאה החסם נאמר בקיצור ("זה מגיע מזה שזה הספייס כפול הטיים"). הפירוט: אילו היינו משתמשים בחסם הגס $\mathrm{time}_{\hat M}=O(\mathrm{time}_M^2)$ היינו מקבלים $O(|\langle\varphi\rangle|^4)$. החסם דרך המקום הדוק יותר משום שהמכונה חסכנית במקום.

משפט 2: $\mathrm{COMPOSITES}\in\mathrm{NP}$ — ומה הכוח האי‑דטרמיניסטי קונה

זהו המהלך המקביל שנעשה במסירה 10 (‏[00:04:49]–[00:34:29]) במקום $\mathrm{SAT}$. הוא מובא כאן במלואו, גם מפני שהוא דוגמה שנייה בלתי תלויה לאותה תבנית, וגם מפני שהוא המקום היחיד בקורס שבו פונקציית המעברים של מכונה אי‑דטרמיניסטית נכתבת במפורש.

נגדיר $A=\{x\in\{0,1\}^*\mid x \text{ is a binary encoding of a composite number}\}.$

נקודת המוצא: כמה עולה הפתרון הדטרמיניסטי הנאיבי? האלגוריתם המתבקש עובר על כל המספרים בין $2$ ל‑$x-1$ ומנסה לחלק. מספר המחלקים שיש לנסות הוא בסדר גודל $x$ עצמו — אבל $x$ מתקבל בקידוד בינרי, כלומר $x\approx 2^{|x|}$. לכן ביחס לאורך הקלט זמן הריצה הוא $O(2^{|x|})$, ואם מוסיפים גם את עלות כל חילוק ($O(|x|^2)$ בכפל/חילוק ארוך) — עוד יותר. זה אקספוננציאלי באורך הקלט, לא פולינומי.

הערה: שני סטודנטים חידדו כאן נקודות אמיתיות (‏[00:11:41] ו‑[00:12:11], מסירה 10). הראשון שאל למה זה $2^{|x|}$ ולא $x$ — התשובה היא שהמדד תמיד נמדד ביחס לאורך הקלט: כדי לכתוב מיליון די בכ‑20 ביטים, ולכן מיליון פעולות הן $\approx 2^{20}$ פעולות ביחס לקלט באורך 20. השני שאל מה עם עלות החילוק עצמו — ואכן צריך להוסיף אותה, אך היא זניחה ביחס למספר האיטרציות ואינה משנה את המסקנה. המרצה ציין גם ([00:08:00]) שקיים אלגוריתם דטרמיניסטי פולינומי לבעיה, תוצאה מלפני כ‑20 שנה, אך הוא מסובך מאוד ואינו הנושא כאן.

המכונה האי‑דטרמיניסטית. נגדיר מכונה אי‑דטרמיניסטית $N$ בעלת ארבעה סרטים. על קלט $x$ (על הסרט הראשון):

1. כתוב באופן אי‑דטרמיניסטי על הסרט השני מספר $a$ באורך לכל היותר $|x|$.
2. כתוב באופן אי‑דטרמיניסטי על הסרט השלישי מספר $b$ באורך לכל היותר $|x|$.
3. אם $a\le 1$ או $a\ge x$ או $b\le 1$ או $b\ge x$ — דחה.
4. חשב את $a\cdot b$ על הסרט הרביעי.
5. אם $a\cdot b=x$ — קבל; אחרת — דחה.

שוב, כמו במכונה של $\mathrm{SAT}$: שלבים 1–2 אי‑דטרמיניסטיים, שלבים 3–5 דטרמיניסטיים לחלוטין (‏[00:24:22], מסירה 10).

איך נראה שלב 1 ברמת $\delta$? זהו הפירוט שהמרצה נתן פעם אחת ואמר שלא נחזור עליו (‏[00:20:04]–[00:23:49], מסירה 10). נניח שהמכונה במצב $q_1$ והראש על הסרט הראשון קורא $0$ או $1$. אז ל‑$\delta(q_1,\cdot)$ יש שלוש אפשרויות:

• לכתוב $0$ על הסרט השני, להישאר ב‑$q_1$, ולהזיז את שני הראשים ימינה;
• לכתוב $1$ על הסרט השני, להישאר ב‑$q_1$, ולהזיז את שני הראשים ימינה;
• להחליט שסיימנו לכתוב, ולעבור ל‑$q_2$ (שם הראשים מוחזרים לתחילת הסרטים ומתחיל שלב 2).

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

נכונות. ננסח כשרשרת של "אם ורק אם" (‏[00:29:41]–[00:31:17], מסירה 10): $x\in A \iff x \text{ is composite} \iff \exists a,b \text{ with } 1<a,b<x \text{ and } a\cdot b=x \iff \exists \text{ an accepting run of } N \text{ on } x.$ השוויון האחרון הוא בדיוק בנייתה של $N$: היא בוחרת שני מספרים בטווח ובודקת את המכפלה, וזה המקרה היחיד שבו היא מקבלת. בכיוון אחד: אם $x$ פריק, קיימים $a,b$ כאלה, ולכן קיימת ריצה שבה $N$ בוחרת בדיוק אותם ומקבלת. בכיוון השני: אם קיימת ריצה מקבלת, אז בריצה זו נכתבו $a,b$ שעברו את בדיקת שלב 3 ומקיימים $ab=x$, ולכן $x$ פריק.

הערה מתודית מההרצאה (‏[00:31:17], מסירה 10): כשהשקילות נובעת ישירות מההגדרה מותר לכתוב אותה כשרשרת "אם ורק אם" כזו; בבעיות מורכבות יותר עדיף לפצל ולהוכיח כל כיוון בנפרד. שימו לב שגם כאן, כמו במשפט 4 בהמשך, שני הכיוונים נחוצים.

ניתוח זמן ומקום. יהי $x$ קלט, $n=|x|$.

• שלב 1: לכל היותר $n$ צעדים (חסמנו את אורך $a$ ב‑$n$).
• שלב 2: לכל היותר $n$ צעדים, ובנוסף החזרת הראשים — $O(n)$.
• שלב 3: השוואות בין מספרים באורך $\le n$ — $O(n)$.
• שלב 4: כפל ארוך של שני מספרים בני $n$ ביטים — $O(n^2)$: צריך להכפיל כל ספרה בכל אחת מהאחרות ולסכום.
• שלב 5: השוואה אחת — $O(n)$.

סך הכל $\mathrm{time}_N(x)=O(n^2)$. המקום: הסרטים מחזיקים את $x$, את $a$, את $b$ ואת המכפלה שאורכה $\le 2n$ — לכן $\mathrm{space}_N(x)=O(n)$.

מכיוון ש‑$\mathrm{time}_N(x)$ חסום, בפרט כל ריצה עוצרת — התנאי הראשון בהגדרת ההכרעה מתקיים "בחינם" מתוך חסם הזמן (‏[00:29:10], מסירה 10).

מעבר לחד‑סרטית. $N$ היא רב‑סרטית, ואילו הגדרת $\mathrm{NTime}$ נוסחה למכונה סטנדרטית. לפי סעיף (ב) ברקע: $\mathrm{time}_{\hat N}(x)\ \le\ O\big(\mathrm{space}_N(x)\cdot\mathrm{time}_N(x)\big)=O(n\cdot n^2)=O(n^3).$

מסקנה. $A\in\mathrm{NTime}(n^3)\subseteq\mathrm{NP}$. $\blacksquare$

מה הרווחנו. דטרמיניסטית‑נאיבית: $2^{\Theta(n)}$. אי‑דטרמיניסטית: $O(n^3)$. במקום לעבור על כל המחלקים האפשריים, המכונה בוחרת אחד ובודקת רק אותו; מספיק שתהיה אפשרות לבחור נכון (‏[00:13:14], מסירה 10).

אזהרה מהמרצה (‏[00:37:36], מסירה 10): המודל האי‑דטרמיניסטי הוא מודל פיקטיבי. אין דבר כזה מכונה אי‑דטרמיניסטית במציאות; זהו כלי להבנת הקושי של בעיות. ההגדרה השקולה שנוכיח מיד היא זו שנותנת ל‑$\mathrm{NP}$ משמעות ממשית.

משפט 3 (למת נרמול): אפשר להניח שתי אפשרויות בכל מעבר

טענה. לכל מכונה אי‑דטרמיניסטית $N$ קיימת מכונה אי‑דטרמיניסטית מנורמלת $\hat N$ (כלומר $|\hat\delta(q,\alpha)|\le 2$ לכל $q,\alpha$) כך ש:

1. לכל $x$: קיימת ריצה מקבלת של $N$ על $x$ אם ורק אם קיימת ריצה מקבלת של $\hat N$ על $x$ (שקילות סמנטית);
2. לכל $x$: $\ \mathrm{time}_{\hat N}(x)=O\big(\mathrm{time}_{N}(x)\big)$.

הבנייה (‏[00:57:43]–[01:07:23], מסירה 10). נתבונן במעבר של $N$ שבו יש $k$ אפשרויות: $\delta(q,\alpha)=\big\{(q_{i_1},\beta_1,d_1),\ (q_{i_2},\beta_2,d_2),\ \dots,\ (q_{i_k},\beta_k,d_k)\big\}.$ נחליף אותו ב‑$k$ מעברים בינאריים, בעזרת מצבי עזר חדשים $q^{(2)},q^{(3)},\dots,q^{(k)}$: $\hat\delta(q,\alpha)=\big\{(q_{i_1},\beta_1,d_1),\ (q^{(2)},\alpha,S)\big\},$ $\hat\delta(q^{(2)},\alpha)=\big\{(q_{i_2},\beta_2,d_2),\ (q^{(3)},\alpha,S)\big\},\quad\dots$ $\hat\delta(q^{(k)},\alpha)=\big\{(q_{i_k},\beta_k,d_k)\big\}.$ כאן $S$ פירושו "אל תזיז את הראש ואל תשנה את התו" — מעבר שמטרתו היחידה היא לדחות את ההחלטה. במילים: בכל שלב המכונה נשאלת שאלה בינרית — "לבצע את האפשרות הנוכחית, או לעבור למצב שאומר 'עכשיו תבחר מבין הנותרות'?" — וכך מצטמצם מספר האפשרויות באחת בכל פעם, עד שבמצב האחרון נותרת אפשרות יחידה.

נכונות (סעיף 1). לכל $q,\alpha$ ולכל $j\le k$: $(q_{i_j},\beta_j,d_j)\in\delta(q,\alpha) \iff \text{there is a choice sequence in } \hat N \text{ from } q \text{ ending in } (q_{i_j},\beta_j,d_j),$ כלומר הסדרה $(q^{(2)},\alpha,S),(q^{(3)},\alpha,S),\dots,(q^{(j)},\alpha,S)$ ואז $(q_{i_j},\beta_j,d_j)$. מכיוון שמצבי העזר אינם משנים את הסרט ואינם מזיזים את הראש, הקונפיגורציה בסוף השרשרת הזו זהה לקונפיגורציה שאליה $N$ מגיעה בצעד יחיד. באינדוקציה על מספר הצעדים: לכל ריצה של $N$ על $x$ מתאימה ריצה של $\hat N$ העוברת באותן קונפיגורציות (עם קונפיגורציות ביניים), ולהפך. בפרט קיימת ריצה מקבלת ב‑$N$ אם ורק אם קיימת ב‑$\hat N$.

חשבון הזמן (סעיף 2). על כל צעד יחיד של $N$, המכונה $\hat N$ מבצעת לכל היותר $k$ צעדים, כאשר $k=|\delta(q,\alpha)|$. נחסום את $k$: כל אפשרות היא שלשה מתוך $Q\times\Gamma\times\{L,R\}$, ולכן $k\ \le\ |Q|\cdot|\Gamma|\cdot 2 .$ זהו קבוע התלוי רק ב‑$N$ ולא ב‑$x$ (‏[01:08:28]–[01:10:40], מסירה 10). לכן $\mathrm{time}_{\hat N}(x)\ \le\ 2|Q||\Gamma|\cdot \mathrm{time}_{N}(x)\ =\ O\big(\mathrm{time}_{N}(x)\big).\qquad\blacksquare$

הערה: בהרצאה נאמר במפורש שזו אינה הוכחה פורמלית מלאה אלא בנייה מלווה בהסבר (‏[01:04:09] ו‑[01:11:42], מסירה 10). הפירוט כאן — הניסוח המדויק של $\hat\delta$, טענת ההתאמה בין סדרות בחירה, האינדוקציה, וחסם $k\le 2|Q||\Gamma|$ — הוא ההשלמה. הבנייה עצמה, כולל מצבי העזר וחסם מספר השלשות, נאמרה בהרצאה.

מדוע זה משתלם. אחרי הנרמול, כדי לתאר ריצה מספיק ביט אחד לכל צעד, ולא שלשה שלמה. זה מה שמאפשר במשפט 4 לקחת $|w|=p(|x|)$ בדיוק, ולא $(\lceil\lg|Q|\rceil+\lceil\lg|\Gamma|\rceil+1)\cdot p(|x|)$. חשוב מכך: בקידוד הביטים, כל מחרוזת $w$ מתארת ריצה חוקית, ולכן המוודא אינו צריך כלל לבדוק חוקיות — הוא רק מריץ.

משפט 4 (המשפט המרכזי): $\mathrm{NP}=\mathrm{NP}'$

ניסוח. תהא $A$ שפה. אזי $A\in \mathrm{NP}$ אם ורק אם קיימים פולינומים $p,q$ ומכונה דטרמיניסטית $M$ כך ש:

1. לכל קלט $a$: $\ \mathrm{time}_M(a)\le p(|a|)$;
2. לכל $x$: $\ x\in A \iff \exists w\in\{0,1\}^{q(|x|)}$ שעבורו $M$ מקבלת את $(x,w)$.

הערה מקדימה. ב‑(1)–(2) המכונה $M$ היא דטרמיניסטית, בניגוד להגדרה המקורית של $\mathrm{NP}$ שבה המכונה אי‑דטרמיניסטית. זה כל העניין: המשפט מחליף אי‑דטרמיניזם בעזרה חיצונית קצרה. (בסיכום זו הערה בכחול בשולי עמוד 2.) שימו לב גם ש‑(1) חוסם את זמן הריצה באורך הקלט המלא של $M$ — כלומר $|x|+|w|$ — ולא ב‑$|x|$ (‏[01:14:20], מסירה 10).

כיוון א': מ‑verifier ל‑$\mathrm{NP}$ (אם קיימים $p,q,M$ כנ"ל, אז $A\in \mathrm{NP}$)

הבנייה. נניח שקיימים $p,q,M$ המקיימים (1) ו‑(2). נבנה מכונה אי‑דטרמיניסטית $\hat M$. שימו לב ש‑$\hat M$ "מחזיקה את $M$ בבטן" — $M$ ידועה בזמן הבנייה ואינה חלק מהקלט (‏[00:30:03], מסירה 11). על קלט $x$:

1. $\hat M$ מחשבת את $q(|x|)$.
2. $\hat M$ כותבת מחרוזת $w\in\{0,1\}^{q(|x|)}$ באופן אי‑דטרמיניסטי, על הסרט מיד אחרי $x$.
3. $\hat M$ מריצה את $M$ על $(x,w)$ ומחזירה את אותה תשובה.

זה בדיוק מה שעשו שתי המכונות שראינו: ג'נרוט אובייקט באופן אי‑דטרמיניסטי, ואחריו בדיקה דטרמיניסטית (‏[00:28:30], מסירה 11; ‏[01:24:07], מסירה 10). שלב 3 חוקי משום שמכונה אי‑דטרמיניסטית תמיד יכולה להריץ מכונה דטרמיניסטית — כל מכונה דטרמיניסטית היא בפרט אי‑דטרמיניסטית עם אפשרות יחידה בכל מעבר (‏[01:22:00], מסירה 10).

נכונות: $\hat M$ מכריעה את $A$ באופן אי‑דטרמיניסטי. יהי $x$.

אם $x\in A$: מתנאי (2), בכיוון "רק אם", קיימת $w\in\{0,1\}^{q(|x|)}$ כך ש‑$M$ מקבלת את $(x,w)$. מכיוון ששלב 2 כותב מחרוזת שרירותית באורך $q(|x|)$, קיימת ריצה אפשרית של $\hat M$ על $x$ שבה נכתבת בדיוק אותה $w$. בריצה זו שלב 3 מריץ את $M$ על $(x,w)$, מקבל "קבל", ולכן $\hat M$ מקבלת.

אם $x\notin A$: מתנאי (2), בכיוון "אם", אף $w\in\{0,1\}^{q(|x|)}$ אינה גורמת ל‑$M$ לקבל את $(x,w)$ — כלומר לכל $w$ המכונה $M$ דוחה. תהא ריצה אפשרית כלשהי של $\hat M$ על $x$, ותהא $w$ המחרוזת שנכתבה בה בשלב 2. שלב 3 מריץ את $M$ על $(x,w)$, מקבל "דחה", ומחזיר אותה תשובה. לכן כל ריצה אפשרית של $\hat M$ דוחה.

הערה: כאן הנקודה שהמרצה עצר עליה במפורש (‏[00:32:17]–[00:33:49], מסירה 11): תנאי (2) הוא אם ורק אם, ובהוכחה משתמשים בשני הכיוונים שלו — באחד כדי לייצר ריצה מקבלת כש‑$x\in A$, ובשני כדי לשלול ריצה מקבלת כש‑$x\notin A$. אילו (2) היה גרירה חד‑כיוונית בלבד, $\hat M$ הייתה עלולה לקבל קלטים שאינם ב‑$A$. שתי המסירות מנסחות את הכיוון השני אחרת: מסירה 11 עושה זאת בשלילה (נניח שקיימת ריצה מקבלת, ונגיע לסתירה), ומסירה 10 ישירות (‏[01:33:36]). שתי הגרסאות תקפות; הגרסה הישירה מובאת למעלה, וגרסת השלילה שקולה לה.

לכן $\hat M$ מכריעה את $A$ באופן אי‑דטרמיניסטי.

ניתוח יעילות. יהי $x$, ונסמן $n=|x|$.

• שלב 1 דורש $O(q(n))$ צעדים. הנימוק: $q$ הוא פולינום, וכל פונקציה אלמנטרית כזו היא ישימה בזמן — ניתנת לחישוב בזמן מסדר הגודל של ערכה (‏[00:35:56], מסירה 11; ‏[01:26:09], מסירה 10).
• שלב 2 דורש בדיוק $q(n)$ צעדים: המכונה רק רושמת $q(n)$ ביטים, ביט אחד לצעד.
• שלב 3 דורש $\mathrm{time}_M\big((x,w)\big)\le p\big(|(x,w)|\big)$ לפי תנאי (1). הקידוד של הזוג הוא שרשור של $x$ ואחריו $w$ (עד כדי תו מפריד קבוע), ולכן $|(x,w)|=|x|+|w|=n+q(n)$, ומכאן $\mathrm{time}_M\big((x,w)\big)\ \le\ p\big(n+q(n)\big).$

סך הכל, אם נגדיר $\tilde p(n)=O(q(n))+q(n)+p\big(n+q(n)\big)$, אז $\mathrm{time}_{\hat M}(x)\le \tilde p(n)$. פולינומים סגורים תחת סכום, מכפלה והרכבה (‏[00:38:03], מסירה 11; ‏[01:28:51], מסירה 10) — ולכן $\tilde p$ הוא פולינום ב‑$n=|x|$. קיבלנו מכונה אי‑דטרמיניסטית המכריעה את $A$ בזמן פולינומי, כלומר $A\in \mathrm{NP}$. $\blacksquare$

למה סגירות הפולינומים היא לב העניין (‏[01:29:21], מסירה 10). זו אחת הסיבות שמסתכלים דווקא על $\mathrm{P}$ ו‑$\mathrm{NP}$: אלגוריתם פולינומי שמריץ אלגוריתם פולינומי אחר נשאר פולינומי. אין דבר כזה בזמן ליניארי — אלגוריתם ליניארי שמריץ אלגוריתם ליניארי בתוך לולאה כבר ריבועי. כאן זה קריטי: שלב 3 של $\hat M$ הוא בדיוק "הרצת אלגוריתם בתוך אלגוריתם".

למה החישוב עובד רק בגלל ששני החסמים פולינומיים. אילו $q$ היה, נניח, $2^n$ — שלב 2 לבדו היה דורש $2^n$ צעדים. ואילו $p$ לא היה פולינומי — שלב 3 היה הורג אותנו. שני החסמים נכנסים לחישוב, כל אחד במקומו.

כיוון ב': מ‑$\mathrm{NP}$ ל‑verifier (אם $A\in \mathrm{NP}$ אז קיימים $p,q,M$ כנ"ל)

נתון. $A\in \mathrm{NP}$: קיימת מכונה אי‑דטרמיניסטית $N$ ופולינום $p_0$ כך ש‑$N$ מכריעה את $A$ באופן אי‑דטרמיניסטי, ולכל $x$ מתקיים $\mathrm{time}_N(x)\le p_0(|x|)$. איננו יודעים דבר על אופן פעולתה של $N$ — רק את שתי העובדות האלה (‏[01:38:49], מסירה 10).

מה חסר ל‑verifier? הבעיה במכונה אי‑דטרמיניסטית היא בדיוק שהיא עושה בחירות עצמאיות. מכונה דטרמיניסטית שרוצה לדעת אם קיימת ריצה מקבלת חייבת, בלי עזרה, לסרוק עץ ריצות שגודלו אקספוננציאלי. העזרה המינימלית שתפתור לה את הבעיה היא רשימת הבחירות (הגדרה 2, אנלוגיית המבוך). בניסוח של מסירה 10 (‏[01:40:26]): זהו "להוציא את האי‑דטרמיניזם אל מחוץ למכונה" — במקום שהמכונה תבצע בחירות תוך כדי ריצה, היא מקבלת את כל הבחירות מראש, ומאותו רגע היא דטרמיניסטית לחלוטין.

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

דרך I — העד הוא תסריט ריצה מלא (מסירה 11 והסיכום)

אורך התסריט. מספר הצעדים בכל ריצה של $N$ על $x$ חסום ב‑$p_0(|x|)$, ולכן מספר ההחלטות חסום גם הוא ב‑$p_0(|x|)$. כל החלטה היא שלשה $(q,\beta,d)$ הנתונה ב‑$\lceil\lg|Q|\rceil+\lceil\lg|\Gamma|\rceil+1$ ביטים. נסמן $q(n)\;=\;\big(\lceil\lg|Q|\rceil+\lceil\lg|\Gamma|\rceil+1\big)\cdot p_0(n),$ פולינום ב‑$n$, שכן הגורם הראשון קבוע התלוי רק ב‑$N$.

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

1. $M$ מפרשת את $w$ כרשימת שלשות, ומוודאת ש‑$w$ מתאר ריצה חוקית ומקבלת של $N$ על $x$.
2. אם כן — קבל; אחרת — דחה.

מה נבדק בשלב 1? $M$ מסמלצת: מחזיקה את הקונפיגורציה הנוכחית (מצב, תוכן סרט, מיקום ראש), מתחילה מהקונפיגורציה ההתחלתית של $N$ על $x$, וקוראת את השלשות בזו אחר זו. לכל שלשה היא בודקת מול $\delta_N$ שהמעבר המבוקש הוא באמת אחת מהאפשרויות המותרות מהקונפיגורציה הנוכחית, ואם כן — מעדכנת. בסיום היא בודקת שהמצב הסופי ב‑$F$ (‏[00:49:55]–[00:50:25], מסירה 11).

דרך II — העד הוא רצף ביטי בחירה (מסירה 10)

לפי משפט 3 נניח ש‑$N$ מנורמלת: בכל מעבר לכל היותר שתי אפשרויות. (אם לא — נחליף אותה ב‑$\hat N$ מהמשפט, שזמן ריצתה $O(p_0)$, ונקרא לפולינום החדש $p_0$.) כעת די בביט אחד לכל צעד, ולכן נסמן פשוט $q(n)=p_0(n).$

הבנייה. מכונה דטרמיניסטית $M$ בעלת שני סרטים; על קלט $(x,w)$:

1. אתחול: העתק את $w$ אל הסרט השני ומחק אותו מהסרט הראשון, כך שעל הסרט הראשון נשאר רק $x$.
2. סימולציה: סמלץ את ריצת $N$ על $x$; בכל צעד שבו ל‑$N$ יש בחירה בין שתי אפשרויות — אם הראש שעל הסרט השני קורא $0$, בצע את האפשרות הראשונה; אם הוא קורא $1$, בצע את השנייה. בסוף כל צעד הזז את הראש שעל הסרט השני ימינה. החזר את התשובה שאליה הגיעה הסימולציה.

למה זה חוקי. מכונה דטרמיניסטית אינה יכולה "להריץ" מכונה אי‑דטרמיניסטית — הכיוון ההפוך אפשרי, לא זה (‏[01:45:08], מסירה 10). הפתרון: בבנייה הזו אין ל‑$M$ שום בחירה, כי כל בחירה נקבעת מראש על ידי הביט הנוכחי שעל הסרט השני. פורמלית, במקום מעבר אחד עם שתי אפשרויות יש ל‑$M$ שני מעברים דטרמיניסטיים נפרדים, המובחנים לפי התו הנקרא על הסרט השני.

ההבדל המהותי בין שתי הדרכים. בדרך I יש מחרוזות $w$ שאינן מתארות ריצה חוקית כלל, ולכן המוודא חייב לבדוק חוקיות מול $\delta_N$. בדרך II כל $w\in\{0,1\}^{q(|x|)}$ מתארת ריצה חוקית של $N$ — פשוט מפני שכל ביט בוחר בין שתי אפשרויות שקיימות ממילא — ולכן אין מה לבדוק, רק להריץ. זה מה שהלמה של משפט 3 קונה לנו.

נכונות (משותפת לשתי הדרכים)

יהי $x$.

אם $x\in A$: מכיוון ש‑$N$ מכריעה את $A$ אי‑דטרמיניסטית, קיימת ריצה מקבלת של $N$ על $x$. נתבונן בריצה כזו. ראשית נחסום את אורכה: נתון ש‑$\mathrm{time}_N(x)\le p_0(|x|)$, וזהו חסם על הריצה הארוכה ביותר; בפרט מספר הצעדים בריצה המקבלת הספציפית הזו הוא $\le p_0(|x|)$ (‏[01:50:59]–[01:51:34], מסירה 10). לכן מספר הבחירות בה $\le p_0(|x|)$, ורצף הבחירות מתקודד ב‑$w$ באורך $\le q(|x|)$: בדרך I כרצף שלשות, בדרך II כרצף ביטים שבו הביט ה‑$i$ מתאים לבחירה שביצעה $N$ בצעד ה‑$i$ ($0$ לאפשרות הראשונה, $1$ לשנייה). על הקלט $(x,w)$ הסימולציה של $M$ עוברת בדיוק לאורך הריצה הזו ומסתיימת במצב מקבל, ולכן $M$ מקבלת.

אם $x\notin A$: אזי אין ריצה מקבלת של $N$ על $x$ כלל. תהא $w$ כלשהי. בדרך II, $w$ מגדירה ריצה יחידה של $N$ על $x$, ומכיוון שאין ריצה מקבלת — הריצה הזו דוחה, ולכן $M$ דוחה את $(x,w)$. בדרך I, אם $w$ אינה חוקית $M$ תגלה זאת מול $\delta_N$ ותדחה; ואם היא חוקית, היא מתארת ריצה של $N$, שאינה מקבלת, ולכן $M$ תדחה בסוף. בשני המקרים: לכל $w$, המכונה $M$ דוחה.

קיבלנו בדיוק את תנאי (2): $\ x\in A \iff \exists w\in\{0,1\}^{q(|x|)}$ שעבורה $M$ מקבלת את $(x,w)$.

הערה: המרצה במסירה 10 עצר כאן באמצע ותיקן את עצמו בקול (‏[01:56:24]–[01:57:25]): הוא הוכיח את שני הכיוונים אך לא סגר במפורש את המסקנה "ולכן $x\in A$", ואמר "אולי צריך להוסיף — זה מקור הבלבול". הניסוח שלמעלה סוגר את השרשרת במפורש.

שאלה מהכיתה: מה מבטיח שהסימולציה תסתיים לפני ש‑$w$ ייגמר? (‏[01:59:30]–[02:01:38], מסירה 10)

זו השאלה הטובה ביותר שנשאלה בשיעור. אם $M$ מתקדמת ביט אחד לכל צעד סימולציה, מה מונע מצב שבו הריצה המסומלצת עוד לא הסתיימה ו‑$w$ כבר אזל?

התשובה: החסם $\mathrm{time}_N(x)\le p_0(|x|)$ הוא חסם על הריצה הארוכה ביותר של $N$ על $x$ — כלומר על כל ריצה, ולא משנה אילו בחירות בוצעו. לכן, יהיה $w$ אשר יהיה, הסימולציה עוצרת אחרי $\le p_0(|x|)$ צעדים, וזה בדיוק אורך $w$. שימו לב שהתשובה אינה נשענת על כך ש‑$M$ מקבלת, ואינה נשענת על מבנה כלשהו של $N$ — היא נובעת אך ורק מהנתון על זמן הריצה. (סטודנטית אחרת הציעה שהדבר נובע מכך שהמכונה עוצרת במצב מקבל; זו אינה התשובה, כי היא לא הייתה מכסה ריצות דוחות.)

ניתוח יעילות

נעשה אותו לפי דרך II, שבה הוא נקי יותר. יהיו $x$ ו‑$w$.

• שלב 1 (העתקת $w$ לסרט השני): מעבר אחד על הקלט — $O(|x|+|w|)$ צעדים.
• שלב 2 (הסימולציה): לכל היותר $\mathrm{time}_N(x)\le p_0(|x|)$ צעדי סימולציה, וכל צעד עולה מספר קבוע של פעולות (קריאת ביט, התייעצות בטבלת $\delta_N$, עדכון, הזזת שני הראשים).

נגדיר $Q(n)=n+p_0(n)$ — פולינום. אז $\mathrm{time}_M\big((x,w)\big)\ \le\ O\big(|x|+|w|\big)+p_0(|x|)\ \le\ O\big(Q(|x|+|w|)\big),$ כאשר המעבר האחרון הוא חסם מלמעלה גס אך תקף: החלפנו $p_0(|x|)$ ב‑$p_0(|x|+|w|)$, מה שרק מגדיל (‏[02:03:43]–[02:04:13], מסירה 10). כלומר זמן הריצה של $M$ פולינומי באורך הקלט שלה, כנדרש בתנאי (1).

לבסוף, $M$ היא דו‑סרטית; לפי סעיף (ב) ברקע קיימת חד‑סרטית שקולה שזמן ריצתה חסום ב‑$O(Q^2)$ — עדיין פולינום. לכן קיימים $p$ (נניח $p=O(Q^2)$) ו‑$q$ ומכונה דטרמיניסטית המקיימים (1) ו‑(2), כלומר $A\in\mathrm{NP}'$. $\blacksquare$

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

מכיוון ששני הכיוונים הוכחו, $\mathrm{NP}=\mathrm{NP}'$. $\blacksquare$

מבט לאחור: $\mathrm{SAT}$ ו‑$\mathrm{COMPOSITES}$ כמקרים פרטיים. אם מפעילים את כיוון ב' על המכונה של $\mathrm{SAT}$ ממשפט 1, מקבלים verifier שהעד שלו הוא תסריט הריצה המלא. אבל למכונה ההיא מבנה מיוחד — האי‑דטרמיניזם מרוכז כולו בשלב 2 — ולכן כל הבחירות שמחוץ לשלב 2 נקבעות ביחידות ואפשר להשמיטן. מה שנשאר מהתסריט הוא בדיוק $n$ הביטים של ההשמה. באותו אופן בדיוק, במכונה של $\mathrm{COMPOSITES}$ נשארים מהתסריט רק הביטים של $a$ ושל $b$. זו הסיבה שהעד ה"טבעי" הוא ההשמה או זוג הגורמים, ולא היסטוריית החישוב: התסריט הוא הבנייה הכללית, וההשמה היא הדחיסה שלה במקרה הפרטי.

משפט 5: שני החסמים הכרחיים

(א) ויתור על החסם $q$ על אורך העד מוריד את ההגדרה ל‑$\mathrm{RE}$. נגדיר: $A\in\mathcal{C}$ אם קיימת מכונה דטרמיניסטית $M$ הרצה בזמן פולינומי באורך כל הקלט שלה, כך ש‑$A=\{x\mid \exists w\in\{0,1\}^*: M \text{ accepts } (x,w)\}$, ללא כל חסם על $|w|$. אזי $\mathcal{C}=\mathrm{RE}$.

הוכחה. ($\subseteq$) בהינתן $M$ כזו, המכונה שעל $x$ עוברת על כל $w\in\{0,1\}^*$ בסדר לקסיקוגרפי ומריצה את $M(x,w)$, עוצרת ומקבלת ברגע שנמצאה $w$ מקבלת, מזהה את $A$; לכן $A\in \mathrm{RE}$. ($\supseteq$) תהא $A\in \mathrm{RE}$ ותהא $N$ מכונה המזהה אותה. נגדיר $M(x,w)$ שמקבלת אם ורק אם $w$ מקודדת חישוב מקבל של $N$ על $x$ — בדיקה פולינומית באורך $|x|+|w|$, בדיוק כמו בכיוון ב'. אם $x\in A$ אז $N$ עוצרת ומקבלת ולכן קיים $w$ כזה; אם $x\notin A$ אין חישוב מקבל ולכן אין $w$. $\blacksquare$

זהו בדיוק המשפט מקורס החישוביות: $A\in \mathrm{RE}$ אם ורק אם קיים פרדיקט דו‑מקומי כריע $f$ כך ש‑$A=\{x\mid \exists t:\ f(x,t)=1\}$. הקשר הזה עלה בשתי המסירות באופן בלתי תלוי — במסירה 11 המרצה הצביע עליו מיוזמתו (‏[00:22:11]), ובמסירה 10 סטודנט שאל עליו ישירות (‏[00:43:55]). התשובה שם: "זה בדיוק אותו משפט אפיון, עד כדי כך ששם לא דיברנו על זמן ריצה… ב‑$\mathrm{RE}$ הייתה לנו עדות לא מוגבלת באורך; כאן אורך העדות צריך להיות פולינומי, כי אני לא מאפשר הוכחות ארוכות מדי — אם כן, רק לקרוא אותה היה לוקח זמן אקספוננציאלי" (‏[00:44:26], מסירה 10). כלומר ההבדל היחיד בין האפיון של $\mathrm{RE}$ לבין האפיון של $\mathrm{NP}$ הוא שני החסמים הפולינומיים.

(ב) ויתור על החסם $p$ על זמן האימות מנפח את המחלקה. אם נדרוש $|w|=q(|x|)$ פולינומי אך נרשה ל‑$M$ לרוץ בזמן $2^{|x|^k}$, המחלקה המתקבלת מכילה את $\mathrm{EXP}$ במלואה: קחו $q\equiv 0$ (עד ריק) והריצו את המכריע האקספוננציאלי ישירות. מכיוון ש‑$\mathrm{P}\subsetneq\mathrm{EXP}$ ממשפט היררכיית הזמן, זו בבירור אינה המחלקה שביקשנו לאפיין.

המסקנה. ההגדרה חייבת את שני החסמים בו‑זמנית: העד קצר, והבדיקה מהירה.

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

דוגמה 1: מעקב מלא אחרי המכונה של $\mathrm{SAT}$

תהא הנוסחה (משוחזרת; המרצה שרטט נוסחה בת חמישה משתנים על הלוח, [00:06:34], מסירה 11) $\varphi=(x_1\vee\neg x_2\vee x_3)\wedge(\neg x_1\vee x_4)\wedge(x_2\vee\neg x_5)\wedge(x_3\vee x_5).$

שלב 1 (דטרמיניסטי). סריקה וספירה: חמישה משתנים, $n=5$.

שלב 2 (אי‑דטרמיניסטי). כתיבת חמישה ביטים על הסרט השני. יש $2^5=32$ ריצות אפשריות.

ריצה מקבלת. נניח שנכתב $w=01101$, כלומר $x_1=0,\ x_2=1,\ x_3=1,\ x_4=0,\ x_5=1$ — הביט ה‑$i$ הוא הערך של $x_i$ (‏[00:07:06], מסירה 11).

• פסוקית 1: $x_1=0$, $\neg x_2=0$, $x_3=1$ ⟶ מסופקת.
• פסוקית 2: $\neg x_1=1$ ⟶ מסופקת.
• פסוקית 3: $x_2=1$ ⟶ מסופקת.
• פסוקית 4: $x_3=1$ ⟶ מסופקת.

כל הפסוקיות מסופקות, ולכן בריצה זו המכונה מקבלת, ומכאן $\langle\varphi\rangle\in \mathrm{SAT}$.

ריצה דוחה. בריצה שבה נכתב $w=00000$: פסוקית 4 היא $x_3\vee x_5=0\vee 0=0$ — אינה מסופקת, ולכן בריצה זו המכונה דוחה. זה אינו סותר את ההכרעה: להכרעה אי‑דטרמיניסטית מספיקה ריצה מקבלת אחת.

העד. בשפת משפט 4: $w=01101$ הוא העד לשייכות $\langle\varphi\rangle\in \mathrm{SAT}$, והמוודא הוא "הצב את $w$ ב‑$\varphi$ וחשב".

דוגמה 2: אותו מופע דרך תסריט ריצה (הכיוון ההפוך)

נפעיל את דרך I של כיוון ב' על המכונה של $\mathrm{SAT}$ ועל אותו $\varphi$. תסריט הריצה של הענף המקבל הוא רצף השלשות $(q,\beta,d)$ של כל הצעדים: ראשית $O(|\langle\varphi\rangle|)$ שלשות של שלב הספירה — כולן קבועות, כי השלב דטרמיניסטי; אחריהן חמש שלשות שבהן התו הנכתב הוא $0,1,1,0,1$ בהתאמה — אלה השלשות היחידות שבהן הייתה בחירה; ואחריהן $O(|\langle\varphi\rangle|^2)$ שלשות של שלב הבדיקה, גם הן קבועות. המוודא מקבל את השרשור כ‑$w$, מסמלץ שלשה‑שלשה מול $\delta$, ורואה שהריצה חוקית ומסתיימת במצב מקבל.

בדרך II התמונה נקייה יותר: אחרי הנרמול, הביטים היחידים שיש בהם אינפורמציה הם חמשת הביטים $01101$ — בדיוק העד מדוגמה 1. שאר הצעדים דטרמיניסטיים ולכן הביט שלהם נקבע ביחידות.

דוגמה 3: $8$ הוא פריק — מקצה לקצה בשני המודלים

במודל האי‑דטרמיניסטי (משפט 2). קלט $x=1000_2$ (כלומר 8), $|x|=4$.

• שלב 1: המכונה כותבת באופן אי‑דטרמיניסטי מספר באורך $\le 4$. באחת הריצות היא כותבת $a=10_2=2$.
• שלב 2: באותה ריצה היא כותבת $b=100_2=4$.
• שלב 3: בדיקה — $2>1$, $2<8$, $4>1$, $4<8$: עוברת.
• שלב 4: כפל ארוך — $2\cdot 4=8=1000_2$.
• שלב 5: השוואה ל‑$x$: שווה ⟶ קבל.

בריצה אחרת המכונה כותבת $a=3,b=5$: שלב 5 מגלה $15\ne 8$ ⟶ דוחה. בריצה שלישית $a=1$: שלב 3 דוחה מיד. אין בכך פגם — קיימת ריצה מקבלת, ולכן $8\in A$.

לעומת זאת עבור $x=7$: כל זוג $a,b$ עם $1<a,b<7$ מקיים $ab\ne 7$, ולכן כל ריצה דוחה, ובצדק $7\notin A$.

במודל המוודא (הגדרה 1). העד הוא $w$ באורך $2|x|$, המפורש כשני מספרים $a,b$ בני $|x|$ ביטים כל אחד. עבור $x=8$: $w=0010\,0100$, כלומר $a=2,b=4$. המוודא (1) בודק ש‑$1<a<x$ ו‑$1<b<x$; (2) מחשב $a\cdot b$; (3) משווה ל‑$x$. שתיים ראשונות $O(|x|)$, הכפל $O(|x|^2)$ — פולינומי. הפולינום שמגביל את אורך העד הוא $q(n)=2n$ (‏[00:50:45], מסירה 10). לכן $A\in\mathrm{NP}'$, וממשפט 4 גם $A\in\mathrm{NP}$ — הפעם בלי לבנות NTM כלל.

תיקון: בהקלטה, בגרסת המוודא, המרצה תיאר רק את הכפל וההשוואה והשמיט את בדיקת הטווח $1<a,b<x$ (‏[00:49:43]–[00:50:15], מסירה 10). בלעדיה העד $w=(1,x)$ היה מתקבל עבור כל $x$, וכל מספר היה נראה פריק. הבדיקה כן מופיעה בגרסת ה‑NTM של אותה הרצאה (שלב 3, [00:17:29]), ולכן ברור שמדובר בהשמטה בעל פה. הוחזרה כאן.

דוגמה 4 (תוספת עורך): $\mathrm{CLIQUE}$

$\mathrm{CLIQUE}=\{\langle G,k\rangle\mid G \text{ contains a clique of size } k\}$. העד הוא רשימת $k$ קודקודים; אורכה $O(k\log|V|)$ — פולינומי בקלט. האימות: לוודא שכל הקודקודים שונים, שיש בדיוק $k$ מהם, ושכל אחד מ‑$\binom{k}{2}$ הזוגות הוא קשת ב‑$G$ — $O(k^2)$ בדיקות. לכן $\mathrm{CLIQUE}\in \mathrm{NP}$. הדוגמה מובאת כתרגול נוסף לתבנית "עד + אימות" ולא נאמרה באף אחת מהמסירות.

תרגיל: המבוך כמודל (‏[00:41:16], מסירה 11)

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

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

תרגיל: נרמול מכונה עם 10 אפשרויות (‏[00:58:15]–[01:00:22], מסירה 10)

השאלה שהמרצה שאל את הכיתה: נתון מעבר של מכונה אי‑דטרמיניסטית שבו יש 10 אפשרויות. איך מגדירים מכונה שקולה שבה לכל מעבר לכל היותר שתי אפשרויות?

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

הפתרון המלא. מפצלים את השאלה "בחר אחת מתוך 10" ל‑10 שאלות בינאריות שרשוריות: "האם לבצע את האפשרות הראשונה, או לעבור למצב שאומר 'בחר אחת מתוך התשע הנותרות'?" — וכן הלאה, עד שבמצב האחרון נשארת אפשרות יחידה. זו בדיוק הבנייה של משפט 3. המחיר: על כל צעד מקורי מבצעים לכל היותר $k\le 2|Q||\Gamma|$ צעדים — קבוע שאינו תלוי בקלט, ולכן זמן הריצה גדל לכל היותר בגורם קבוע.

שאלה מהכיתה: האם זה כמו fixer? (‏[00:33:49], מסירה 11)

השאלה: תנאי (2) נראה כמו הפעלת מכונה על שני ארגומנטים, כמו העיקרון של נקודת שבת.

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

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

• [00:00:34] מסירה 11 / [00:19:33] מסירה 10 — אל תגידו "מגרילה". שני המרצים, בנפרד, הזהירו מפני המונח. האי‑דטרמיניזם אינו הגרלה, אינו דגימה ואינו אקראיות. המונח "מנחשת" נפוץ אך שניהם ממליצים להימנע ממנו: "הוא עצמו לא טעות, אבל הוא מקרב אתכם לטעות". במסירה 10 סטודנט שאל במפורש "האם זה אומר שהיא לוקחת מספר אקראי?", והתשובה: לא בדיוק — כשמדברים על אקראיות יש גם התפלגות הסתברות על התוצאות, וכאן אין. הניסוח המדויק: המכונה בוחרת או כותבת מחרוזת באופן אי‑דטרמיניסטי.
• [00:01:04] מסירה 11 / [00:24:22] מסירה 10 — איפה בדיוק האי‑דטרמיניזם. בשתי המכונות שראינו הוא מרוכז בשלב אחד בלבד; כל השאר דטרמיניסטי. זו התובנה שממנה נולד כל השיעור.
• [00:02:45] מסירה 11 — $\langle\varphi\rangle$ מול $\varphi$. פורמלית עובדים עם הקידוד, כי שפה היא קבוצת מחרוזות; בראש חושבים על הנוסחה.
• [00:14:17] מסירה 10 — עד כמה מפורט לכתוב מכונה. המרצה כתב את $\delta$ במפורש פעם אחת בכוונה, והדגיש: מכאן והלאה כותבים מכונות ברמת high level ("כתוב באופן אי‑דטרמיניסטי מספר באורך…"), ולא תראו את הכתיבה המפורטת בשום מקום אחר. אבל חשוב לראות אותה פעם אחת כדי להבין שההגדרות באמת עומדות מאחורי הניסוח המקוצר.
• [00:15:35] מסירה 11 — למה זו לא מכונת הכרעה. מכונה שמכריעה את $\mathrm{SAT}$ מקבלת נוסחת CNF ומחזירה true/false. כאן שינינו את צורת הקלט — הוא הפך לזוג — ולכן זו כבר לא מכונת הכרעה אלא מוודא.
• [00:17:43] מסירה 11 / [00:39:10] מסירה 10 — "הגדרה שקולה" היא בעצם משפט. ברגע שמוסרים הגדרה שנייה לאותה מחלקה כבר טוענים טענה. במסירה 10 המרצה נזהר במיוחד וקרא למחלקה החדשה $\mathrm{NP}'$ עד שהוכיח את השוויון.
• [00:26:23] מסירה 11 — ההברקה שמחברת בין שתי ההגדרות. ה"קיים $w$" בהגדרת ה‑verifier מתחבר בדיוק ל"קיימת ריצה אפשרית מקבלת" שבהגדרת ההכרעה האי‑דטרמיניסטית. שני כמתי הקיום הם אותו כמת.
• [00:27:27] מסירה 11 — מה המכונה "מחזיקה בבטן". $\hat M$ מקבלת כקלט רק את $x$; את $M$ היא אינה מקבלת כקלט — היא מקודדת בתוך הגדרתה. הדבר היחיד שחסר לה הוא $w$.
• [00:37:36] מסירה 10 — המודל האי‑דטרמיניסטי פיקטיבי. אין מכונות אי‑דטרמיניסטיות במציאות. ההגדרה עם המוודא היא זו שנותנת ל‑$\mathrm{NP}$ משמעות.
• [00:45:28]–[00:46:32] מסירה 10 — המשמעות הפילוסופית של $\mathrm{P}$ מול $\mathrm{NP}$. $\mathrm{NP}$ היא מחלקת הבעיות שבהן לקלטים בפנים יש עדות משכנעת, ולקלטים בחוץ אין אף עדות — כלומר "אי אפשר להוכיח טענות לא נכונות". לכן השאלה $\mathrm{P}$ מול $\mathrm{NP}$ היא השאלה: האם יש משמעות להוכחות? האם כל דבר שאני יודע לבדוק הוכחה עבורו, אני גם יודע להוכיח בעצמי? האינטואיציה מהעולם היום‑יומי אומרת שקל יותר לבדוק הוכחה מאשר לכתוב אותה — כלומר שמשערים $\mathrm{P}\ne\mathrm{NP}$ — אבל אין לכך הוכחה.
• [01:19:11] מסירה 10 — כיוון הבנייה. סטודנט הציע להפוך כל מצב אי‑דטרמיניסטי ל"סינגלטון". המרצה הבהיר שבכיוון הזה נתונה מכונה דטרמיניסטית ומבקשים לבנות אי‑דטרמיניסטית — ולכן אין מה "לצמצם"; מה שחסר הוא לייצר את $w$. הבלבול טבעי, ושווה לשים לב לו: בכל אחד משני הכיוונים המכונה הנתונה והמכונה הנבנית מתחלפות בתפקידיהן.
• [01:45:08] מסירה 10 — אסימטריה שכדאי לזכור. מכונה אי‑דטרמיניסטית יכולה להריץ מכונה דטרמיניסטית (כל מכונה דטרמיניסטית היא בפרט אי‑דטרמיניסטית). ההפך אינו נכון — ולכן בכיוון ב' חייבים לספק את הבחירות מבחוץ.
• [00:38:34] מסירה 11 / [01:29:21] מסירה 10 — מה נדרש על פולינומים. סכום, מכפלה והרכבה של פולינומים הם פולינום. במסירה 10 המרצה הוסיף שזו אחת הסיבות שמסתכלים דווקא על $\mathrm{P}$ ו‑$\mathrm{NP}$: אלגוריתם פולינומי שמריץ אלגוריתם פולינומי נשאר פולינומי — תכונה שאינה מתקיימת בזמן ליניארי.
• [00:52:39] מסירה 11 — לגבי המבחן והתרגיל. הכיוון $\mathrm{NP}\Rightarrow$ verifier לא נכתב במלואו במסירה 11, והמרצה אמר שיחזרו עליו. הוא ציין שיש שאלה בתרגיל הבית הנשענת על החומר, ושכדי לפתור אותה אין צורך בהוכחה עצמה — צריך את הרעיון של תסריט ריצה ואת ניסוח הטענה. במסירה 10 (‏[02:13:45]) נאמר שבסוף אותו תרגיל יש שתי שאלות שאי אפשר לפתור עד שיילמד הנושא הבא (טכניקת הריפוד).

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

• מקור: הקלטה 12 (0_fFIUnWa4g). הפער: אינה שייכת לשיעור זה כלל — כולה טכניקת הריפוד: $\mathrm{P}=\mathrm{NP}\Rightarrow \mathrm{EXP}=\mathrm{NEXP}$, $E\subseteq \mathrm{PSPACE}\Rightarrow E^2\subseteq \mathrm{PSPACE}$, והמסקנה $E\ne \mathrm{PSPACE}$. ההכרעה: סומנה coverage: none; החומר שייך לשיעור אחר בסדרה.
• מקור: הקלטה 10 (zcCQY3oT40Y) מול הקלטה 11. הפער: שתי המסירות בונות את אותו משפט על שתי דוגמאות שונות לגמרי — מסירה 11 על $\mathrm{SAT}$ (בהמשך לשיעור 5), מסירה 10 על $\mathrm{COMPOSITES}$. אף אחת אינה מזכירה את הדוגמה של השנייה. ההכרעה: שתיהן נכללו במלואן (משפט 1 ומשפט 2), כי כל אחת מדגימה את אותה תבנית בהקשר אחר. הן מאשרות זו את זו: שתיהן מגיעות ל‑$O(n^3)$ באמצעות $\mathrm{time}\cdot\mathrm{space}$, בשתיהן האי‑דטרמיניזם מרוכז בשלב אחד.
• מקור: הקלטה 10, [00:54:26]–[01:11:42]. הפער: למת הנרמול (לכל היותר שתי אפשרויות בכל מעבר, במחיר גורם קבוע) אינה מופיעה בסיכום ואינה מופיעה בהקלטה 11 כלל. ההכרעה: נוספה כמשפט 3 עם הבנייה המלאה, טענת ההתאמה, וחסם $k\le 2|Q||\Gamma|$. היא משנה את חשבון אורך העד בכיוון ב' — ראו הבא.
• מקור: שתי המסירות. הפער: חשבון אורך העד בכיוון $\mathrm{NP}\Rightarrow$ verifier שונה. מסירה 11 והסיכום (עמוד 3): העד הוא תסריט שלשות, $q(n)=(\lg|Q|+\lg|\Gamma|+1)\cdot p_0(n)$. מסירה 10: אחרי נרמול העד הוא ביט אחד לצעד, $q(n)=p_0(n)$. ההכרעה: שתיהן נכונות. הצגנו את שתיהן כ"דרך I" ו"דרך II", כאשר דרך I שומרת על סימון הסיכום ודרך II היא הטיפול העשיר יותר; ההבדל המהותי — שבדרך II כל $w$ מתארת ריצה חוקית ולכן אין מה לוודא — נכתב במפורש.
• מקור: עמוד 3 בסיכום. הפער: נכתב $\lg|Q|+\lg|\Gamma|+1$ ללא חלקים עליונים. ההכרעה: תוקן ל‑$\lceil\lg|Q|\rceil+\lceil\lg|\Gamma|\rceil+1$; מספר ביטים חייב להיות שלם. אין השפעה על הפולינומיות.
• מקור: הקלטה 10, [00:49:43]–[00:50:15]. הפער: בגרסת המוודא ל‑$\mathrm{COMPOSITES}$ המרצה השמיט את בדיקת $1<a,b<x$, ותיאר רק כפל והשוואה. זו שגיאה מתמטית: בלעדיה $w=(1,x)$ מתקבל לכל $x$, וכל מספר נראה פריק. ההכרעה: הבדיקה הוחזרה בגוף הדוגמה. היא מופיעה בגרסת ה‑NTM של אותה הרצאה ([00:17:29]), ולכן ברור שמדובר בהשמטה בעל פה.
• מקור: עמוד 2 בסיכום מול הקלטה 10. הפער: בגוף ההגדרה בסיכום נכתב $w\in\{0,1\}^{q(|x|)}$ (אורך מדויק), ואילו בהערה הכחולה בצד נכתב $A=\{x\mid \exists w\in\{0,1\}^*\dots\}$ (אורך כלשהו). ההבדל אינו קוסמטי: בלי חסם אורך המחלקה היא $\mathrm{RE}$ ולא $\mathrm{NP}$. ההכרעה: הוכרע לטובת האורך המדויק — מסירה 10 מנסחת גם היא "מחרוזת בינרית באורך $p(|x|)$" (‏[00:40:15]), כלומר שני מקורות בלתי תלויים נגד ההערה הכחולה, שהיא קיצור בלתי‑פורמלי. הנקודה עצמה הפכה למשפט 5(א).
• מקור: שתי המסירות. הפער: שמות שני הפולינומים הפוכים. הסיכום ומסירה 11: $p$ = זמן הריצה, $q$ = אורך העד. מסירה 10: $t$ = זמן הריצה, $p$ = אורך העד. ההכרעה: אומץ סימון הסיכום לאורך כל הקובץ; ההבדל מתועד כאן וב‑open_questions כדי שקורא שיאזין להקלטה 10 לא יתבלבל.
• מקור: הקלטה 11, [00:51:00]. הפער: הכיוון $\mathrm{NP}\Rightarrow$ verifier נמסר שם כ"רעיון הוכחה" בלבד. ההכרעה: הפער נסגר לגמרי על ידי מסירה 10, שמוסרת את הכיוון הזה במלואו — הבנייה הדו‑סרטית, שני כיווני הנכונות, וניתוח הזמן (‏[01:37:48]–[02:05:50]). מה שהיה בגרסה הקודמת של הקובץ שחזור עורך הוא כעת חומר מוקלט.
• מקור: שני המקורות. הפער: בדרך I אף אחד מהם אינו מטפל בפער שבין "ריצה מקבלת עשויה להיות קצרה מ‑$p_0(|x|)$" לבין הדרישה $|w|=q(|x|)$ בדיוק. ההכרעה: בדרך II הבעיה נעלמת — הסימולציה פשוט עוצרת, והביטים הנותרים אינם נקראים, וזו בדיוק תשובת המרצה לשאלת הסטודנט ב‑[01:59:30]. בדרך I מרפדים את התסריט לאורך $q(|x|)$ ומגדירים את המוודא לעצור ולקבל ברגע שהסימולציה הגיעה למצב מקבל. הניסוח $|w|\le q(|x|)$ שקול.
• מקור: הקלטה 11, [00:06:34]. הפער: הנוסחה הקונקרטית בת חמישה המשתנים נכתבה על הלוח ואינה נשמעת. ההכרעה: נבדק גם מול מסירה 10 — שאינה עוסקת ב‑$\mathrm{SAT}$ כלל ולכן אינה יכולה לסייע. הנוסחה נותרת שחזור: נבחרה נוסחת CNF בת חמישה משתנים שההשמה $01101$ שנאמרה בהקלטה אכן מספקת אותה.
• מקור: משפט 5, סעיף (א). הפער: בגרסה הקודמת של הקובץ סומן כתוספת עורך. ההכרעה: מסירה 10 מאשרת אותו — סטודנט שאל ישירות על הקשר לאפיון $\mathrm{RE}$ והמרצה אישר שזה "בדיוק אותו משפט אפיון", והסביר במפורש שחסם אורך העד הוא ההבדל (‏[00:43:55]–[00:44:56]). התיוג שונה מ"תוספת" ל"מבוסס מקור". סעיף (ב) נותר הרחבת עורך.
• מקור: כל מקורות השיעור. הפער: רביעיית המכונה אינה נכתבת במפורש באף אחד מהם, ובפרט מצב ההתחלה אינו מופיע. ההכרעה: אומצה הצורה המחייבת של הסדרה, $M=(Q,q_{start},F,\Sigma,\Gamma,\delta)$, והמצבים המקבלים מסומנים $F$ במקום $q_{acc}$.
• מקור: עמוד 4 בסיכום. הפער: העמוד מכיל חמש שורות בלבד (סיום ההוכחה) וכותרת כחולה קצרה ומעט מטושטשת. ההכרעה: תוכן השורות ברור ושולב במלואו בכיוון ב'; הכותרת אינה נושאת מידע מתמטי ולא שוחזרה.
• מקור: תוספת עורך. הפער: דוגמת $\mathrm{CLIQUE}$ ומשפט 5(ב) אינם מופיעים באף מקור. ההכרעה: נכללו כתוספת מסומנת, כתרגול נוסף וכהשלמת התמונה "למה ההגדרה נראית כך".