5Padding Arguments and an Introduction to SAT

בקצרה

• טיעון ריפוד (padding argument) הוא טכניקה להוכחת הכלה בין מחלקות סיבוכיות בהינתן הכלה אחרת. הרעיון: לוקחים שפה קשה, "מנפחים" מלאכותית את הקלטים שלה בזנב ארוך של תו חדש, ומקבלים שפה שהיא בדיוק אותה בעיה — אבל ביחס לאורך הקלט היא נראית הרבה יותר קלה, ולכן נופלת למחלקה נמוכה יותר שעליה ההכלה הנתונה כן חלה.
• הגרעין של כל הטכניקה הוא תצפית אחת: אם מספר הצעדים של מכונה נשאר קבוע ואורך הקלט גדל, סיבוכיות הריצה ביחס לאורך הקלט יורדת. הריפוד לא הופך שום דבר לקל יותר; הוא רק משנה את המכנה שביחס אליו מודדים.
• מוכיחים שתי טענות מסוג "אם הכלה אז הכלה": אם $\mathrm E\subseteq\mathrm{PSPACE}$ אז $\hat{\mathrm E}\subseteq\mathrm{PSPACE}$, ואם $\mathrm{NP}\subseteq\mathrm P$ אז $\mathrm{NEXP}\subseteq\mathrm{EXP}$ — כלומר, אם $\mathrm P=\mathrm{NP}$ אז $\mathrm{EXP}=\mathrm{NEXP}$, ובניסוח הנגדי־חיובי: אם $\mathrm{EXP}\ne\mathrm{NEXP}$ אז $\mathrm P\ne\mathrm{NP}$.
• טענות מותנות כאלה אינן חסרות שיניים: בשילוב עם משפט ההיררכיה בזמן הן נותנות תוצאה לא מותנית — $\mathrm E\ne\mathrm{PSPACE}$.
• מבנה ההוכחה קבוע ואינו משתנה משאלה לשאלה: ארבע מכונות, שתיים מקבלים "מהשמיים" מתוך שייכות למחלקה ושתיים בונים בעצמנו. הדבר היחיד שדורש מחשבה הוא כמה לרפד, וגם זה נקבע מחשבון פשוט.
• החלק השני של השיעור פותח את הפרק החדש, $\mathrm P$ מול $\mathrm{NP}$: מושגי הלוגיקה (ליטרל, פסוקית, נוסחת CNF, הסמה, ספיקות), הגדרת השפה $\mathrm{SAT}$, והמכונה הא־דטרמיניסטית שמראה $\mathrm{SAT}\in\mathrm{NP}$ — היא "מנחשת" הסמה ומאמתת אותה.
• מלכודת שהמרצה הדגיש: $\mathrm E\ne\mathrm{PSPACE}$ היא טענה על שפות, לא על מכונות. בכל ההכלות הסטנדרטיות שראינו עד כה המכונה נשארה אותה מכונה; כאן, לראשונה, אנחנו מייצרים מכונות חדשות ומשליכים בין מודלים.

רקע ותלויות

השיעור הזה סוגר את הפרק הראשון של הקורס (הקשרים בין מחלקות) ופותח את השני ($\mathrm P$ מול $\mathrm{NP}$). נזכיר במלואן את התוצאות שנשתמש בהן ממש.

מהשיעורים 1–2: המחלקות והמונוטוניות

טענה (מונוטוניות במשאב). אם $g=O(f)$ אז $\mathrm{DTime}(g)\subseteq\mathrm{DTime}(f)$ וגם $\mathrm{DSpace}(g)\subseteq\mathrm{DSpace}(f)$.

נשתמש גם בהבחנה בין מחלקות עדינות ($\mathrm{DTime}(f)$, $\mathrm{DSpace}(f)$ — לכל פונקציה מחלקה משלה) למחלקות גסות (איחוד אינסופי, כמו $\mathrm P$ או $\mathrm{PSPACE}$). כל פעם שנקבל שייכות למחלקה גסה, הצעד הראשון יהיה לקלף את האיחוד החוצה ולקבל שייכות למחלקה עדינה — ורק ממנה אפשר לחלץ מכונה עם חסם קונקרטי.

מהשיעור 3: משפט ההיררכיה בזמן והישימות

משפט ההיררכיה בזמן. אם $f$ ישימה בזמן (time-constructible), $f$ סופר־לינארית, ו-$g=o(f)$, אז $\mathrm{DTime}(g)\subsetneq\mathrm{DTime}\!\left(f^2\right).$

הריבוע שם אינו קישוט — הוא מחיר המעבר ממכונה רב־סרטית למכונה סטנדרטית. נשתמש במשפט הזה פעם אחת בדיוק, בטענה $\mathrm E\ne\mathrm{PSPACE}$.

נשתמש גם, שוב ושוב, בשני מושגי הישימות. פונקציה $f$ ישימה בזמן אם אפשר לחשב אותה בזמן $O(f)$, וישימה במקום אם אפשר לחשב אותה במקום $O(f)$. שתי הפונקציות שיופיעו כאן, $n\mapsto n^2$ ו-$n\mapsto d\cdot 2^{n^c}$, הן ישימות בזמן ובמקום. זה לא פרט טכני שאפשר לדלג עליו: המכונות שנבנה חייבות לחשב את גודל הריפוד, וללא ישימות אין לנו שום מושג כמה זה עולה.

הערה מההקלטה [00:44:21]: סטודנט הציע לחסום את המקום של שלב החישוב באורך הפלט. המרצה עצר על כך במפורש: מכונת טיורינג יכולה להשתמש בהרבה יותר מקום ממה שהיא מוציאה בסוף. הדוגמה הקיצונית שנתן — מכונת הכרעה מוציאה ביט אחד; האם המקום שלה קבוע? ודאי שלא. בדיוק בשביל זה צריך את הישימות במקום.

מהשיעור 4: המודל הא־דטרמיניסטי

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

הוכחנו בשיעור 4 שכל מחלקה דטרמיניסטית מוכלת במקבילה הא־דטרמיניסטית שלה, ובפרט $\mathrm P\subseteq\mathrm{NP}$ ו-$\mathrm{EXP}\subseteq\mathrm{NEXP}$. זו הסיבה שכל טענה על שוויון בין הזוגות האלה מצטמצמת להכלה בכיוון אחד בלבד.

הגדרות

הגדרה 1: המחלקה $\mathrm E$

אינטואיציה. זו מחלקת ה"אקספוננציאלי בדיוק" — החזקה היא $cn$, עם $n$ בלי חזקות בכלל. המרצה עצר על כך במפורש: $\mathrm E$ אינה $\mathrm{EXP}$. ב-$\mathrm{EXP}$ החזקה היא $n^c$, ולכן $2^{n^{100}}$ יושב ב-$\mathrm{EXP}$ אך לא ב-$\mathrm E$.

דוגמה. שפה שמוכרעת בזמן $3\cdot 2^{5n}$ שייכת ל-$\mathrm E$. אי־דוגמה. שפה שזמן ההכרעה המינימלי שלה הוא $2^{n^2}$ אינה ב-$\mathrm E$, אך כן ב-$\mathrm{EXP}$. מתקיים $\mathrm E\subseteq\mathrm{EXP}$, וההכלה היא הכלה ממש.

הגדרה 2: המחלקה $\hat{\mathrm E}$

אינטואיציה. אותו דבר בדיוק, אלא שהמעריך ריבועי במקום לינארי. זו מחלקה גדולה יותר מ-$\mathrm E$ (ובהמשך נוכיח שהיא גדולה ממש), ועדיין מוכלת ב-$\mathrm{EXP}$. ההפרש בין שתי המחלקות הוא בדיוק "ריבוע במעריך" — וזה, כפי שנראה, בדיוק גודל הריפוד שיידרש.

הגדרה 3: שפת ריפוד (padded language)

תהי $A\subseteq\Sigma^*$ שפה, ותהי $p:\mathbb N\to\mathbb N$ פונקציה ישימה בזמן ובמקום. שפת הריפוד של $A$ ביחס ל-$p$ היא

כאשר $\#$ הוא תו חדש שאינו באלף־בית $\Sigma$ של $A$.

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

למה $\#$ חייב להיות תו חדש? כדי שהפירוק $y=x\#^\ell$ יהיה חד־משמעי. אילו $\#\in\Sigma$, לא היינו יכולים לקבוע מהסתכלות ב-$y$ היכן נגמר $x$ ומתחיל הזנב, והשלב הראשון של המכונה שנבנה לא היה מוגדר היטב.

דוגמה. עבור $A=\{\,\texttt{01},\ \texttt{110}\,\}$ ו-$p(n)=n^2$ מקבלים $B=\{\,\texttt{01}\#\#\#\#,\ \texttt{110}\#^9\,\}$. אי־דוגמה. המילה $\texttt{01}\#\#\#$ אינה ב-$B$, אף ש-$\texttt{01}\in A$: אורך הזנב אינו $|x|^2$. זו בדיוק הבדיקה שהמכונה תבצע בשלב השני, ובלעדיה $B$ לא הייתה מוגדרת היטב.

הגדרה 4: ליטרל, פסוקית ונוסחת CNF

יהיו $x_1,\dots,x_n$ משתנים בוליאניים.

• ליטרל הוא משתנה או שלילה של משתנה. למשל $x_2$ הוא ליטרל, וגם $\overline{x_4}$.
• הֶסְגֵּר (או פסוקית, clause) הוא טְפֶל (tuple) סופי של ליטרלים עם $\vee$ ("או") ביניהם. למשל $x_1\vee\overline{x_2}\vee\overline{x_4}$ היא פסוקית עם שלושה ליטרלים.
• נוסחת CNF היא טפל סופי של פסוקיות עם $\wedge$ ("וגם") ביניהן. למשל $(x_1\vee\overline{x_2}\vee x_4)\wedge(\overline{x_1}\vee\overline{x_3}\vee\overline{x_4}\vee x_5).$

אינטואיציה. CNF (Conjunctive Normal Form) היא "וגם של אואים": רשימת דרישות, שכל אחת מהן מסופקת אם לפחות אחת מהאפשרויות שבה מתקיימת. שימו לב שההגדרה היא תחבירית בלבד — עדיין לא נתנו לסימנים האלה שום משמעות.

דוגמה ואי־דוגמה. אין הגבלה על מספר הליטרלים בפסוקית: $\overline{x_2}\vee x_4\vee x_1\vee x_5$ היא פסוקית CNF תקינה. לעומת זאת $(x_1\wedge x_2)\vee x_3$ אינה נוסחת CNF — היא בצורה ההפוכה (DNF).

הערה מההקלטה [01:48:51]: המרצה הוסיף בכוונה משתנה רביעי לדוגמה, "כדי שלא תחשבו שזה חייב להיות עם שלוש". פסוקיות באורך 3 הן מקרה פרטי שיזכה לשם משלו ($3\mathrm{SAT}$), אך אינן ההגדרה.

הגדרה 5: הסמה וספיקות

הסמה היא פונקציה $v:\{x_1,\dots,x_n\}\to\{0,1\}$.

לפי הכללים הלוגיים אפשר להרחיב את $v$ מן המשתנים לכל נוסחה לוגית: אם $v(x_1)=T$ אז $v(\overline{x_1})=F$; אם $v(x_1)=T$ ו-$v(x_2)=F$ אז $v(x_1\vee x_2)=T$ ו-$v(x_1\wedge x_2)=F$; וכן הלאה.

נוסחה $\varphi$ נקראת ספיקה אם קיימת הסמה $v$ המעניקה לה את הערך $T$; אומרים אז ש-$v$ מספקת את $\varphi$.

אינטואיציה. ההסמה היא הסמנטיקה — האובייקט החיצוני שנותן משמעות לתחביר. ספיקות אינה תלויה בהסמה מסוימת: היא טענת קיום.

דוגמה. ההסמה $v(x_1)=T,\ v(x_2)=F$ מספקת את $x_1\vee x_2$ ואינה מספקת את $x_1\wedge x_2$ — אבל $x_1\wedge x_2$ בכל זאת ספיקה, כי הסמה אחרת (שנותנת $T$ לשניהם) כן מספקת אותה. אי־דוגמה (נוסחה שאינה ספיקה). $x_1\wedge\overline{x_1}$. יש כאן משתנה אחד; כל הסמה נותנת $F$ לאחד משני הליטרלים, ולכן נותנת $F$ לנוסחה כולה. לא קיימת הסמה מספקת.

הערה מההקלטה [01:56:48]: "אל תגידו $x_1=T$ אף פעם. תביאו הסמה ותגידו: ההסמה נותנת $T$ ל-$x_1$." הרבה טעויות נובעות מהתייחסות למשתנים כאילו יש להם ערכים. למשתנים אין ערכים — כדי לתת להם ערך צריך אובייקט נוסף מבחוץ.

הגדרה 6: השפה $\mathrm{SAT}$

עבור נוסחת CNF $\varphi$ נסמן ב-$\langle\varphi\rangle$ את הקידוד הבינרי שלה. מניחים שכל מחרוזת בינארית מקודדת נוסחת CNF כלשהי (מחרוזת שאינה במבנה התקין מתורגמת לנוסחה קבועה אחת) — בדיוק כפי שעשינו עם קידוד מכונות טיורינג בחישוביות. אז

אינטואיציה. שימו את הקידוד בצד; הוא נחוץ רק מפני שמכונת טיורינג מקבלת מחרוזות. במהות, $\mathrm{SAT}$ היא אוסף כל נוסחאות ה-CNF שיש להן הסמה מספקת.

דוגמה. $\langle x_1\vee x_2\rangle\in\mathrm{SAT}$. אי־דוגמה. $\langle x_1\wedge\overline{x_1}\rangle\notin\mathrm{SAT}$.

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

משפט 1: אם $\mathrm E\subseteq\mathrm{PSPACE}$ אז $\hat{\mathrm E}\subseteq\mathrm{PSPACE}$

הוכחה. נניח $\mathrm E\subseteq\mathrm{PSPACE}$, ותהי $A\in\hat{\mathrm E}$. עלינו להראות $A\in\mathrm{PSPACE}$.

שלב א' — קבלת המכונה הראשונה. $\hat{\mathrm E}$ מוגדרת על ידי איחוד, ולכן נקלף את האיחוד: קיים $c>0$ כך ש-$A\in\mathrm{DTime}\!\left(2^{cn^2}\right)$. זו שייכות למחלקה עדינה, ומהגדרתה קיימת מכונה $M_A$ וקיים $d>0$ כך ש-$M_A$ מכריעה את $A$ וכן לכל $x$:

שלב ב' — בניית שפת הריפוד. נגדיר

כאשר $\#$ תו חדש שאינו ב-$\Sigma$, האלף־בית של $A$.

למה דווקא $|x|^2$? מפני שההפרש היחיד בין $\mathrm E$ ל-$\hat{\mathrm E}$ הוא ש-$n$ עולה בריבוע במעריך. אם אני מנפח את הקלט כך שאורכו יהיה סדר גודל של $|x|^2$, אז מספר צעדים שהיה $2^{c|x|^2}$ ביחס לקלט הישן נעשה $2^{c|y|}$ ביחס לקלט החדש — בדיוק המעבר מ-$\hat{\mathrm E}$ ל-$\mathrm E$.

שלב ג' — בניית המכונה השנייה. נגדיר מכונה $M_B$ שעל קלט $y\in(\Sigma\cup\{\#\})^*$ פועלת כך:

1. נבדוק ש-$y$ מהצורה $x\#^{\ell}$ כאשר $x\in\Sigma^*$; אחרת נדחה.
2. נחשב את $|x|^2$ ונבדוק ש-$\ell=|x|^2$; אחרת נדחה.
3. נריץ את $M_A$ על $x$ ונחזיר את תשובתה.

נכונות: $M_B$ מכריעה את $B$. יהי $y\in(\Sigma\cup\{\#\})^*$.

כיוון ראשון. אם $y\in B$ אז קיים $x\in A$ כך ש-$y=x\#^{|x|^2}$. בהרצת $M_B$ על $y$: שלב 1 עובר (זהו בדיוק המבנה), שלב 2 עובר (זהו בדיוק האורך), ובשלב 3 המכונה $M_A$ מקבלת את $x$ כי $x\in A$ ו-$M_A$ מכריעה את $A$. לכן $M_B$ מקבלת את $y$.

כיוון שני. נניח ש-$M_B$ מקבלת את $y$. מכיוון שכל שלב שנכשל גורם לדחייה, בהכרח שלושת השלבים עברו: מ-1 נובע ש-$y=x\#^\ell$ עבור $x\in\Sigma^*$; מ-2 נובע $\ell=|x|^2$; ומ-3 נובע ש-$M_A$ קיבלה את $x$, ולכן $x\in A$. מכאן $y=x\#^{|x|^2}$ עם $x\in A$, כלומר $y\in B$.

בנוסף, $M_B$ עוצרת תמיד: שלבים 1–2 הם סריקות סופיות, ו-$M_A$ עוצרת תמיד כי היא מכריעה. לכן $M_B$ מכריעה את $B$.

שלב ד' — חשבון הזמן של $M_B$. יהי $y$ שעבר את שלב 1, ונסמן $y=x\#^\ell$.

• שלב 1 — סריקה אחת של הקלט: מרגע שראינו $\#$ לוודא שלא מופיע עוד תו מ-$\Sigma$. עלות: $O(|y|)$ צעדים.
• שלב 2 — כאן נדרשת הישימות בזמן של $n\mapsto n^2$: היא מבטיחה שחישוב הערך $|x|^2$ אורך $O(|x|^2)$ צעדים. וכיוון ש-$|y|=|x|+|x|^2\ge|x|^2$, זהו $O(|y|)$.
• שלב 3 — מהגדרת $M_A$, ההרצה על $x$ אורכת לכל היותר $d\cdot 2^{c|x|^2}$ צעדים. שוב $|x|^2\le|y|$, ולכן זה חסום ב-$d\cdot 2^{c|y|}$.

סך הכול, לכל $y$:

לכן $B\in\mathrm{DTime}\!\left(2^{cn}\right)$, ומכאן $B\in\mathrm E$.

שלב ה' — חציית הגשר. מההנחה $\mathrm E\subseteq\mathrm{PSPACE}$ נובע $B\in\mathrm{PSPACE}$. נקלף שוב את האיחוד: קיים $\alpha>0$ כך ש-$B\in\mathrm{DSpace}(n^\alpha)$, ולכן קיימת המכונה השלישית $\widetilde{M_B}$ וקיים $\beta>0$ כך ש-$\widetilde{M_B}$ מכריעה את $B$ ולכל $y$:

שלב ו' — בניית המכונה הרביעית. נגדיר $\widetilde{M_A}$ שעל קלט $x$:

1. תחשב את $|x|^2$ ותבנה את $y=x\#^{|x|^2}$.
2. תריץ את $\widetilde{M_B}$ על $y$ ותחזיר את אותה תשובה.

נכונות: $\widetilde{M_A}$ מכריעה את $A$. יהי $x\in\Sigma^*$. אם $x\in A$ אז לפי הגדרת $B$ מתקיים $x\#^{|x|^2}\in B$, ולכן $\widetilde{M_B}$ מקבלת אותו, ולכן $\widetilde{M_A}$ מקבלת את $x$. אם $x\notin A$ אז $x\#^{|x|^2}\notin B$ (שוב לפי הגדרת $B$, שכל איבריה מגיעים מאיברי $A$), ולכן $\widetilde{M_B}$ דוחה אותו ו-$\widetilde{M_A}$ דוחה את $x$.

שלב ז' — חשבון המקום של $\widetilde{M_A}$. יהי $x\in\Sigma^*$.

• שלב 1 — כאן נדרשת הישימות במקום של $n\mapsto n^2$: חישוב הערך $|x|^2$ דורש $O(|x|^2)$ מקום. כתיבת $y$ עצמה תופסת $|x|+|x|^2=O(|x|^2)$ תאים.
• שלב 2 — מהגדרת $\widetilde{M_B}$, ההרצה דורשת לכל היותר $\beta|y|^{\alpha}$ תאים, וכיוון ש-$|y|=O(|x|^2)$ זהו $O\!\left(|x|^{2\alpha}\right)$.

סך הכול $\mathrm{space}_{\widetilde{M_A}}(x)=O\!\left(|x|^{2\alpha}\right)$, כלומר $A\in\mathrm{DSpace}\!\left(n^{2\alpha}\right)$ ולכן $A\in\mathrm{PSPACE}$. $\blacksquare$

התבנית ב-high level: ארבע מכונות

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

הערה מההקלטה [00:40:10]: סטודנט שאל למה בכלל צריך את מכונות ה"גל" ($\widetilde{\ \ }$) אם כבר יש $M_A,M_B$. התשובה: על $M_A$ ו-$M_B$ יש לנו מידע על זמן בלבד. כדי להסיק שייכות ל-$\mathrm{PSPACE}$ אנחנו חייבים מכונה שאנו יודעים לחסום את המקום שלה — ולכן חייבים לקבל מכונה חדשה. המעבר הזה, ממשאב אחד למשאב אחר או ממודל אחד לאחר, הוא כל תוכן ההוכחה.

משפט 2: $\mathrm E\ne\mathrm{PSPACE}$

זו טענה לא מותנית — והיא מודגמת כאן כדי להראות שטענות מותנות מסוג משפט 1 אינן חסרות ערך.

כיצד מוכיחים אי־שוויון בין קבוצות? $\mathrm E\ne\mathrm{PSPACE}$ פירושו: $\mathrm E\not\subseteq\mathrm{PSPACE}$ או $\mathrm{PSPACE}\not\subseteq\mathrm E$. זו טענת "או", ולכן מוכיחים אותה בהפרדה למקרים: מניחים שהחלק הראשון אינו מתקיים ומוכיחים את השני. (המרצה הדגיש: לטענת "או" מספיק צד אחד, ואין צורך בהוכחה בשלילה.)

הוכחה. אם $\mathrm E\not\subseteq\mathrm{PSPACE}$ — סיימנו. נניח אפוא $\mathrm E\subseteq\mathrm{PSPACE}$; נראה $\mathrm{PSPACE}\not\subseteq\mathrm E$.

1. ממשפט 1 נובע $\hat{\mathrm E}\subseteq\mathrm{PSPACE}$.
2. לכל $c>0$ מתקיים $2^{cn}=O\!\left(2^{n^2}\right)$ (שכן $cn\le n^2$ לכל $n\ge c$). לפי מונוטוניות במשאב, $\mathrm{DTime}\!\left(2^{cn}\right)\subseteq\mathrm{DTime}\!\left(2^{n^2}\right)$. הכלה נשמרת תחת איחוד, ולכן

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

$f$ סופר־לינארית וישימה בזמן, ומתקיים $g=o(f)$ שכן $g(n)/f(n)=2^{-n^2}\xrightarrow[n\to\infty]{}0$. לכן

4. מהגדרת $\hat{\mathrm E}$ (עם $c=4$) מתקיים $\mathrm{DTime}\!\left(2^{4n^2}\right)\subseteq\hat{\mathrm E}$.
5. נשרשר: $\mathrm E\subseteq\mathrm{DTime}\!\left(2^{n^2}\right)\subsetneq\mathrm{DTime}\!\left(2^{4n^2}\right)\subseteq\hat{\mathrm E}\subseteq\mathrm{PSPACE}$. בשרשרת הכלות שאחת מהן ממש, ההכלה בין הקצוות היא ממש, ולכן

6. מהכלה ממש נובע $\mathrm{PSPACE}\not\subseteq\mathrm E$, ובפרט $\mathrm E\ne\mathrm{PSPACE}$. $\blacksquare$

הערה: המרצה ציין ש"בדרך הזו" השתמשנו במשפט 1 בצורה חזקה מאוד — בלעדיו לא היה לנו מסלול מ-$\mathrm E$ אל $\hat{\mathrm E}$ בתוך $\mathrm{PSPACE}$. וכן: הכלה נשמרת תחת איחוד, הכלה ממש לא — ולכן שלב 3 נעשה על מחלקות עדינות דווקא.

משפט 3: אם $\mathrm P=\mathrm{NP}$ אז $\mathrm{EXP}=\mathrm{NEXP}$

בניסוח שהוצג בכיתה: הראו כי אם $\mathrm{EXP}\ne\mathrm{NEXP}$ אז $\mathrm P\ne\mathrm{NP}$.

צמצום הניסוח. ראשית מעיפים את השלילות במעבר לנגדי־חיובי: הטענה שקולה ל"אם $\mathrm P=\mathrm{NP}$ אז $\mathrm{EXP}=\mathrm{NEXP}$". שנית, כבר ידוע (שיעור 4) ש-$\mathrm P\subseteq\mathrm{NP}$ ו-$\mathrm{EXP}\subseteq\mathrm{NEXP}$; לכן כל מה שהטענה מחדשת הוא ההכלה בכיוון השני, ומספיק להוכיח:

אם $\mathrm{NP}\subseteq\mathrm P$ אז $\mathrm{NEXP}\subseteq\mathrm{EXP}$.

וזו כבר טענה מן הצורה "אם הכלה אז הכלה" — מועמדת מובהקת לריפוד.

הוכחה. נניח $\mathrm{NP}\subseteq\mathrm P$, ותהי $A\in\mathrm{NEXP}$.

מכונה 1. קיים $c\ge 1$ כך ש-$A\in\mathrm{NTime}\!\left(2^{n^c}\right)$, ולכן קיימת מכונה א־דטרמיניסטית $M_A$ וקיים $d>0$ כך ש-$M_A$ מכריעה את $A$ באופן א־דטרמיניסטי ולכל $x$:

(ההדגשה "א־דטרמיניסטית" חיונית: ללא ציון אחר, "מכונה" פירושה מכונה דטרמיניסטית סטנדרטית.)

כמה לרפד? זה החישוב היחיד שדורש מחשבה, והמרצה עשה אותו בקול. אני רוצה ש-$B$ תהיה ב-$\mathrm{NP}$, כלומר שזמן הריצה יהיה פולינומי ב-$|y|$. אבל הזמן היקר הוא הרצת $M_A$, שהוא מעריכי ב-$|x|$. כדי שאותו מספר צעדים ייראה פולינומי, $|y|$ חייב להיות מעריכי ב-$|x|$. לכן הריפוד יהיה מעריכי — וניקח מיד את הקבוע $d$ פנימה, כדי שהחשבון יֵצא נוח:

מכונה 2. נגדיר מכונה א־דטרמיניסטית $M_B$, שעל קלט $y\in(\Sigma\cup\{\#\})^*$:

1. תוודא ש-$y$ מהצורה $x\#^{\ell}$ עם $x\in\Sigma^*$; אחרת תדחה.
2. תחשב את $d\cdot 2^{|x|^c}$ ותוודא ש-$\ell=d\cdot 2^{|x|^c}$; אחרת תדחה.
3. תריץ את $M_A$ על $x$ ותחזיר את תשובתה.

שימו לב: שלבים 1 ו-2 דטרמיניסטיים לחלוטין; כל האי־דטרמיניזם של $M_B$ יושב בתוך הרצת $M_A$ בשלב 3. $M_B$ "מחזיקה את $M_A$ בבטן" ומריצה אותה, ולכן היא יורשת ממנה את האי־דטרמיניזם. (אין כאן שימוש במכונה אוניברסלית: כשאנו בונים את $M_B$ אנו כבר מכירים את $M_A$ וקובעים אותה בתוך המכונה.)

נכונות — בטרמינולוגיה של אי־דטרמיניזם.

כיוון ראשון. נניח $y\in B$, כלומר $y=x\#^{d\cdot 2^{|x|^c}}$ עבור $x\in A$. שלבים 1 ו-2 דטרמיניסטיים ויעברו בכל ריצה. כיוון ש-$x\in A$ ו-$M_A$ מכריעה את $A$ א־דטרמיניסטית, קיימת ריצה של $M_A$ על $x$ שמסתיימת במצב מקבל. לכן קיימת ריצה של $M_B$ על $y$ שמסתיימת במצב מקבל — זו שבה $M_B$ בוחרת בשלב 3 את הבחירות של אותה ריצה מקבלת.

כיוון שני. נניח שקיימת ריצה של $M_B$ על $y$ המסתיימת במצב מקבל. בריצה זו שלבים 1 ו-2 עברו, ולכן קיים $x\in\Sigma^*$ עם $y=x\#^{d\cdot 2^{|x|^c}}$. כמו כן, בריצה זו ההרצה של $M_A$ על $x$ הסתיימה במצב מקבל, ולכן $x\in A$. מכאן $y\in B$.

בנוסף, כל ריצה של $M_B$ עוצרת, כי שלבים 1–2 סופיים וכל ריצה של $M_A$ עוצרת. לכן $M_B$ מכריעה את $B$ באופן א־דטרמיניסטי.

חשבון הזמן של $M_B$. נסמן $y=x\#^{\ell}$.

• שלב 1: סריקה אחת, $O(|y|)$ צעדים.
• שלב 2: מהישימות בזמן של $n\mapsto d\cdot 2^{n^c}$, החישוב עולה $O\!\left(2^{|x|^c}\right)$ צעדים. וכיוון ש-$|y|\ge d\cdot 2^{|x|^c}$, זהו $O(|y|)$.
• שלב 3: מהגדרת $M_A$, לכל היותר $d\cdot 2^{|x|^c}$ צעדים — שהם, שוב, לכל היותר $|y|$.

סך הכול $\mathrm{time}_{M_B}(y)=O(|y|)$, כלומר $B\in\mathrm{NTime}(n)\subseteq\mathrm{NP}$. הריפוד הוריד את הסיבוכיות ממעריכית ללינארית — לא מפני שהחישוב התייעל, אלא מפני שהמכנה גדל.

מכונה 3. מההנחה $\mathrm{NP}\subseteq\mathrm P$ נובע $B\in\mathrm P$, ולכן קיים $\alpha>0$ כך ש-$B\in\mathrm{DTime}(n^\alpha)$, ולכן קיימת מכונה דטרמיניסטית $\widetilde{M_B}$ וקיים $\beta>0$ כך ש-$\widetilde{M_B}$ מכריעה את $B$ ולכל $y$:

מכונה 4. נגדיר מכונה דטרמיניסטית $\widetilde{M_A}$ שעל קלט $x$:

1. תחשב את $d\cdot 2^{|x|^c}$ ותבנה את $y=x\#^{\,d\cdot 2^{|x|^c}}$.
2. תריץ את $\widetilde{M_B}$ על $y$ ותחזיר את אותה תשובה.

ההוכחה ש-$\widetilde{M_A}$ מכריעה את $A$ זהה מילה במילה לזו שבמשפט 1: $x\in A\iff x\#^{d\cdot 2^{|x|^c}}\in B\iff\widetilde{M_B}$ מקבלת אותו.

הערה: בהרצאה השלב הזה נאמר במשפט אחד ("תשלימו בדיוק אותה הוכחה"); הפירוט המלא: אם $x\in A$ אז לפי הגדרת $B$ מתקיים $y\in B$, ו-$\widetilde{M_B}$ מכריעה את $B$ ולכן מקבלת. אם $x\notin A$, אז אף איבר של $B$ אינו מהצורה $x\#^{d\cdot 2^{|x|^c}}$ עבור $x$ זה, ולכן $y\notin B$ ו-$\widetilde{M_B}$ דוחה. בשני המקרים $\widetilde{M_A}$ מחזירה את התשובה הנכונה, והיא עוצרת תמיד.

חשבון הזמן של $\widetilde{M_A}$. יהי $x\in\Sigma^*$.

• שלב 1: מהישימות בזמן של $d\cdot 2^{n^c}$, החישוב עולה $O\!\left(2^{|x|^c}\right)$; כתיבת $y$ עולה עוד $|x|+d\cdot 2^{|x|^c}=O\!\left(2^{|x|^c}\right)$ צעדים.
• שלב 2: לכל היותר $\beta|y|^{\alpha}=\beta\left(|x|+d\cdot 2^{|x|^c}\right)^{\alpha}$ צעדים.

הגורם הדומיננטי הוא השני, והעלאה בחזקת $\alpha$ מכניסה את $\alpha$ כמקדם במעריך:

כאשר המעבר האחרון תקף כי $\alpha|x|^c\le|x|^{c+1}$ לכל $|x|\ge\alpha$, וקלטים קצרים יותר נבלעים בקבוע. לכן

הערה מההקלטה [01:10:09]: אודליה שאלה אם המעבר בריפוד תמיד יהיה "זמן ↔ מקום". התשובה: לא. כאן זה מזמן לזמן, אבל מא־דטרמיניסטי לדטרמיניסטי. תמיד יש איזשהו מעבר בין משהו למשהו, אך הוא לא תמיד זמן ומקום — ומבחינת מבנה ההוכחה זה שקוף לחלוטין.

משפט 4: $\mathrm{SAT}\in\mathrm{NP}$

הוכחה. נבנה מכונת טיורינג א־דטרמיניסטית דו־סרטית $M$, שעל קלט $\langle\varphi\rangle$:

1. נספור את מספר המשתנים ב-$\varphi$ (בפועל: האינדקס הגדול ביותר המופיע בנוסחה) ונסמנו $n$.
2. נכתוב $n$ ביטים באופן א־דטרמיניסטי על הסרט השני.
3. נתייחס לביטים כאל הסמה $v$ (הביט ה-$i$ הוא $v(x_i)$) ונבדוק אם $v$ מספקת את $\varphi$; נקבל אם כן, ונדחה אחרת.

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

הערה: בהרצאה נאמר "אם הנוסחה ספיקה קיימת אפשרות לכתוב הסמה מספקת על הסרט השני" ותו לא; הנימוק המפורט לשני הכיוונים הוא הפירוט שלנו. המרצה השאיר במפורש את המשך ההוכחה כשיעורי בית לשיעור הבא [02:05:32].

חשבון הזמן. נסמן $m=|\langle\varphi\rangle|$ ו-$n\le m$ את מספר המשתנים.

• שלב 1: סריקה של הקידוד תוך שמירת האינדקס המרבי — $O(m^2)$ צעדים בגבול העליון הגס (סריקה אחת לכל השוואה); בוודאי פולינומי.
• שלב 2: כתיבת $n\le m$ ביטים — $O(m)$ צעדים.
• שלב 3: עוברים על הנוסחה ליטרל־ליטרל; לכל ליטרל ניגשים לביט המתאים בסרט השני, מה שעולה לכל היותר $O(m)$ צעדי הזזה. מספר הליטרלים חסום ב-$m$, ולכן $O(m^2)$ צעדים.

סך הכול $\mathrm{time}_M(\langle\varphi\rangle)=O(m^2)$ — פולינומי.

מעבר למכונה סטנדרטית. המחלקות מוגדרות באמצעות מכונות חד־סרטיות, ולכן נותר לתרגם. מהשקילות בין המודלים (שיעור 1), סימולציה של מכונה רב־סרטית במכונה חד־סרטית עולה לכל היותר ריבוע בזמן; לכן קיימת מכונה א־דטרמיניסטית חד־סרטית $\widehat M$ שמכריעה את $\mathrm{SAT}$ בזמן $O(m^4)$. מכאן

הערה מההקלטה [02:03:54]: "לכתוב באופן א־דטרמיניסטי" אינו "לכתוב באקראי". אין כאן שום הסתברות: פונקציית המעברים פשוט מאפשרת גם לכתוב $0$ וגם לכתוב $1$, ואנחנו שואלים אם קיימת בחירה נכונה. לא בכל ריצה המכונה תבחר נכון — אבל קיימת לה אפשרות כזו. הסתברות היא מודל אחר לגמרי.

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

דוגמה 1: מעקב אחרי מילה קונקרטית בריפוד הריבועי

ניקח $\Sigma=\{0,1\}$ ונניח ש-$x=\texttt{101}\in A$, כאשר $A\in\hat{\mathrm E}$ עם $c=1$ ו-$d=1$, כלומר $M_A$ רצה על $x$ לכל היותר $2^{|x|^2}=2^9=512$ צעדים.

קדימה (מ-$A$ ל-$B$): $|x|=3$, ולכן $|x|^2=9$ ו-

$y=\texttt{101}\#\#\#\#\#\#\#\#\#,\qquad |y|=3+9=12 .$

$M_B$ על $y$: שלב 1 סורק 12 תווים ומוודא שאחרי ה-$\#$ הראשון אין תו מ-$\Sigma$ — עובר. שלב 2 מחשב $3^2=9$ ומשווה ל-9 — עובר. שלב 3 מריץ את $M_A$ על $\texttt{101}$ ב-$\le 512$ צעדים. סך הצעדים $\le 12+9+512<2^{1\cdot 12}=4096$ — ואכן ההרצה נכנסת בתקציב $2^{c|y|}$.

אחורה (מ-$B$ ל-$A$): $\widetilde{M_A}$ על $\texttt{101}$ מחשבת 9, כותבת את אותו $y$ באורך 12, ומריצה עליו את $\widetilde{M_B}$ במקום $\le\beta\cdot 12^{\alpha}$ — שהוא $O\!\left(3^{2\alpha}\right)$, כלומר פולינומי ב-$|x|$.

היכן זה נשבר בכוונה: המילה $y'=\texttt{101}\#\#\#\#$ (זנב באורך 4) תיפול בשלב 2, וזה נכון — היא באמת אינה ב-$B$. וזו הסיבה ששלב 2 אינו מותרות: בלעדיו $M_B$ הייתה מקבלת מילים קצרות מדי, וחשבון הזמן שנשען על $|x|^2\le|y|$ היה קורס.

דוגמה 2: מעקב בריפוד המעריכי

נניח $A\in\mathrm{NTime}\!\left(2^{n^2}\right)$ (כלומר $c=2$), $d=1$, ו-$x=\texttt{10}$, $|x|=2$. גודל הריפוד: $d\cdot 2^{|x|^c}=2^{4}=16$, ולכן $|y|=2+16=18$.

$M_A$ על $x$ רצה לכל היותר 16 צעדים. ביחס ל-$y$ זה $\le 18$ צעדים — לינארי. אותו מספר צעדים בדיוק, מכנה גדול פי תשעה. זה, בשורה אחת, כל טיעון הריפוד.

דוגמה 3: הבדיקה שהנוסחה מסופקת (הדוגמה מהסיכום)

נתונה הנוסחה

יש בה ארבעה משתנים (הם חוזרים על עצמם, אך המשתנים הם $x_1,x_2,x_3,x_4$), ולכן $M$ תכתוב בשלב 2 מחרוזת באורך 4.

ריצה שנכשלת: נניח שנכתב $\texttt{0100}$, כלומר $v(x_1)=0,\ v(x_2)=1,\ v(x_3)=0,\ v(x_4)=0$. הפסוקית הראשונה: $v(x_1)=0$, $v(\overline{x_2})=0$, $v(x_3)=0$ — כולם $F$, ולכן הפסוקית אינה מסופקת, ולכן $v$ אינה מספקת את $\varphi$. הריצה הזו דוחה.

ריצה שמצליחה: לו נכתב $\texttt{1101}$, כלומר $v(x_1)=1,\ v(x_2)=1,\ v(x_3)=0,\ v(x_4)=1$. הפסוקית הראשונה: $v(x_1)=1$ — מסופקת. הפסוקית השנייה: $v(x_2)=1$ — מסופקת. לכן $v$ מספקת את $\varphi$ והריצה מקבלת.

המסקנה: קיימת ריצה מקבלת, ולכן $M$ מקבלת את $\langle\varphi\rangle$ — כנדרש, שכן $\varphi$ אכן ספיקה. שימו לב שהריצה הדוחה אינה סתירה: בהכרעה א־דטרמיניסטית מספיק שקיימת ריצה מקבלת.

תרגיל 1 (נשאל בכיתה): הנוסחה שאינה ספיקה

שאלה: לפי ההגדרה מרגיש כאילו כל נוסחה ספיקה. תנו דוגמה לנוסחה שאינה ספיקה.

פתרון: $\varphi=x_1\wedge\overline{x_1}$. יש כאן משתנה יחיד, ולכן שתי הסמות אפשריות בלבד. אם $v(x_1)=T$ אז $v(\overline{x_1})=F$ ולכן $v(\varphi)=F$; אם $v(x_1)=F$ אז $v(\varphi)=F$. בשני המקרים $F$, ולכן לא קיימת הסמה מספקת ו-$\langle\varphi\rangle\notin\mathrm{SAT}$.

תרגיל 2 (השאלה המכינה מהשיעור הקודם)

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

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

תרגיל 3 (הכיוון של הריפוד — כמה לרפד?)

שאלה: בטענה על $\mathrm{NEXP}$, מדוע לא הספיק ריפוד ריבועי כמו במשפט 1?

פתרון: מטרתנו הייתה $B\in\mathrm{NP}$, כלומר זמן פולינומי ב-$|y|$. הצוואר הוא הרצת $M_A$, שעולה $d\cdot 2^{|x|^c}$ — מעריכי ב-$|x|$. ריפוד ריבועי נותן $|y|=O\!\left(|x|^2\right)$, ואז $d\cdot 2^{|x|^c}$ אינו פולינומי ב-$|y|$. רק ריפוד מעריכי מביא את $|y|$ לאותו סדר גודל כמו מספר הצעדים, ואז אותו מספר צעדים נעשה לינארי ב-$|y|$. הכלל האצבע שהמרצה נתן: כתבו את החסם הרצוי, כתבו את החסם שיש, וראו איזה $|y|$ מגשר; אם חורגים — הקטינו או הגדילו את הריפוד ונסו שוב.

תרגיל 4 (האינטואיציה מההקלטה המקבילה, [02:07:54]–[02:13:14])

שאלה: קחו את השפה $A=\{x\mid x$ is a composite number in binary$\}$ ואת האלגוריתם הנאיבי שעובר על כל המספרים מ-$1$ עד $x$ ומנסה לחלק. מה זמן הריצה שלו, ומה קורה אם משנים את הקידוד לאונרי?

פתרון: בקידוד בינרי, אורך הקלט הוא $\Theta(\log x)$ בעוד שמספר הפעולות הוא $\Theta(x)$ (ואף יותר, בגלל עלות כל חילוק). לכן ביחס לאורך הקלט זמן הריצה הוא $2^{\Theta(|x|)}$ — מעריכי. בקידוד אונרי, אורך הקלט הוא בדיוק $x$; אותו אלגוריתם בדיוק, ללא שינוי של תו אחד, רץ עכשיו בזמן פולינומי (סדר גודל $|x|^2$) ביחס לאורך הקלט.

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

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

• [00:09:20] "בדרך תהיינה ארבע מכונות." שתיים מקבלים משייכות למחלקה, שתיים בונים. שווה לכתוב את הספירה הזו בשוליים לפני שמתחילים — היא מונעת אבדן דרך באמצע.
• [00:19:31] שאלת סטודנט: איך $M_A$ מכירה את התו $\#$, הרי הוא לא באלף־בית של $A$? תשובה: היא אינה מכירה אותו, ואינה צריכה — $M_A$ מורצת רק על $x$, לא על הזנב. בעקבות השאלה המרצה חידד את הכתיבה והוסיף במפורש "כאשר $x\in\Sigma^*$", וסימן $\Sigma$ = האלף־בית של $A$.
• [00:21:04] מוסכמה: אחרי כל שלב אפשר לכתוב "אחרת נדחה", במקום שלב מסכם רביעי. שתי הכתיבות שקולות; בסיכום מופיע שלב 4 מפורש, בהקלטה הוא נבלע בשלבים.
• [00:33:10] הניסוח המדויק של הרווח: "מספר הצעדים לא השתנה, אבל הכול גדל, אז פתאום אני משלם פחות ביחס לקלט."
• [00:45:28] הישימות אינה טכניקליות. בכל טיעון ריפוד יש לומר במפורש שפונקציית הריפוד ישימה (בזמן, במקום, או בשניהם — לפי מה שחוסמים). "היא תמיד תהיה חשובה בריפוד, אז תמיד צריך להגיד את זה" [01:34:30].
• [00:59:45] מלכודת מושגית: $\mathrm E=\mathrm{PSPACE}$ היא טענה על שפות. אין טענה שמכונה שרצה בזמן כזה תרוץ במקום כזה; הטענה היא שאם קיימת מכונה אחת, קיימת מכונה אחרת. בכל ההכלות הסטנדרטיות שראינו עד כה המכונה נשארה אותה מכונה — כאן, לראשונה, החלפנו מכונות.
• [01:00:17] טכניקה לטענת "או": מוכיחים בהפרדה למקרים — מניחים שהחלק הראשון אינו מתקיים ומוכיחים את השני. אין צורך להוכיח את שני הצדדים, ואין צורך בהוכחה בשלילה.
• [01:05:46] שאלת סטודנט: מאיפה הופיעה פתאום הכלה ממש? תשובה: היא הגיעה ממשפט ההיררכיה בזמן, והיא נשמרת: בשרשרת הכלות שאחת מהן ממש, ההכלה בין הקצוות היא ממש.
• [01:38:48] כלל עבודה: ריפוד מוכיח הכלה. אם רוצים הכלה ממש, מפרקים לשתיים — הכלה בכיוון אחד, ואי־הכלה בכיוון השני. לא מערבבים את שני המהלכים.
• [01:06:25] הערת מבחן/תרגיל: "תקבלו תרגיל ממש ממש דומה בשיעורי הבית. תעקבו אחד לאחד וזה מסתדר." המבנה קבוע; הדבר היחיד שמשתנה בין שאלה לשאלה הוא גודל הריפוד.
• [01:25:06] שאלת סטודנט: האם $M_B$ היא מכונה א־דטרמיניסטית מפני ש"משכנו" אליה את האי־דטרמיניזם של $M_A$? תשובה: כן בדיוק. היא מחזיקה את $M_A$ בתוכה ומריצה אותה, ולכן יורשת את האי־דטרמיניזם.
• [01:45:45] טרמינולוגיה: "טפל" (tuple) ולא "סדרה" — סדרה מרמזת על אינסופיות, ופסוקית היא סופית תמיד. "הסגר" ו"פסוקית" הם שני שמות לאותו מושג.
• [02:06:05] מה נשאר פתוח לשיעור הבא: להוכיח פורמלית ש-$M$ מכריעה את $\mathrm{SAT}$ באופן א־דטרמיניסטי, לחשב את זמן הריצה, ולעבור למכונה חד־סרטית ("לא לשכוח שהמחלקות מוגדרות על ידי מכונה חד־סרטית"). הפירוט המלא הוזן כאן לתוך משפט 4.

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

• מקור: עמוד 6 בסיכום. הפער: כתוב "$B\in\mathrm{NSpace}(n)\subseteq\mathrm{NP}$" מיד אחרי שחושב חסם זמן $\mathrm{time}_{M_B}(y)\le O(|y|)$. ההכרעה: זו פליטת קולמוס; הנכון הוא $\mathrm{NTime}(n)\subseteq\mathrm{NP}$ (ואכן $\mathrm{NSpace}(n)\subseteq\mathrm{NP}$ אינה טענה נכונה כלל). ההקלטה [01:28:57] מאשרת: "$B$ הוא אפילו בזמן ליניארי, אבל זה מוכל ב-$\mathrm{NP}$". תוקן בגוף.
• מקור: עמוד 6 בסיכום. הפער: כתוב "קיים $\alpha>0$ כך ש-$B\in\mathrm{DSpace}(n^\alpha)$" — אף שההנחה היא $B\in\mathrm P$, ואף שהשורה הבאה בסיכום עצמו נוקבת בחסם זמן $\mathrm{time}_{\widetilde{M_B}}\le\beta|y|^\alpha$. ההכרעה: אותה פליטת קולמוס (Space במקום Time). הנכון הוא $B\in\mathrm{DTime}(n^\alpha)$. תוקן בגוף.
• מקור: עמוד 5 בסיכום. הפער: מספור השלבים של $M_B$ במקרה ה-$\mathrm{NEXP}$ הוא ①,③,④ — שלב ② חסר. ההכרעה: מספור בלבד, ללא חוסר מתמטי; מוספרו כאן 1,2,3 בעקביות עם ההוכחה הראשונה.
• מקור: ההקלטה. הפער: בהקלטה מופיעה שאלה מכינה ("מכונה שרצה מיליון צעדים על קלט גדול יותר — הסיבוכיות עלתה או ירדה?") שהיא הגרעין האינטואיטיבי של כל הטכניקה, ואינה מופיעה בסיכום כלל. ההכרעה: נכללה כתרגיל 2 וכהערה.
• מקור: ההקלטה [00:42:15]–[00:45:28]. הפער: דיון ארוך ומהותי מדוע אי אפשר לחסום את המקום באורך הפלט, ומדוע דווקא הישימות במקום היא שמצילה — אין לו זכר בסיכום. ההכרעה: נכלל כהערה בסעיף הרקע.
• מקור: ההקלטה [01:14:30]–[01:16:02]. הפער: ההסבר כיצד בוחרים את גודל הריפוד (כותבים את החסם הרצוי, את החסם הקיים, ומגשרים; ואם חורגים — מנסים שוב) הוא הדבר היחיד שדורש מחשבה בהוכחה, והסיכום מציג רק את התוצאה. ההכרעה: נכלל בגוף משפט 3 ובתרגיל 3.
• מקור: ההקלטה השנייה (zcCQY3oT40Y). הפער: ההקלטה כולה, פרט לשבע הדקות האחרונות, עוסקת בחומר של שיעור אחר (המודל הא־דטרמיניסטי, דוגמת המספרים הפריקים, ואפיון $\mathrm{NP}$ באמצעות מוודא ועדות והוכחת השקילות). ההכרעה: סומנה partial; מתוכה נלקחה רק ההקדמה המוטיבציונית לריפוד (בינרי מול אונרי), שנכללה כתרגיל 4. אין בה גרסה שנייה של ההוכחות, ולכן הצלבת החסמים נעשתה מול הסיכום בלבד.
• מקור: ההקלטה [02:01:15] מול עמוד 8 בסיכום. הפער: בכתוביות האוטומטיות הפסוקית השנייה בדוגמה נשמעת "$x_2\vee x_3\vee x_4$" ללא שלילה, ובסיכום היא $(x_2\vee x_3\vee\overline{x_4})$. ההכרעה: הסיכום מנצח (וממילא ההסמה $\texttt{1101}$ מספקת את שתי הגרסאות). כמו כן, מחרוזות ההסמה בכתוביות מקוטעות ("$0\,1$", "$1\,0\,1$"); הסיכום נוקב ב-$\texttt{0100}$ ו-$\texttt{1101}$, ואלו נבדקו ונמצאו נכונות.
• מקור: ההקלטה [02:05:32] והסיכום עמוד 8. הפער: שני המקורות עוצרים אחרי תיאור המכונה ל-$\mathrm{SAT}$ ולפני חשבון זמן הריצה והמעבר למכונה חד־סרטית. ההכרעה: ההשלמה נכתבה כאן במלואה וסומנה כהשלמה בהערה; ראו גם open_questions.
• מקור: עמוד 3 בסיכום. הפער: הערה סגולה בשוליים השמאליים, שנראה שהיא מסבירה מדוע הריפוד הוא בגודל $n^2$, קריאה רק חלקית. ההכרעה: שוחזרה מתוך ההסבר המקביל בהקלטה [00:50:55] ("מכיוון שההבדל בין $\mathrm E$ ל-$\hat{\mathrm E}$ היה רק שה-$n$ עולה בריבוע, ריפדתי בריבוע").