24Exam Review: Characterising Complexity Classes Relative to NP (Question 3, parts a–c)

בקצרה

• זהו מפגש חזרה למבחן: אין בו תיאוריה חדשה, אלא פתרון מלא של שאלה אחת מתרגיל הבית — שאלה שכולה ברמת ההגדרה, כדברי המרצה: "אין שם שום דבר פרט להגדרה" [00:00:30].
• נתונות שלוש מחלקות $\mathrm{C}_1,\mathrm{C}_2,\mathrm{C}_3$, שכל אחת מהן נראית כמעט בדיוק כמו הגדרת ה‑verifier של $\mathrm{NP}$ (שיעור 6), ולכל אחת יש להכריע שלוש שאלות נפרדות: האם היא מכילה את $\mathrm{NP}$, האם היא מוכלת ב‑$\mathrm{NP}$, והאם היא שווה לה.
• התשובות: $\mathrm{C}_1=\mathrm{NP}$ (ההבדל היחיד הוא "דוחה" במקום "מקבלת", והוא ניתן לגישור על ידי היפוך מצבי הקבלה והדחייה); $\mathrm{NP}\subsetneq\mathrm{C}_2$, ולמעשה $\mathrm{C}_2$ היא מחלקת כל השפות (ההבדל הוא "לכל" שהוחלף ב"קיים", והוא ניתן לגישור רק בכיוון אחד); $\mathrm{C}_3=\mathrm{P}$ (העד מקוצר לאורך קבוע, ולכן אפשר לעבור על כולו), ולכן $\mathrm{C}_3\subseteq\mathrm{NP}$ נכון, בעוד ש‑$\mathrm{NP}\subseteq\mathrm{C}_3$ שקול לשאלה הפתוחה $\mathrm{P}=\mathrm{NP}$.
• מעבר לתשובות, השיעור הוא בעיקרו שיעור בשיטה. המרצה מפרק את פתרון שאלות מהסוג הזה לארבעה שלבים קבועים, שניים מחשבתיים ושניים טכניים [00:05:45]–[00:06:17]; מי שמפנים אותם מקבל מתכון לכל שאלה כזו במבחן.
• שני כשלים לוגיים חוזרים מתועדים כאן במפורש: המעבר מ"לכל" ל"קיים" מותר רק כשהתחום אינו ריק [00:32:54], והטענה "ממשפט ההיררכיה קיימת שפה שאינה ב‑$\mathrm{NP}$" בלי להסביר איך — תשובה חלקית בלבד [00:53:30].
• קו הגבול העדין ביותר בשיעור: להוכיח קיום צריך להציג עצם אחד; להוכיח הכלה צריך לצטט את ההגדרה. המרצה מסרב במכוון להוכיח יותר ממה שנדרש, גם כשהטענה החזקה יותר נכונה [00:57:10].

רקע ותלויות

(א) $\mathrm{NP}$ בנוסח ה‑verifier (ראו שיעור 6). זו ההגדרה שכל השאלה סובבת סביבה, ולכן היא מובאת כאן במלואה. שפה $A\subseteq\Sigma^*$ שייכת ל‑$\mathrm{NP}$ אם קיים $c\ge 1$ וקיימת מכונת טיורינג דטרמיניסטית $M$ עם זמן ריצה פולינומי, כך שלכל $x\in\Sigma^*$: $x\in A \iff \exists\, w\in\{0,1\}^{|x|^c}\ \text{ s.t. } M \text{ accepts } (x,w).$ המכונה $M$ נקראת verifier, המחרוזת $w$ נקראת עד (witness). שיעור 6 הוכיח שהגדרה זו שקולה להגדרה דרך מכונה אי‑דטרמיניסטית פולינומית, כלומר $\mathrm{NP}'=\mathrm{NP}$; כאן נשתמש בשתי הצורות בלי להבדיל ביניהן.

שימו לב לניסוח: בשיעור 6 החסם על אורך העד נכתב כפולינום $q(|x|)$, וכאן הוא נכתב כ‑$|x|^c$. זה אותו דבר — כל פולינום נחסם על ידי $n^c$ עבור $c$ גדול דיו, ואת מספר סופי של הערכים הקטנים אפשר תמיד "לצרוב" בתוך המכונה [00:22:12]. המרצה חוזר ומדגיש: היצמדו לניסוח שבו נכתבה השאלה [00:09:30] — אם השאלה כותבת $|x|^c$, כתבו $|x|^c$.

(ב) $\mathrm{P}$ ומשמעות "מכריעה" (ראו שיעורים 1–2). $\mathrm{P}=\bigcup_{c\ge1}\mathrm{DTime}(n^c)$. מכונה $\hat M$ מכריעה שפה $A$ אם לכל $x$ היא עוצרת, מקבלת אם $x\in A$ ודוחה אם $x\notin A$. הממשק חשוב: מכונה מכריעה מקבלת רק את $x$, ואילו verifier מקבל את הזוג $(x,w)$ ולכן אינו מכריע דבר [00:30:17].

(ג) שרשרת ההכלות הגסות (ראו שיעורים 2–4). מהסיכום, עמוד 2, במסגרת מודגשת: $\mathrm{P}\subseteq\mathrm{NP}\subseteq\mathrm{PSPACE}\subseteq\mathrm{EXP}\subseteq\mathrm{EXPSPACE},\qquad \mathrm{P}\subsetneq\mathrm{EXP}.$ $\mathrm{P}\subseteq\mathrm{PSPACE}$ הוכח בשיעור 2, $\mathrm{PSPACE}\subseteq\mathrm{EXP}$ בשיעורים 2–3, $\mathrm{P}\subseteq\mathrm{NP}$ בשיעור 4, $\mathrm{NP}\subseteq\mathrm{PSPACE}$ בשיעור 8, ו‑$\mathrm{P}\subsetneq\mathrm{EXP}$ ממשפט ההיררכיה בזמן בשיעור 3.

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

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

הגדרות

הגדרה 1: המחלקה $\mathrm{C}_1$ (סעיף א' בשאלה)

$\mathrm{C}_1$ היא מחלקת השפות $A\subseteq\Sigma^*$ עבורן קיים $c\ge 1$ כך שקיימת מכונת טיורינג דטרמיניסטית $M$ עם זמן ריצה פולינומי, כך שלכל $x\in\Sigma^*$ מתקיים: $x\in A \iff \exists\, w\in\{0,1\}^{|x|^c}\ \text{ s.t. } M \text{ rejects } (x,w).$

אינטואיציה. זו מילה במילה הגדרת ה‑verifier של $\mathrm{NP}$, כשההבדל היחיד הוא שבמקום "$M$ מקבלת את $(x,w)$" כתוב "$M$ דוחה את $(x,w)$". במילים: העד אינו מחרוזת שמשכנעת את הבודק לומר "כן", אלא מחרוזת שגורמת לו לומר "לא". מכיוון שהמכונה דטרמיניסטית ופולינומית — ולכן עוצרת תמיד — "לא לקבל" ו"לדחות" הם אותו אירוע, ואפשר להחליף ביניהם על ידי החלפת שני מצבי העצירה.

מופע. $\mathrm{SAT}\in\mathrm{C}_1$: קחו את ה‑verifier הרגיל של $\mathrm{SAT}$ (הצב את ההשמה $w$ בנוסחה) והחליפו בו את מצב הקבלה במצב הדחייה. אי‑מופע (למראית עין): אין כאן אף שפה שהיא ב‑$\mathrm{C}_1$ ולא ב‑$\mathrm{NP}$ — זו בדיוק תוצאת סעיף א'.

הגדרה 2: המחלקה $\mathrm{C}_2$ (סעיף ב' בשאלה)

$\mathrm{C}_2$ היא מחלקת השפות $A\subseteq\Sigma^*$ עבורן קיים $c\ge 1$ כך שקיימת מכונת טיורינג דטרמיניסטית $M$ עם זמן ריצה פולינומי, כך שלכל $x\in\Sigma^*$ מתקיים:

• אם $x\in A$ אז $\exists\, w\in\{0,1\}^{|x|^c}$ שעבורו $M$ מקבלת את $(x,w)$;
• אם $x\notin A$ אז $\exists\, w\in\{0,1\}^{|x|^c}$ שעבורו $M$ דוחה את $(x,w)$.

אינטואיציה. גם כאן ההשוואה היא ל‑$\mathrm{NP}$, וההבדל הוא כמתי: בהגדרת $\mathrm{NP}$ הצד השני הוא "אם $x\notin A$ אז לכל $w$ המכונה דוחה", וכאן הוא הוחלף ב"קיים $w$ שעבורו היא דוחה" [00:17:57]. זו החלשה דרמטית: תנאי "קיים" בשני הצדדים אינו מחייב את המכונה להבחין בין $x\in A$ ל‑$x\notin A$ בכלל. די שהמכונה תדע לקבל על עד אחד ולדחות על עד אחר — וזה משהו שכל מכונה טיפשית יודעת לעשות.

מופע. כל שפה שהיא. אי‑מופע. אין. זו בדיוק המסקנה שסטודנט העלה בכיתה [00:52:59]: "$\mathrm{C}_2$ זה בעצם קבוצת כל השפות" — והמרצה אישר שהטענה נכונה, אך סירב להוכיח אותה כי אין בה צורך (ראו הערות).

הגדרה 3: המחלקה $\mathrm{C}_3$ (סעיף ג' בשאלה)

$\mathrm{C}_3$ היא מחלקת השפות $A\subseteq\Sigma^*$ עבורן קיים $c\ge 1$ כך שקיימת מכונת טיורינג דטרמיניסטית $M$ עם זמן ריצה פולינומי, כך שלכל $x\in\Sigma^*$ מתקיים: $x\in A \iff \exists\, w\in\{0,1\}^{c}\ \text{ s.t. } M \text{ accepts } (x,w).$

אינטואיציה. ההגדרה זהה אות באות להגדרת $\mathrm{NP}$, למעט מקום אחד: אורך העד הוא $c$ ולא $|x|^c$ — כלומר קבוע שאינו תלוי בקלט כלל [00:58:53]. וזה משנה הכול: מספר העדים האפשריים הוא $2^c$, שהוא קבוע, ולכן אפשר פשוט לעבור על כולם בזמן פולינומי. העד מפסיק להיות "עזרה מבחוץ" והופך לפרט טכני שאפשר לנחש בכוח.

מופע. כל שפה ב‑$\mathrm{P}$ (הוכחה בתרגיל 3 להלן). אי‑מופע. $\mathrm{SAT}$, אלא אם $\mathrm{P}=\mathrm{NP}$ — כלומר אנחנו לא יודעים להצביע על אי‑מופע קונקרטי, וזה בדיוק תוכן החלק האחרון של הסעיף.

הגדרה 4: $\mathrm{HALT}$

$\mathrm{HALT}=\{\langle M,x\rangle \mid M \text{ halts on } x\}.$ מקורס החישוביות: $\mathrm{HALT}\notin\mathrm{R}$. זו השפה שתשמש אותנו כ"עד" לכך ש‑$\mathrm{C}_2$ אינה מוכלת ב‑$\mathrm{NP}$.

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

משפט 1: היפוך מצבי הקבלה והדחייה

טענה. תהי $M$ מכונת טיורינג דטרמיניסטית העוצרת על כל קלט, ותהי $\hat M$ המכונה המתקבלת מ‑$M$ על ידי החלפת מצב הקבלה ומצב הדחייה זה בזה. אזי לכל קלט $a$: $\hat M$ מקבלת את $a$ אם ורק אם $M$ דוחה את $a$; ו‑$\mathrm{time}_{\hat M}(a)=\mathrm{time}_M(a)$.

הוכחה. $\hat M$ זהה ל‑$M$ בכל רכיביה — $Q$, $q_{start}$, $\Sigma$, $\Gamma$, $\delta$ — למעט תיוג שני מצבי העצירה. לכן על כל קלט $a$ שתי המכונות עוברות את אותה סדרת קונפיגורציות בדיוק, ובפרט עוצרות באותו מספר צעדים ובאותו מצב עצירה. מכיוון ש‑$M$ עוצרת על כל קלט, מצב העצירה הוא בהכרח אחד משני המצבים $q_{acc},q_{rej}$; ומכיוון שהתיוג הוחלף, $\hat M$ מקבלת בדיוק כאשר $M$ דוחה. $\blacksquare$

הערה: בהרצאה זה נאמר במשפט אחד — "כי המכונה דטרמיניסטית, אני יכול להפוך את ה‑accept וה‑reject" [00:03:41]; הפירוט כאן. שימו לב היכן נכנסת הדטרמיניסטיות: במכונה אי‑דטרמיניסטית "לא מקבלת" פירושו "כל הריצות דוחות", ואילו "דוחה" של ריצה בודדת הוא אירוע אחר לגמרי — היפוך המצבים היה הופך "קיימת ריצה מקבלת" ל"קיימת ריצה דוחה", שאינה שלילת המקור. המשפט הזה נכשל למכונות אי‑דטרמיניסטיות.

הערת סגנון של המרצה [00:07:20]–[00:08:27]. כשמציגים את $\hat M$ אין לכתוב "נגדיר מכונה"; הניסוח הנכון הוא "נסמן ב‑$\hat M$ את המכונה המתקבלת מ‑$M$ על ידי החלפת מצבי הקבלה והדחייה". הסיבה: לא כתבנו אלגוריתם חדש, שינינו תיוג. "נגדיר" אינו טעות, זה עניין של סגנון — אבל הוא מטשטש את מה שבאמת קורה.

משפט 2: מ"לכל" ל"קיים" מעל תחום לא ריק

טענה. תהי $S$ קבוצה לא ריקה ותהי $\varphi$ תכונה. אם לכל $s\in S$ מתקיים $\varphi(s)$, אז קיים $s\in S$ שעבורו $\varphi(s)$.

הוכחה. $S\ne\emptyset$, ולכן קיים $s_0\in S$. מההנחה $\varphi(s_0)$ מתקיים. $\blacksquare$

למה זה לא טריוויאלי, ולמה חייבים לומר את זה במפורש [00:32:54]. הטענה "כל מספר שריבועו שלילי מתחלק ב‑3" היא נכונה (ריקנית), ובכל זאת לא קיים מספר שריבועו שלילי. לכן המעבר מ"לכל" ל"קיים" אינו כלל לוגי חופשי — הוא דורש את אי‑ריקות התחום. בכל השימושים בקובץ הזה התחום הוא $\{0,1\}^{|x|^c}$, שהוא לעולם אינו ריק (יש בו $2^{|x|^c}\ge 1$ מחרוזות), ולכן המעבר תקף.

המלצת המרצה [00:33:25]: במקום להסתמך על המעבר הזה, פשוט הציגו איבר קונקרטי. אם ידוע שכל $w$ מקיים משהו וצריך להוכיח שקיים כזה — כתבו "נתבונן ב‑$w=0^{|x|^c}$". זה קצר יותר, נצמד לתבנית ההוכחה של טענת קיום, ואינו מסתמך על צעד לוגי שקל לשגות בו.

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

טענה. $\mathrm{HALT}\notin\mathrm{NP}$.

הוכחה. לפי שיעור 8, $\mathrm{NP}\subseteq\mathrm{PSPACE}$. כל שפה ב‑$\mathrm{PSPACE}$ ניתנת להכרעה — קיימת לה מכונה שעוצרת על כל קלט ומכריעה אותה במקום פולינומי — ולכן $\mathrm{PSPACE}\subseteq\mathrm{R}$. נשרשר: $\mathrm{NP}\subseteq\mathrm{PSPACE}\subseteq\mathrm{R}.$ מקורס החישוביות $\mathrm{HALT}\notin\mathrm{R}$, ולכן $\mathrm{HALT}\notin\mathrm{NP}$. $\blacksquare$

מסלול חלופי שהוצג בכיתה [00:41:14]–[00:46:30]. אפשר לא לצאת מ‑$\mathrm{R}$ בכלל. ממשפט ההיררכיה במקום (שיעור 3), באותה הוכחה בדיוק שנתנה $\mathrm{P}\subsetneq\mathrm{EXP}$, מקבלים $\mathrm{PSPACE}\subsetneq\mathrm{EXPSPACE}$: מראים $\mathrm{PSPACE}\subseteq\mathrm{DSpace}(2^n)\subsetneq\mathrm{DSpace}(2^{n^2})\subseteq\mathrm{EXPSPACE}$, כשההכלה האמצעית ממש היא בדיוק משפט ההיררכיה. לכן קיימת $A\in\mathrm{EXPSPACE}\setminus\mathrm{PSPACE}$, ומכיוון ש‑$\mathrm{NP}\subseteq\mathrm{PSPACE}$ נובע $A\notin\mathrm{NP}$. המרצה ציין שהוא מרגיש פחות בנוח עם המסלול הזה, אך הוא תקף לגמרי.

מה אי אפשר לעשות [00:43:17]. אי אפשר להסיק ישירות מ‑$\mathrm{P}\subsetneq\mathrm{EXP}$ שקיימת שפה מחוץ ל‑$\mathrm{NP}$: הכלה ממש בין הקצוות של שרשרת אינה אומרת לנו איזו מן ההכלות בפנים היא ממש, ולכן לא נובע ממנה כלום על $\mathrm{NP}$ עצמה. צריך משפט היררכיה שמפריד שתי מחלקות ש‑$\mathrm{NP}$ יושבת בין הקטנה שבהן לבין עצמה.

משפט 4: $\mathrm{NP}\subseteq\mathrm{PSPACE}$ — הפניה לשיעור 8, והמכונה שנשתמש בה שוב

טענה. $\mathrm{NP}\subseteq\mathrm{PSPACE}$. הוכחה: ראו שיעור 8, משפט 1.

הסיבה שמזכירים אותה כאן היא לא הטענה אלא המכונה: בהינתן verifier $M$ ופולינום $q$ לאורך העד, בונים מכונה $\hat M$ שעל קלט $x$ עוברת על כל $w\in\{0,1\}^{q(|x|)}$, מריצה את $M$ על $(x,w)$, ומקבלת אם אחת ההרצות קיבלה. מספר האיטרציות הוא $2^{q(|x|)}$ — מעריכי, ולכן מקבלים $\mathrm{PSPACE}$ ולא $\mathrm{P}$. בתרגיל 3 להלן נשתמש באותו מנגנון בדיוק, אך מספר האיטרציות יהיה $2^c$ — קבוע — ולכן נקבל $\mathrm{P}$. כדברי המרצה [01:09:12]: "המכניזם הוא אותו מכניזם, רק שפה מספר האיטרציות של הלולאה קטן יותר".

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

עמוד 1 נושא כותרת ירוקה — "פתרון מטלה 2" — וחמשת העמודים כולם הם פתרון של שאלה 3 במטלה. ניסוח השאלה, כפי שהוא מודפס בראש עמוד 1:

3. עבור כל אחת ממחלקות הסיבוכיות שלהלן קבעו האם היא מכילה את המחלקה $\mathrm{NP}$, האם היא מוכלת בה, והאם היא שווה לה (אם ידוע; אחרת הוכיחו כי השאלה שקולה לשאלה פתוחה).

שימו לב שיש כאן שלוש שאלות נפרדות לכל מחלקה, ולא אחת. המרצה חזר על כך שלוש פעמים בסוף השיעור [01:19:38], [01:23:22], [01:24:27]: תשובה שמתייחסת רק לשוויון — גם אם היא נכונה — אינה עונה על מה שנשאל.

שיטת הפתרון בארבעה שלבים [00:05:45]–[00:06:17]:

1. לזהות איזו הגדרה מוכרת קרובה ביותר להגדרה שניתנה. (מחשבתי)
2. לכתוב את שתי ההגדרות אחת מול השנייה, ולאתר את ההבדל ברמת ה‑pattern matching. (טכני)
3. להכריע האם אפשר לגשר על ההבדל, ובאיזה כיוון. (מחשבתי — כאן נמצא כל התוכן)
4. לכתוב את ההוכחה לפי התבנית. (טכני)

"החלק שנופלים עליו הוא דווקא השלב הקודם" [00:03:09] — כלומר שלב 2, ההשוואה. המרצה מדגיש שהוא עצמו כותב את שתי ההגדרות זו לצד זו על דף, כי הוא לא מסוגל לראות את ההבדל בראש [00:02:07].

תרגיל 1 (סעיף א'): $\mathrm{C}_1$ — האם מכילה, מוכלת, שווה?

זיהוי ההבדל. ההגדרה הקרובה ביותר היא $\mathrm{NP}$ בנוסח ה‑verifier. ההשוואה:

ההבדל הוא מילה אחת, וניתן לגשר עליו לפי משפט 1.

חלק א': $\mathrm{C}_1\subseteq\mathrm{NP}$

תהא $A\in\mathrm{C}_1$. לכן קיימת מכונה $M$ הרצה בזמן פולינומי, וכן קיים $c\ge 1$, כך שלכל $x\in\Sigma^*$: $x\in A \iff \exists\, w\in\{0,1\}^{|x|^c}\ \text{ s.t. } M \text{ rejects } (x,w).$

נסמן ב‑$\hat M$ את המכונה המתקבלת מ‑$M$ על ידי החלפת מצבי הקבלה והדחייה. לפי משפט 1, $\hat M$ רצה בזמן פולינומי (אותו זמן ריצה בדיוק), ולכל קלט $a$: $\hat M$ מקבלת את $a$ אם ורק אם $M$ דוחה אותו.

נתבונן ב‑$\hat M$ ונתבונן ב‑$c$. אכן $\hat M$ רצה בזמן פולינומי, ואכן $c\ge 1$.

יהי $x\in\Sigma^*$.

כיוון ראשון. נניח $x\in A$. לכן קיים $w\in\{0,1\}^{|x|^c}$ כך ש‑$M$ דוחה את $(x,w)$. נתבונן ב‑$w$ זה. אכן $w\in\{0,1\}^{|x|^c}$ (הוא התקבל מתוך ההגדרה של $\mathrm{C}_1$, ולכן באורך הנכון), ומכיוון ש‑$M$ דוחה את $(x,w)$, לפי משפט 1 המכונה $\hat M$ מקבלת את $(x,w)$.

כיוון שני. נניח $x\notin A$. לפי ההגדרה של $\mathrm{C}_1$ (בשלילת הצד הימני של האם‑ורק‑אם), לכל $w\in\{0,1\}^{|x|^c}$ המכונה $M$ אינה דוחה את $(x,w)$, ומכיוון שהיא עוצרת תמיד — היא מקבלת את $(x,w)$. יהי $w\in\{0,1\}^{|x|^c}$; לפי משפט 1, $\hat M$ דוחה את $(x,w)$.

סיכום התבנית. קיבלנו: קיימת מכונה $\hat M$ הרצה בזמן פולינומי וקיים $c\ge1$ כך שלכל $x$ — אם $x\in A$ אז קיים $w\in\{0,1\}^{|x|^c}$ ש‑$\hat M$ מקבלת את $(x,w)$, ואם $x\notin A$ אז לכל $w\in\{0,1\}^{|x|^c}$ המכונה $\hat M$ דוחה את $(x,w)$. זו בדיוק הגדרת $\mathrm{NP}$, ולכן $A\in\mathrm{NP}$.

מכאן $\mathrm{C}_1\subseteq\mathrm{NP}$. $\blacksquare$

על שתי השורות האחרונות [00:13:44]. המרצה רשם את "סיכום התבנית" הזה על הלוח בשחור, מסגרת נפרדת, למרות שהוא רק חוזר על מה שהוכח. הסיבה: "כשמביאים את זה ככה, המבנה קופץ החוצה" — הקישור בין ההוכחה להגדרה נעשה ברמה תחבירית ולא ברמה של אינטואיציה. אפשר לכתוב במקום זה את הצורה המקוצרת ("ולכן לכל $w$ המכונה $\hat M$ דוחה"), וזה נכון מתמטית ומקובל, אבל המבנה פחות נראה [00:14:47].

חלק ב': $\mathrm{NP}\subseteq\mathrm{C}_1$

הסיכום כותב "ובאותו אופן"; ההרצאה אמרה "הכיוון השני זה אותו דבר בדיוק, אני לא חושב שאנחנו צריכים" [00:16:56]. הנה הוא במלואו.

תהא $A\in\mathrm{NP}$. לכן קיימת מכונה $M$ הרצה בזמן פולינומי וקיים $c\ge1$ כך שלכל $x\in\Sigma^*$: $x\in A$ אם ורק אם קיים $w\in\{0,1\}^{|x|^c}$ ש‑$M$ מקבלת את $(x,w)$. נסמן ב‑$\hat M$ את המכונה המתקבלת מ‑$M$ בהחלפת מצבי הקבלה והדחייה; לפי משפט 1 היא פולינומית, ולכל $a$ היא דוחה את $a$ אם ורק אם $M$ מקבלת אותו.

נתבונן ב‑$\hat M$ ונתבונן ב‑$c$. יהי $x\in\Sigma^*$.

• אם $x\in A$: קיים $w\in\{0,1\}^{|x|^c}$ ש‑$M$ מקבלת את $(x,w)$, ולכן $\hat M$ דוחה את $(x,w)$ — כלומר קיים $w$ שעבורו $\hat M$ דוחה.
• אם $x\notin A$: לכל $w\in\{0,1\}^{|x|^c}$ המכונה $M$ דוחה את $(x,w)$, ולכן $\hat M$ מקבלת את $(x,w)$ — כלומר אין אף $w$ שעבורו $\hat M$ דוחה.

שני התנאים יחד נותנים בדיוק $x\in A \iff \exists w\in\{0,1\}^{|x|^c}:\ \hat M \text{ rejects } (x,w)$, כלומר $A\in\mathrm{C}_1$. מכאן $\mathrm{NP}\subseteq\mathrm{C}_1$. $\blacksquare$

התשובה לשלוש השאלות

$\boxed{\ \mathrm{C}_1=\mathrm{NP}\ }$

• האם $\mathrm{C}_1$ מוכלת ב‑$\mathrm{NP}$? כן — חלק א'.
• האם $\mathrm{C}_1$ מכילה את $\mathrm{NP}$? כן — חלק ב'.
• האם $\mathrm{C}_1$ שווה ל‑$\mathrm{NP}$? כן, משתי ההכלות. אף אחת מהשאלות אינה פתוחה.

תרגיל 2 (סעיף ב'): $\mathrm{C}_2$ — האם מכילה, מוכלת, שווה?

זיהוי ההבדל [00:17:57]. שוב ההגדרה הקרובה היא $\mathrm{NP}$. כשכותבים אותן זו מול זו:

ההבדל: "קיים" פעמיים במקום "לכל" וְ"קיים". הגישור אפשרי רק בכיוון אחד: מ"לכל" ל"קיים" (משפט 2, התחום אינו ריק), ולא להפך. לכן התחושה המיידית היא $\mathrm{NP}\subseteq\mathrm{C}_2$, וכנראה הכלה ממש [00:26:54].

חלק א': $\mathrm{NP}\subseteq\mathrm{C}_2$

תהא $A\in\mathrm{NP}$. לכן קיימת מכונה $M$ הרצה בזמן פולינומי וקיים $c\ge1$ כך שלכל $x\in\Sigma^*$: $x\in A \iff \exists\, w\in\{0,1\}^{|x|^c}\ \text{ s.t. } M \text{ accepts } (x,w).$

נתבונן ב‑$M$ ונתבונן ב‑$c$ — אותה מכונה ואותו קבוע, אין צורך לבנות דבר. אכן $M$ רצה בזמן פולינומי ואכן $c\ge1$.

יהי $x\in\Sigma^*$.

המקרה $x\in A$. לפי ההגדרה קיים $w\in\{0,1\}^{|x|^c}$ ש‑$M$ מקבלת את $(x,w)$. זו בדיוק הטענה שצריך להוכיח, ולכן עוצרים כאן [00:31:21].

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

לכן $A\in\mathrm{C}_2$, ומכאן $\mathrm{NP}\subseteq\mathrm{C}_2$. $\blacksquare$

שאלת סטודנט [00:35:29]: האם $1^{|x|^c}$ היה עובד גם? כן — כל מחרוזת בקבוצה עובדת, כי הטענה מתקיימת לכל $w$. $0^{|x|^c}$ ו‑$1^{|x|^c}$ הן פשוט הכתיבות הקצרות ביותר.

חלק ב': $\mathrm{C}_2\not\subseteq\mathrm{NP}$

צריך להציג שפה שהיא ב‑$\mathrm{C}_2$ ואינה ב‑$\mathrm{NP}$. נתבונן ב‑$\mathrm{HALT}$. לפי משפט 3, $\mathrm{HALT}\notin\mathrm{NP}$. נותר להראות $\mathrm{HALT}\in\mathrm{C}_2$.

נבנה מכונה $M$, שעל קלט $(x,w)$:

1. אם התו הראשון של $w$ הוא $1$ — קבל.
2. אחרת — דחה.

נתבונן ב‑$M$ ונתבונן ב‑$c=1$. אכן $c\ge1$. $M$ רצה בזמן פולינומי בגודל הקלט — למעשה בזמן קבוע, היא קוראת תו אחד [00:50:13].

יהי $x$.

המקרה $x\in\mathrm{HALT}$. נתבונן ב‑$w=1^{|x|}$. אכן $w\in\{0,1\}^{|x|^1}$. התו הראשון של $w$ הוא $1$, ולכן $M$ מקבלת את $(x,w)$.

המקרה $x\notin\mathrm{HALT}$. נתבונן ב‑$w=0^{|x|}$. אכן $w\in\{0,1\}^{|x|^1}$. התו הראשון של $w$ אינו $1$, ולכן $M$ דוחה את $(x,w)$.

לכן $\mathrm{HALT}$ מקיימת את הגדרת $\mathrm{C}_2$, כלומר $\mathrm{HALT}\in\mathrm{C}_2$. מכיוון ש‑$\mathrm{HALT}\notin\mathrm{NP}$, נובע $\mathrm{C}_2\not\subseteq\mathrm{NP}$. $\blacksquare$

השלמה: הקלט הריק. אם $x=\varepsilon$ אז $|x|=0$, העד היחיד הוא המחרוזת הריקה, ואין לה "תו ראשון". שלב 1 אינו מתקיים ולכן $M$ דוחה — וזה בדיוק מה שצריך, כי בקידודים המקובלים $\varepsilon$ אינו קידוד חוקי של זוג $\langle M,x\rangle$ ולכן $\varepsilon\notin\mathrm{HALT}$. שני המקורות עוברים על המקרה הזה בשתיקה; ראו סעיף הפערים.

מסקנה: $\mathrm{NP}\subsetneq\mathrm{C}_2$

מחלק א' $\mathrm{NP}\subseteq\mathrm{C}_2$, ומחלק ב' $\mathrm{C}_2\not\subseteq\mathrm{NP}$, ולכן ההכלה ממש: $\boxed{\ \mathrm{NP}\subsetneq\mathrm{C}_2\ }$

• האם $\mathrm{C}_2$ מכילה את $\mathrm{NP}$? כן, וממש.
• האם $\mathrm{C}_2$ מוכלת ב‑$\mathrm{NP}$? לא.
• האם $\mathrm{C}_2$ שווה ל‑$\mathrm{NP}$? לא. אף אחת מהשאלות אינה פתוחה.

מה באמת קורה כאן: $\mathrm{C}_2$ היא מחלקת כל השפות

סטודנט הצביע על כך בכיתה [00:52:59], והמרצה אישר שהטענה נכונה [00:57:10]. הנימוק: אותה מכונה $M$ בדיוק ("אם התו הראשון של $w$ הוא 1 קבל, אחרת דחה") מקיימת את הגדרת $\mathrm{C}_2$ עבור כל שפה $A$, כי היא כלל אינה מסתכלת על $x$ — ולכל $x$ יש עד שגורם לה לקבל ועד שגורם לה לדחות. תהא $A\subseteq\Sigma^*$ כלשהי: אם $x\in A$ ניקח $w=1^{|x|}$ והמכונה מקבלת, ואם $x\notin A$ ניקח $w=0^{|x|}$ והמכונה דוחה. לכן $A\in\mathrm{C}_2$, כלומר $\mathrm{C}_2=\{A \mid A\subseteq\Sigma^*\}.$

ואף על פי כן המרצה סירב לכתוב את זה [00:57:10]. הסיבה מתודית: השאלה דורשת להוכיח קיום של שפה ב‑$\mathrm{C}_2\setminus\mathrm{NP}$, ותבנית ההוכחה של טענת קיום היא "נתבונן ב‑$\mathrm{HALT}$", לא "תהא $A$ שפה כלשהי". הוכחת הטענה החזקה יותר אינה שגויה ואינה מפסידה נקודות — "בתנאי שאתה לא טועה שם" — אבל היא עבודה מיותרת שמגדילה את שטח הפנים לשגיאות.

תרגיל 3 (סעיף ג'): $\mathrm{C}_3$ — האם מכילה, מוכלת, שווה?

זיהוי ההבדל [00:58:53]. ההגדרה זהה להגדרת $\mathrm{NP}$ למעט אורך העד: $w\in\{0,1\}^c$ במקום $w\in\{0,1\}^{|x|^c}$ — אורך קבוע שאינו תלוי ב‑$x$.

הגישור. מספר העדים האפשריים הוא $2^c$. "זה נראה מעריכי, זה מעריכי — אבל לא ב‑$x$" [00:59:55]. מה שקובע הוא האם הביטוי מעריכי כפונקציה של אורך הקלט, ו‑$2^c$ הוא קבוע. לכן אפשר להריץ את ה‑verifier על כל העדים ועדיין להישאר בזמן פולינומי. המרצה הפנה כאן לאחור, לשיעור הקודם, שבו נדון באותו הקשר הביטוי $n^{2^c}$: "לא כל מה שיש לו צורה מעריכית אומר שזה מעריכי" [00:59:55].

חלק א': $\mathrm{C}_3\subseteq\mathrm{P}$

תהא $A\in\mathrm{C}_3$. לכן קיימת מכונה $M$ הרצה בזמן פולינומי וקיים $c\ge1$ כך שלכל $x\in\Sigma^*$: $x\in A \iff \exists\, w\in\{0,1\}^{c}\ \text{ s.t. } M \text{ accepts } (x,w).$

נגדיר מכונה $\hat M$ באופן הבא, על קלט $x$:

1. לכל $w\in\{0,1\}^c$:
   • 1.1 הרץ את $M$ על $(x,w)$.
   • 1.2 אם $M$ קיבלה — קבל.
2. דחה.

(שימו לב לממשק: $\hat M$ מקבלת רק את $x$, כי היא אמורה להכריע את $A$ [01:01:32].)

ניתוח זמן ריצה. יהי $x\in\Sigma^*$.

• לכל $w\in\{0,1\}^c$, זמן הריצה של $M$ על $(x,w)$ פולינומי ב‑$|x|+|w|=|x|+c$. מכיוון ש‑$c$ קבוע, זהו פולינום ב‑$|x|$.
• $\hat M$ מריצה את $M$ בדיוק $2^c$ פעמים. מספר הפעמים אינו תלוי ב‑$x$ — זהו קבוע של המכונה.
• כתיבת המונה ומעבר על $\{0,1\}^c$ עולים $O(c)=O(1)$.

סך הכול $\mathrm{time}_{\hat M}(x)\le 2^c\cdot\big(p(|x|+c)+O(1)\big)$, שהוא פולינום ב‑$|x|$ (מכפלה בקבוע והרכבת פולינומים).

נכונות. יהי $x\in\Sigma^*$.

נניח $x\in A$. אז קיים $w\in\{0,1\}^c$ כך ש‑$M$ מקבלת את $(x,w)$. מכיוון ש‑$\hat M$ עוברת על כל $\{0,1\}^c$, קיימת בריצה שלה על $x$ איטרציה שבה נבחר בדיוק ה‑$w$ הזה; באיטרציה זו שלב 1.2 מתקיים ו‑$\hat M$ מקבלת את $x$.

נניח $x\notin A$. אזי לכל $w\in\{0,1\}^c$ המכונה $M$ אינה מקבלת את $(x,w)$, ומכיוון שהיא עוצרת — היא דוחה. יהי $w\in\{0,1\}^c$; שלב 1.2 אינו מתקיים באיטרציה שלו. מכיוון שזה נכון לכל $w$, הלולאה מסתיימת ו‑$\hat M$ דוחה את $x$ בשלב 2.

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

תיקון שעלה בכיתה [01:07:39]. בכתיבה הראשונה על הלוח המרצה כתב במקרה $x\notin A$ ישירות "$M$ דוחה את $(x,w)$" בלי לכמת. סטודנט העיר שחסר "יהי $w\in\{0,1\}^c$" — כי כדי להסיק ש‑$\hat M$ דוחה צריך להראות שהמקרה נכשל לכל $w$, לא ל‑$w$ אחד. המרצה קיבל: "אתה צודק, שאלה טובה". התיקון מופיע בגוף ההוכחה למעלה, וגם בסיכום.

הקשר לשיעור 8 [01:02:35], [01:09:12]. זו אותה מכונה בדיוק שבנינו כדי להוכיח $\mathrm{NP}\subseteq\mathrm{PSPACE}$ — "נבנה מכונה שתעבור על כל העדים". שם מספר האיטרציות היה $2^{q(|x|)}$, ולכן יכולנו לטעון רק על המקום (בתנאי שכל איטרציה משתמשת באותם תאים). כאן מספר האיטרציות קבוע, ולכן אנחנו מקבלים חסם על הזמן. אילו אורך העד היה $|x|^c$ היו לנו $2^{|x|^c}$ איטרציות והטיעון היה קורס.

חלק ב': $\mathrm{P}\subseteq\mathrm{C}_3$

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

נגדיר מכונה $\hat M$ באופן הבא, על קלט $(x,w)$:

1. הרץ את $M$ על $x$ והחזר את אותה תשובה. (העד $w$ נזרק.)

נתבונן ב‑$\hat M$ ונתבונן ב‑$c=1$. אכן $c\ge1$.

$M$ רצה בזמן פולינומי ב‑$|x|$, ומכיוון ש‑$|x|\le|(x,w)|$, המכונה $\hat M$ רצה בזמן פולינומי בגודל הקלט שלה [01:14:41]. (המרצה הדגיש שאין שום צורך "להיכנס פנימה" ולחלץ את הפולינום או הקבוע של $M$ — מריצים את אותה מכונה על אותו קלט, ואין מה לנתח.)

יהי $x\in\Sigma^*$.

נניח $x\in A$. אזי $M$ מקבלת את $x$. נתבונן ב‑$w=0$. אכן $w\in\{0,1\}^1=\{0,1\}^c$, ו‑$\hat M$ מריצה את $M$ על $x$ ומחזירה קבלה, כלומר $\hat M$ מקבלת את $(x,w)$.

נניח $x\notin A$. אזי $M$ דוחה את $x$. יהי $w\in\{0,1\}^1$. אזי $\hat M$ מריצה את $M$ על $x$ ומחזירה דחייה, כלומר $\hat M$ דוחה את $(x,w)$. זה נכון לכל $w$.

לכן $x\in A \iff \exists w\in\{0,1\}^c:\ \hat M \text{ accepts } (x,w)$, כלומר $A\in\mathrm{C}_3$. מכאן $\mathrm{P}\subseteq\mathrm{C}_3$. $\blacksquare$

טעות בזמן אמת, ותיקונה [01:16:26]–[01:16:56]. המרצה כתב תחילה $w=0^c$, ומיד תיקן ל‑$w=0$: "חשבתי על ה‑$2^c$ מההוכחה הקודמת". מכיוון שבחרנו $c=1$, קבוצת העדים היא $\{0,1\}^1=\{0,1\}$, ולכן העד הוא ביט בודד. זו טעות טיפוסית שנולדת מהעתקת תבנית מהסעיף הקודם בלי לבדוק את הפרמטר שנבחר.

התשובה לשלוש השאלות

משני החלקים: $\boxed{\ \mathrm{C}_3=\mathrm{P}\ }$

• האם $\mathrm{C}_3$ מוכלת ב‑$\mathrm{NP}$? כן, וזו טענה ידועה. $\mathrm{C}_3\subseteq\mathrm{P}\subseteq\mathrm{NP}$ (שיעור 4). זו אינה שאלה פתוחה.
• האם $\mathrm{C}_3$ מכילה את $\mathrm{NP}$? שאלה פתוחה. מכיוון ש‑$\mathrm{C}_3=\mathrm{P}$, הטענה $\mathrm{NP}\subseteq\mathrm{C}_3$ שקולה לטענה $\mathrm{NP}\subseteq\mathrm{P}$; ומכיוון ש‑$\mathrm{P}\subseteq\mathrm{NP}$ תמיד, זו בדיוק השאלה $\mathrm{P}=\mathrm{NP}$.
• האם $\mathrm{C}_3$ שווה ל‑$\mathrm{NP}$? שקול ל‑$\mathrm{P}=\mathrm{NP}$, כלומר שאלה פתוחה.

למה לפרק את השוויון לשתי הכלות [01:19:08]–[01:24:27]. סטודנט שאל למה לא לכתוב פשוט "$\mathrm{C}_3=\mathrm{NP}$ אם ורק אם $\mathrm{P}=\mathrm{NP}$, ולכן שאלה פתוחה". התשובה: זה נכון ולא שגוי, אבל הוא מחביא מידע. השוויון הוא צירוף של שתי הכלות, שאחת מהן ידועה (ונכונה) והשנייה פתוחה. השאלה במפורש ביקשה להתייחס לשלוש הטענות בנפרד, ולכן התשובה צריכה להצביע איזה חלק של השוויון הוא הפתוח. המרצה הודה שניסוח השאלה יכול היה להיות בהיר יותר [01:20:43].

תרגיל 4 (סעיף ה'): $\mathrm{C}_5$ — נדון בעל פה בלבד

הסעיף הזה אינו בסיכום; הוא נפתר בעל פה בעשר הדקות האחרונות [01:24:27]–[01:29:44] לבקשת סטודנט, בלי לכתוב על הלוח. הוא מובא כאן בקצרה כי הוא משתמש בדיוק באותה טכניקה.

ההגדרה. $\mathrm{C}_5$ היא מחלקת השפות $A$ עבורן קיים קבוע $c$ כך שקיימת מכונה אי‑דטרמיניסטית $N$ עם זמן ריצה פולינומי המכריעה את $A$, וכך שלכל $x\in\Sigma^*$ מספר הבחירות האי‑דטרמיניסטיות בריצה על $x$ אינו עולה על $c\log|x|$.

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

התשובה: $\mathrm{C}_5=\mathrm{P}$. נזכיר מתסריט הריצה של שיעור 6: נסמן ב‑$\alpha=\max_{q,\sigma}|\delta(q,\sigma)|$ את מספר האפשרויות המרבי בנקודת בחירה. $\alpha$ הוא קבוע של המכונה — הוא נחסם על ידי $|Q|\cdot|\Gamma|\cdot 2$ ואינו תלוי ב‑$x$. לתיאור בחירה אחת דרושים $\lceil\log\alpha\rceil$ ביטים, ולכן לתיאור ריצה שלמה דרושים $\lceil\log\alpha\rceil\cdot c\log|x|$ ביטים, ומספר העדים האפשריים הוא $2^{\lceil\log\alpha\rceil\cdot c\log|x|}=|x|^{\,c\lceil\log\alpha\rceil},$ כלומר פולינומי ב‑$|x|$. עכשיו מפעילים בדיוק את המכונה מחלק א' של תרגיל 3: עוברים על כל תסריטי הריצה, מסמלצים את $N$ על כל אחד מהם דטרמיניסטית, ומקבלים אם אחת הסימולציות קיבלה. מספר האיטרציות פולינומי וכל סימולציה פולינומית, ולכן הסימולציה כולה פולינומית, ומכאן $A\in\mathrm{P}$. הכיוון ההפוך, $\mathrm{P}\subseteq\mathrm{C}_5$, מיידי: מכונה דטרמיניסטית היא מכונה אי‑דטרמיניסטית עם אפס בחירות.

האינטואיציה של המבוך [01:26:04]. מכונה אי‑דטרמיניסטית היא מבוך; העד הוא רשימת ההוראות "בצומת הראשון שמאלה, בשני ימינה". ב‑$\mathrm{NP}$ צריך הוראה לכל צעד — לכן העד ארוך פולינומית ומספר העדים מעריכי. כאן יש רק $c\log|x|$ צמתים שבהם בכלל יש ברירה, ולכן רשימת ההוראות קצרה לוגריתמית ומספר הרשימות האפשריות הוא רק פולינומי.

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

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

• [00:02:07] הכלי הפיזי. המרצה כותב את שתי ההגדרות זו לצד זו על דף, ולא בראש: "אני באופן אישי לא מסוגל לראות את הדברים האלה בראש". ב‑[00:25:17] הוא מסביר למה הוא כותב על דפים ולא על טאבלט — הוא רוצה הרבה דברים מול העיניים בו זמנית.

• [00:04:12]–[00:05:14] מה זה בכלל עד. התשובה לשאלה "מה תפקידו של $w$": ה‑verifier אינו מכריע את $A$; הוא מכונה שאם נותנים לה קצת עזרה היא יודעת לוודא. הדוגמה: לשכנע שמספר הוא פריק דורש פירוק לגורמים, שהוא יקר — אבל בהינתן גורם, מספיק חילוק ארוך. "$\mathrm{NP}$ זה כל הבעיות שבהינתן עד לא מאוד גדול אני יכול לוודא אותן בזמן פולינומי. השאלה $\mathrm{P}$ מול $\mathrm{NP}$ היא כמו לשאול מה יותר קשה — לפתור מבחן או לבדוק אותו" [00:05:14].

• [00:10:00] סדר כמתים. אפשר להחליף בין שני כמתים מאותו סוג ($\exists\exists$ או $\forall\forall$) בלי לשנות את המשמעות; אסור להחליף בין כמתים משני סוגים. בהגדרות שכאן זה מתיר לכתוב "קיים $c$ כך שקיימת $M$" או "קיימת $M$ כך שקיים $c$" באותה מידה.

• [00:19:32]–[00:22:43] $|x|^c$ מול פולינום $q$. סטודנטית שאלה למה מותר להחליף ביניהם, ובצדק: לא כל פולינום הוא מהצורה $n^c$. התשובה בשני חלקים: (א) לכל פולינום $q$ קיים $c$ כך ש‑$q(n)\le n^c$ אסימפטוטית, ואם העד ארוך יותר — האלגוריתם פשוט מתעלם מהזנב; (ב) עבור מספר סופי של ערכי $n$ קטנים שבהם החסם עדיין לא תופס, המכונה יכולה "לזכור בעל פה" את התשובות. מסקנה: שתי הצורות שקולות, ובכתיבה נצמדים לניסוח של השאלה.

• [00:30:17] אזהרה חוזרת. ה‑verifier $M$ אינה מכריעה את $A$, וזה לא עניין של יעילות אלא של ממשק: הקלטים שלה הם זוגות $(x,w)$, ולא אובייקטים שאנחנו שואלים לגביהם שייכות. "היא לא מקבלת בכלל את $x$ ככלט" — זו מכונת verification.

• [00:53:30]–[00:54:03] מה מקבל נקודות. לכתוב "ממשפט ההיררכיה קיימת $A$ שאינה ב‑$\mathrm{NP}$" — תשובה חסרה, לא שגויה: "אתה צודק שזה נובע ממשפט ההיררכיה, אבל איך?". לכתוב "ממשפט ההיררכיה קיימת $A\in\mathrm{EXPSPACE}$ שאינה ב‑$\mathrm{PSPACE}$, ומכיוון ש‑$\mathrm{NP}\subseteq\mathrm{PSPACE}$ היא אינה ב‑$\mathrm{NP}$" — תשובה מלאה.

• [00:55:37]–[00:56:39] מה המכונה בסעיף ב' לא מתיימרת לעשות. סטודנטית התקשתה: המכונה שבנינו ל‑$\mathrm{HALT}$ אינה מכריעה את $\mathrm{HALT}$, אפילו לא חלקית, ולא מזהה בה כלום — אז מה בעצם הוכחנו? התשובה: הגדרת $\mathrm{C}_2$ אינה דורשת הכרעה. היא דורשת רק ש‑לכל $x$ בשפה תהיה אפשרות שהמכונה תקבל, ולכל $x$ מחוץ לשפה תהיה אפשרות שהיא תדחה. "אני מצייט להגדרה, אני לא צריך יותר מזה." זה בדיוק מה שמבלבל בתרגיל.

• [01:16:26] אזהרה על העתקת תבניות. הטעות $w=0^c$ במקום $w=0$ בסעיף ג' נולדה מהעתקת הצורה $0^{|x|^c}$ מהסעיף הקודם. הלקח: אחרי שבוחרים $c$, לבדוק פיזית מהי קבוצת העדים שנוצרה.

• [00:15:20] על הפורמליות. "המטרה אינה שזה יהיה מסודר כי זה קדוש. המטרה היא שזה ייצור לכם בהירות מחשבתית." מותר לכתוב זורם יותר אם אתם בטוחים — "על אחריות המשתמש".

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

• מקור: ההקלטה, [01:24:27]–[01:29:44]. הפער: סעיף ה' של אותה שאלה ($\mathrm{C}_5$ — הגבלת מספר הבחירות האי‑דטרמיניסטיות ל‑$c\log|x|$) נפתר בעל פה ואינו מופיע כלל בחמשת עמודי הסיכום. ההכרעה: נכלל כאן כתרגיל 4, בקצרה ובסימון מפורש שהוא לא נכתב על הלוח, כי הוא מדגים את אותה טכניקה בדיוק ועשוי להופיע במבחן.
• מקור: ההקלטה, [01:29:44] מול הסיכום. הפער: סעיף ד' של השאלה נדחה במפורש לשיעור הבא ("אנחנו נתחיל בסעיף ד' בשיעור הבא") ואינו בסיכום ולא בהקלטה. ההכרעה: לא נכתב כאן דבר עליו. בדיקה שנעשתה לאחר מכן על פני כל הקורפוס העלתה שהסעיף אינו מופיע גם בסיכום 25 ולא בהקלטות 29 או 30: הקלטה 29 נפתחת כבר בתוך תרגיל 3, כלומר תחילת אותו מפגש אינה מוקלטת, ושם נלמד הסעיף ככל הנראה. המחלקות C₁–C₄ שבהקלטה 30 הן וריאציות הסתברותיות על BPP ([00:29:05]) — התנגשות שמות בלבד, ואינן קשורות לסעיף זה. מסקנה: לסעיף ד' אין תיעוד בקורפוס.
• מקור: ההקלטה, [00:52:59]–[00:57:42]. הפער: הסיכום אינו מזכיר כלל ש‑$\mathrm{C}_2$ היא מחלקת כל השפות; זו תוצאה של דיון כיתה. ההכרעה: נכללה כתת‑סעיף נפרד בתרגיל 2, יחד עם ההסבר המתודי מדוע המרצה בחר לא להוכיח אותה.
• מקור: ההקלטה, [00:41:14]–[00:46:30]. הפער: הסיכום מנמק $\mathrm{HALT}\notin\mathrm{NP}$ רק דרך $\mathrm{NP}\subseteq\mathrm{PSPACE}\subseteq\mathrm{R}$; ההקלטה מציגה גם מסלול חלופי דרך משפט ההיררכיה במקום, ומזהירה מפני שימוש שגוי ב‑$\mathrm{P}\subsetneq\mathrm{EXP}$. ההכרעה: שני המסלולים והאזהרה נכתבו במשפט 3.
• מקור: הסיכום, עמוד 2, וההקלטה [00:47:35]–[00:52:28]. הפער: הבנייה "אם התו הראשון של $w$ הוא 1 — קבל" אינה מטפלת בקלט $x=\varepsilon$, שעבורו $c=1$ נותן עד ריק שאין לו תו ראשון. ההכרעה: הבנייה נשמרה כפי שהיא (שלב 2 דוחה במקרה זה), והוספה הערה מפורשת בגוף: המקרה תקין כי $\varepsilon\notin\mathrm{HALT}$ בקידודים המקובלים.
• מקור: הסיכום, עמוד 1, סוף העמוד. הפער: הכיוון $\mathrm{NP}\subseteq\mathrm{C}_1$ נכתב כ"באותו אופן" בלבד, וההקלטה [00:16:56] דילגה עליו במפורש. ההכרעה: נכתב כאן במלואו (תרגיל 1, חלק ב'), לפי דרישת הפירוט המלא.
• מקור: ההקלטה, [01:07:39]. הפער: בכתיבה על הלוח חסר היה הכימות "יהי $w\in\{0,1\}^c$" במקרה $x\notin A$ בהוכחת $\mathrm{C}_3\subseteq\mathrm{P}$; סטודנט תיקן והמרצה אישר. הסיכום כן כולל את השורה. ההכרעה: נכתב עם הכימות, והתיקון תועד כהערה כי הוא מדגים בדיוק את סוג הפער שהתבנית נועדה למנוע.
• מקור: ההקלטה, [01:16:26]. הפער: על הלוח נכתב לרגע $w=0^c$ במקום $w=0$ בהוכחת $\mathrm{P}\subseteq\mathrm{C}_3$. ההכרעה: בגוף נכתב $w=0$ (שכן $c=1$), והטעות תועדה כהערה — היא כשל טיפוסי של העתקת תבנית.
• מקור: הסיכום, עמוד 1, כותרת ירוקה, מול ההקלטה [00:00:00]. הפער: הכותרת קצרה ומקוצרת. הקריאה שנבחרה היא "פתרון מטלה 2", והיא מאושרת מההקלטה — המרצה פותח ב"תפתחו את תרגיל הבית… נתתי לכם פה ארבע מחלקות", ובסוף השיעור [01:29:44] מכריז על מעבר ל"תרגיל שלוש", כלומר למטלה הבאה. ההכרעה: צוטטה בגוף כ"פתרון מטלה 2".
• מקור: שני המקורות. הפער: אין בעמודים האלה שום נתון מזהה של סטודנט. ההכרעה: לא נדרש טיפול.
• מקור: מוסכמות הסימון של הפרויקט. הפער: הסיכום כותב את שמות המחלקות ללא \mathrm. ההכרעה: בקובץ זה שמות מחלקות ובעיות נכתבו ב‑\mathrm לפי §2a, בעוד שאותיות המשתנים ($A$, $M$, $\hat M$, $c$, $w$, $x$) נשמרו בדיוק כבמקור.

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

התוצאות שכדאי לזכור.

המנוע שמאחורי כל השורות. בכל שורה יש הבדל תחבירי אחד מהגדרת $\mathrm{NP}$, והשאלה היחידה היא האם ניתן לגשר עליו ובאיזה כיוון:

1. היפוך קבלה/דחייה — ניתן לגישור בשני הכיוונים, כי המכונה דטרמיניסטית ועוצרת. שוויון.
2. החלפת $\forall$ ב‑$\exists$ — ניתן לגישור בכיוון אחד בלבד (מ‑$\forall$ ל‑$\exists$, מעל תחום לא ריק). הכלה ממש.
3. קיצור העד לאורך שאינו תלוי בקלט — הופך את "לנחש" ל"לעבור על הכול" בזמן פולינומי. קריסה ל‑$\mathrm{P}$.

מלכודות סטנדרטיות.

• לענות על שאלה אחת במקום שלוש. "האם היא שווה ל‑$\mathrm{NP}$" אינה מכסה את "האם היא מכילה" ואת "האם היא מוכלת". פרקו את השוויון לשתי הכלות ואמרו על כל אחת בנפרד: נכונה / שגויה / שקולה לשאלה פתוחה.
• מעבר מ"לכל" ל"קיים" בלי לומר למה. אם אתם עושים אותו — כתבו "הקבוצה אינה ריקה". עדיף פשוט להציג עד קונקרטי.
• "ממשפט ההיררכיה קיימת שפה מחוץ ל‑$\mathrm{NP}$" בלי לפרט את שרשרת ההכלות — תשובה חלקית.
• בלבול בין $\mathrm{P}\subsetneq\mathrm{EXP}$ לבין הפרדה שימושית. הכלה ממש בין קצוות שרשרת אינה אומרת איזו הכלה פנימית היא ממש.
• להעתיק את צורת העד מהסעיף הקודם. אחרי שבוחרים $c$, בדקו מהי בפועל הקבוצה $\{0,1\}^{\ldots}$.
• לשכוח שהמכונה עוצרת. כל הטיעונים "אינה מקבלת ⟸⟹ דוחה" נשענים על כך שהמכונה פולינומית ולכן עוצרת. במכונה אי‑דטרמיניסטית זה נשבר.

רשימת בדיקה — מה צריך לדעת לעשות אחרי השיעור הזה.

• לכתוב את הגדרת ה‑verifier של $\mathrm{NP}$ מהזיכרון, בדיוק, כולל שני החסמים הנפרדים (אורך העד וזמן האימות).
• בהינתן הגדרה חדשה שדומה ל‑$\mathrm{NP}$, לזהות את ההבדל התחבירי היחיד ולנסח בעצמכם האם ניתן לגשר עליו ובאיזה כיוון.
• להוכיח $\mathrm{C}_1=\mathrm{NP}$ בשני הכיוונים, כולל ההצדקה מדוע היפוך המצבים חוקי דווקא במכונה דטרמיניסטית.
• להציג שפה מחוץ ל‑$\mathrm{NP}$ בשתי דרכים: $\mathrm{HALT}$ דרך $\mathrm{NP}\subseteq\mathrm{PSPACE}\subseteq\mathrm{R}$, ושפה מ‑$\mathrm{EXPSPACE}\setminus\mathrm{PSPACE}$ דרך משפט ההיררכיה במקום.
• לבנות את המכונה שעוברת על כל העדים, ולדעת בדיוק מתי היא נותנת $\mathrm{PSPACE}$ (עד פולינומי) ומתי $\mathrm{P}$ (עד קבוע או לוגריתמי).
• לנסח תשובה לשאלה "האם המחלקה שווה ל‑$\mathrm{NP}$" בצורה שמפרידה בין החלק הידוע לחלק הפתוח.