23חזרה למבחן א׳: פתרון מטלה 1 ושאלה 1 ממבחן 2

בקצרה

• זהו הראשון מארבעה שיעורי חזרה. אין בו תיאוריה חדשה: הוא פתרון מלא של מטלה 1 (שאלות 3, 4, 8) ושל שאלה 1 ממבחן 2 (סעיפים א, ד, ה, ו).
• סידור שבע מחלקות סיבוכיות לפי הכלה, וקביעה לגבי כל הכלה האם היא שוויון או הכלה ממש. התוצאה: שלוש מהמחלקות "המפחידות" מתמוטטות ל-$\mathrm{P}$ או ל-$\mathrm{EXP}$, ושלוש ההכלות שנשארות הן ממש — כולן דרך משפט ההיררכיה בזמן.
• המחלקה $\mathrm{TISP}(f,g)$ (חסם זמן וחסם מקום בו-זמנית): מוכיחים ש-$\mathrm{TISP}(f,f)=\mathrm{DTime}(f)$, ומסיקים שהטענה $\bigcup_c\mathrm{TISP}(n^c,n^c)=\mathrm{PSPACE}$ שקולה לשאלה הפתוחה $\mathrm{P}=\mathrm{PSPACE}$.
• שתי הוכחות שונות לחסם עליון על $\mathrm{NP}$: $\mathrm{NP}\subseteq\mathrm{EXP}$ דרך סריקת עץ הריצות של מכונה אי-דטרמיניסטית, ו-$\mathrm{NP}\subseteq\mathrm{PSPACE}$ דרך מעבר על כל העדים. הנקודה שהמרצה הדגיש: אותה מכונה בדיוק משמשת לשתי ההוכחות — היא צנועה במקום ובזבזנית בזמן.
• שלוש טענות רדוקציה שהאלגוריתם המוצע להן שגוי, וזה עיקר השיעור: פלט שאינו קלט חוקי של בעיית היעד; פונקציית הזהות שאינה שומרת על כיוון ההכרעה; ואלגוריתם שבונה מספר אקספוננציאלי של קודקודים. בשלושתן הטענה עצמה נכונה — רק ההוכחה קרסה.
• הסעיף האחרון של שאלת המבחן נגמר בשאלה מושגית: $\mathrm{IS}\le_p\mathrm{MAX}\text{-}\mathrm{IS}$ מתקיים תמיד, ואילו $\mathrm{MAX}\text{-}\mathrm{IS}\le_p\mathrm{IS}$ מתקיים אם ורק אם $\mathrm{NP}=\mathrm{coNP}$.
• מי שקורא רק את הסעיף הזה יכול לדלג — אבל לא כדאי: קובץ זה הוא בדיוק סוג העבודה שהמבחן דורש.

רקע ותלויות

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

• המחלקות העדינות והגסות — $\mathrm{DTime}(f)$, $\mathrm{DSpace}(f)$, ומעליהן $\mathrm{P}=\bigcup_{c\ge1}\mathrm{DTime}(n^c)$, $\mathrm{EXP}=\bigcup_{c\ge1}\mathrm{DTime}(2^{n^c})$, $\mathrm{PSPACE}=\bigcup_{c\ge1}\mathrm{DSpace}(n^c)$ (ראו שיעור 2). שייכות למחלקה גסה היא טענת קיום — קודם "מקלפים" את הקיים ורק אז מגיעים למכונה.
• מונוטוניות — אם $f=O(g)$ אז $\mathrm{DTime}(f)\subseteq\mathrm{DTime}(g)$ (שיעור 2, משפט 4). זהו סוס העבודה של תרגיל 1: כמעט כל הכלה שם היא הערכת סדר גודל אחת ואז ציטוט המשפט.
• הקשר בין מקום לזמן — $\mathrm{space}_M(x)\le\mathrm{time}_M(x)$ (שיעור 2, משפט 2; ובמודל האי-דטרמיניסטי שיעור 4, משפט 3). זהו כל תרגיל 2 סעיף (א).
• משפט ההיררכיה בזמן (שיעור 3, משפט 4) — היחיד שיודע להוכיח הכלה ממש. בלעדיו אין לתרגיל 1 סעיף שני.
• מכונות אי-דטרמיניסטיות ועץ הריצות (שיעור 4) — הגדרת ההכרעה האי-דטרמיניסטית, וספירת הקונפיגורציות.
• שתי ההגדרות של $\mathrm{NP}$ — עם מכונת הכרעה אי-דטרמיניסטית (שיעור 4) ועם מוודא דטרמיניסטי ועד (שיעור 6). התרגיל דורש במפורש הוכחה לכל הגדרה בנפרד.
• $\mathrm{NP}\subseteq\mathrm{PSPACE}$ (שיעור 8, משפט 1) וסגירות $\mathrm{P},\mathrm{NP},\mathrm{PSPACE}$ כלפי מטה תחת $\le_p$ (שיעור 7 ושיעור 8).
• רדוקציות, NP-קשיות ו-NP-שלמות (שיעור 7), והשפות $\mathrm{IS}$ ו-$\mathrm{SAT}$ (שיעורים 5, 7).
• $\mathrm{MAX}\text{-}\mathrm{IS}$, קשיותה משני הצדדים, והקשר ל-$\mathrm{NP}=\mathrm{coNP}$ (שיעור 22).

תזכורת על כיוון הרדוקציה, כי בעל פה מבלבלים בזה תמיד: $A\le_p B$ פירושו שקיימת פונקציה $f$ הניתנת לחישוב בזמן פולינומי כך שלכל $x$ מתקיים $x\in A\iff f(x)\in B$. כלומר $B$ היא הקשה מבין השתיים: מי שיודע לפתור את $B$ יודע לפתור גם את $A$.

הגדרות

הסעיף הזה קצר בכוונה — נזכיר רק את מה שהתרגילים כאן באמת משתמשים בו.

הגדרה 1: $\mathrm{TISP}(f,g)$

תהיינה $f,g:\mathbb N\to\mathbb N$. המחלקה $\mathrm{TISP}(f,g)$ היא מחלקת השפות $A\subseteq\Sigma^*$ שעבורן קיימת מכונת טיורינג $M$ עם אלפבית קלט $\Sigma$ וקיימים קבועים $c,d>0$ כך ש-$M$ מכריעה את $A$, וגם לכל $x\in\Sigma^*$ מתקיים

$\mathrm{time}_M(x)\le c\cdot f(|x|)\qquad\text{and}\qquad \mathrm{space}_M(x)\le d\cdot g(|x|).$

אינטואיציה. השם הוא ראשי תיבות של TIme–SPace: זו מחלקה שדורשת משאב אחד בו-זמנית בשני החסמים — לא "יש מכונה מהירה ויש מכונה חסכונית", אלא "יש מכונה אחת שהיא גם מהירה וגם חסכונית". הסדר של הכמתים הוא הרגיל: קודם המכונה והקבועים, ואחר כך כל הקלטים.

מופע. $\mathrm{PAL}\in\mathrm{TISP}(n^2,n)$: האלגוריתם הנאיבי לפלינדרומים רץ בזמן $O(n^2)$ ואינו כותב מחוץ לאזור הקלט.

אי-מופע שמחדד את הגבול. המכונה שעוברת על כל העדים בהוכחת $\mathrm{NP}\subseteq\mathrm{PSPACE}$ (תרגיל 3(ב) להלן) מעידה על שייכות ל-$\mathrm{DSpace}(n^k)$, אבל לא על שייכות ל-$\mathrm{TISP}(n^k,n^k)$: זמן הריצה שלה אקספוננציאלי. שני החסמים חייבים להיתפס על ידי אותה מכונה.

הגדרה 2: ספיקוּת מסוג NAE ובעיית $\mathrm{4NAE}$

השמה $V$ מספקת נוסחה באופן NAE (Not-All-Equal) אם בכל הסגר יש לפחות ליטרל אחד שערכו True וגם לפחות ליטרל אחד שערכו False — כלומר, ערכי הליטרלים בהסגר אינם כולם שווים. $\mathrm{4NAE}$ היא שפת נוסחאות ה-4CNF שקיימת עבורן השמה המספקת אותן באופן NAE.

אינטואיציה. ספיקוּת רגילה דורשת "לפחות אחד אמת"; NAE דורשת בנוסף "לפחות אחד שקר". זו דרישה סימטרית בין אמת לשקר, ומכאן נובעת התכונה המרכזית שמשמשת בתרגיל 4 (ראו משפט 5).

מופע. $(x_1\vee x_2)$ עם $V(x_1)=\text{True},V(x_2)=\text{False}$ — מסופקת באופן NAE.

אי-מופע. ההשמה $V(x_1)=V(x_2)=\text{True}$ מספקת את $(x_1\vee x_2)$ במובן הרגיל אך לא באופן NAE.

הגדרה 3: $\mathrm{IS}$ ו-$\mathrm{MAX}\text{-}\mathrm{IS}$

$\mathrm{IS}=\{\langle G,k\rangle \mid \text{there is an independent set of size } k \text{ in } G\},$ $\mathrm{MAX}\text{-}\mathrm{IS}=\{\langle G,k\rangle \mid \text{the maximum size of an independent set in } G \text{ equals } k\}.$

אינטואיציה, וזו הנקודה שכל תרגילים 5–6 יושבים עליה. $\mathrm{IS}$ היא טענת קיום בלבד. $\mathrm{MAX}\text{-}\mathrm{IS}$ היא טענת וגם: קיימת קבוצה בגודל $k$, וגם כל קבוצה בלתי תלויה היא בגודל לכל היותר $k$. החלק הראשון ב-$\mathrm{NP}$, החלק השני ב-$\mathrm{coNP}$ — ולכן שתי השפות מתנהגות אחרת לגמרי (ראו שיעור 22).

מופע. $G$ = שני קודקודים ללא קשת, $k=2$: $\langle G,2\rangle\in\mathrm{MAX}\text{-}\mathrm{IS}$ וגם $\langle G,2\rangle\in\mathrm{IS}$.

אי-מופע שמפריד בין השתיים. אותו $G$ עם $k=1$: $\langle G,1\rangle\in\mathrm{IS}$ (קודקוד בודד הוא קבוצה בלתי תלויה בגודל 1), אבל $\langle G,1\rangle\notin\mathrm{MAX}\text{-}\mathrm{IS}$ (המקסימום הוא 2). זהו בדיוק הזוג שמפריך את שני האלגוריתמים בתרגילים 5–6.

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

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

משפט 1: מונוטוניות ביחס לסדר גודל

תהיינה $f,g:\mathbb N\to\mathbb N$. אם $f=O(g)$ אז $\mathrm{DTime}(f)\subseteq\mathrm{DTime}(g)$, ובאותו אופן $\mathrm{DSpace}(f)\subseteq\mathrm{DSpace}(g)$.

ההוכחה — שיעור 2, משפט 4. בשורה אחת: אם $M$ ו-$c$ מעידים על $A\in\mathrm{DTime}(f)$ ו-$f\le c_0\cdot g$, אז אותה מכונה עם הקבוע $c\cdot c_0$ מעידה על $A\in\mathrm{DTime}(g)$. אין בנייה, רק החלפת קבוע.

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

משפט 2: משפט ההיררכיה בזמן

תהיינה $f,g:\mathbb N\to\mathbb N$. נניח כי (1) $g=o(f)$; (2) $f$ ישימה בזמן; (3) $f$ סופר-לינארית. אז $\mathrm{DTime}(g)\subsetneq\mathrm{DTime}\!\left(f^{2}\right).$

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

איך משתמשים בו נכון — וזו הטעות הנפוצה. המשפט אינו אומר "יש שפה קשה"; הוא אומר שקיימת שפה ב-$\mathrm{DTime}(f^2)$ שאינה ב-$\mathrm{DTime}(g)$. כדי להוכיח $\mathcal C_1\subsetneq\mathcal C_2$ בין שתי מחלקות גסות צריך תמיד את אותו ריקוד בן שלושה צעדים:

1. לחסום את המחלקה הקטנה בתוך מחלקה עדינה אחת: $\mathcal C_1\subseteq\mathrm{DTime}(g)$.
2. לבחור $f$ ישימה בזמן וסופר-לינארית כך ש-$g=o(f)$ וגם $\mathrm{DTime}(f^2)\subseteq\mathcal C_2$.
3. להסיק $\mathcal C_1\subseteq\mathrm{DTime}(g)\subsetneq\mathrm{DTime}(f^2)\subseteq\mathcal C_2$.

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

הערה: הסיכום מציין עבור $2^{n^6/2}$ רק שהיא "סופר-לינארית". תנאי הישימוּת בזמן נדרש גם הוא, והוא אכן מתקיים לכל הפונקציות מהצורה $2^{p(n)}$ עבור פולינום $p$ בעל מקדמים טבעיים; השלמתי אותו בגוף הפתרון.

משפט 3: מקום חסום בזמן

לכל מכונה $M$ ולכל קלט $x$ שעליו $M$ עוצרת: $\ \mathrm{space}_M(x)\le\mathrm{time}_M(x)$.

ההוכחה — שיעור 2, משפט 2 (ובמודל האי-דטרמיניסטי: שיעור 4, משפט 3). הטיעון בשורה אחת: בכל צעד הראש זז לכל היותר תא אחד, ולכן מספר התאים השונים שבהם ביקרה המכונה אינו עולה על מספר הצעדים שביצעה.

זהו כל תרגיל 2 סעיף (א) — הכיוון הלא-טריוויאלי שם הוא ציטוט אחד של המשפט הזה.

משפט 4: $\mathrm{NP}\subseteq\mathrm{PSPACE}$ (בהגדרת המוודא)

כל שפה ב-$\mathrm{NP}$ ניתנת להכרעה במקום פולינומי.

ההוכחה במלואה — שיעור 8, משפט 1. המכונה $M_A$ מקבלת $x$, מחשבת את $q(|x|)$, ועוברת בסדר לקסיקוגרפי על כל $w\in\{0,1\}^{q(|x|)}$; לכל $w$ היא מריצה את המוודא $M$ על $(x,w)$ ומקבלת אם $M$ קיבלה; בסוף הלולאה היא דוחה. הנקודה שהכול תלוי בה: לפני כל איטרציה מוחקים את סרט העבודה, ולכן המקום אינו מצטבר, אף שמספר האיטרציות אקספוננציאלי.

מה שהסיכום מוסיף כאן ואינו בשיעור 8 (ההערה הכחולה בעמוד 5): אותה מכונה בדיוק, אם מסתכלים עליה במשקפי זמן ולא במשקפי מקום, רצה בזמן $2^{q(|x|)}\cdot\mathrm{poly}(|x|)$ — אקספוננציאלי — ולכן היא מוכיחה בו-זמנית גם $\mathrm{NP}\subseteq\mathrm{EXP}$. זה הופך אותה לפתרון חלופי מלא לסעיף (א) של תרגיל 3, בלי לגעת בעץ הריצות.

משפט 5: עץ הריצות של מכונה אי-דטרמיניסטית

זהו החישוב שסעיף (א) של תרגיל 3 בנוי עליו, ולכן הוא כתוב כאן במלואו.

תהא $M$ מכונת טיורינג אי-דטרמיניסטית ויהי $x$ קלט. נתבונן בעץ כל הריצות האפשריות של $M$ על $x$: הקודקודים הם הקונפיגורציות המופיעות בריצות, והקשתות הן צעדי $\delta$. אז:

1. מספר הבנים של כל צומת חסום ב-$\alpha=|Q|\cdot|\Gamma|\cdot 2$;
2. אם $\mathrm{time}_M(x)\le T$ אז עומק העץ חסום ב-$T$;
3. מספר הצמתים בעץ חסום ב-$\displaystyle\sum_{i=0}^{T}\alpha^{i}=O\!\left(\alpha^{T+1}\right)=O\!\left(2^{(\lg\alpha)(T+1)}\right)$.

הוכחה. (1) צעד יחיד של $M$ מקונפיגורציה נתונה נקבע כולו על ידי שלישייה: המצב שאליו עוברים ($|Q|$ אפשרויות), האות הנכתבת ($|\Gamma|$ אפשרויות), וכיוון תזוזת הראש (שתי אפשרויות). לכן $\delta$ יכולה להציע לכל היותר $|Q|\cdot|\Gamma|\cdot2$ המשכים שונים, וזה מספר הבנים.

(2) מסלול מהשורש לעלה הוא בדיוק ריצה אפשרית אחת, ואורכו הוא מספר הצעדים באותה ריצה. לפי הגדרת $\mathrm{time}_M(x)$ כמקסימום על פני כל הריצות האפשריות, אורך כל מסלול חסום ב-$T$.

(3) עץ שבו לכל צומת לכל היותר $\alpha$ בנים ושעומקו לכל היותר $T$ מכיל לכל היותר $\alpha^i$ צמתים ברמה $i$, ולכן לכל היותר $1+\alpha+\alpha^2+\dots+\alpha^{T}$ צמתים בסך הכול. זהו סכום סדרה הנדסית, וכשהמנה קבועה וגדולה מ-1 הוא מסדר גודל האיבר האחרון: $O(\alpha^{T+1})$. הכתיבה מחדש בבסיס 2 היא זהות: $\alpha^{T+1}=2^{(\lg\alpha)(T+1)}$. $\blacksquare$

הערה: בסיכום החזקה נכתבה פעמיים $|x|^2$ ופעם אחת $|x|^c$ באותו חישוב עצמו. מכיוון שהחסם על זמן הריצה שממנו הכול נגזר הוא $d\cdot|x|^c$, המעריך הנכון בכל שלושת המקומות הוא $c$; כך כתוב כאן.

משפט 6: התכונה הסימטרית של ספיקוּת NAE

תהא $\varphi$ נוסחת CNF ותהא $V$ השמה למשתני $\varphi$ המספקת אותה באופן NAE. תהא $\widehat V$ ההשמה המשלימה, כלומר $\widehat V(y)=\neg V(y)$ לכל משתנה $y$. אז גם $\widehat V$ מספקת את $\varphi$ באופן NAE.

הוכחה. יהי $C$ הסגר של $\varphi$. לפי ההנחה קיימים ב-$C$ ליטרל $\ell_1$ שערכו תחת $V$ הוא True וליטרל $\ell_2$ שערכו תחת $V$ הוא False. היפוך ערכו של כל משתנה הופך את ערכו של כל ליטרל, ולכן תחת $\widehat V$ ערכו של $\ell_1$ הוא False וערכו של $\ell_2$ הוא True. שוב יש ב-$C$ ליטרל אמת וליטרל שקר, כלומר $C$ מסופק באופן NAE. הטענה נכונה לכל הסגר, ולכן $\widehat V$ מספקת את $\varphi$ באופן NAE. $\blacksquare$

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

משפט 7: מתי $\mathrm{MAX}\text{-}\mathrm{IS}\le_p\mathrm{IS}$

$\mathrm{MAX}\text{-}\mathrm{IS}\le_p\mathrm{IS}$ אם ורק אם $\mathrm{NP}=\mathrm{coNP}$.

ההוכחה — שיעור 22, שבו הוכח ש-$\mathrm{MAX}\text{-}\mathrm{IS}$ היא גם NP-קשה וגם coNP-קשה, וש-$\mathrm{MAX}\text{-}\mathrm{IS}\in\mathrm{NP}\cup\mathrm{coNP}$ שקולה ל-$\mathrm{NP}=\mathrm{coNP}$. שתי הרוחות של הטיעון, בקצרה, כדי שהמסקנה בתרגיל 6 לא תיפול מהשמיים:

• ($\Rightarrow$) נניח $\mathrm{MAX}\text{-}\mathrm{IS}\le_p\mathrm{IS}$. מכיוון ש-$\mathrm{IS}\in\mathrm{NP}$ ו-$\mathrm{NP}$ סגורה כלפי מטה תחת $\le_p$ (שיעור 7), נובע $\mathrm{MAX}\text{-}\mathrm{IS}\in\mathrm{NP}$. אבל $\mathrm{MAX}\text{-}\mathrm{IS}$ היא coNP-קשה, ושפה coNP-קשה שנמצאת ב-$\mathrm{NP}$ גוררת $\mathrm{coNP}\subseteq\mathrm{NP}$ ומכאן $\mathrm{NP}=\mathrm{coNP}$.
• ($\Leftarrow$) נניח $\mathrm{NP}=\mathrm{coNP}$. השייכות $\langle G,k\rangle\in\mathrm{MAX}\text{-}\mathrm{IS}$ היא חיתוך של שתי טענות: "קיימת קבוצה בלתי תלויה בגודל $k$" (ב-$\mathrm{NP}$) ו"כל קבוצה בלתי תלויה היא בגודל לכל היותר $k$" (ב-$\mathrm{coNP}$). תחת ההנחה שתיהן ב-$\mathrm{NP}$, ו-$\mathrm{NP}$ סגורה לחיתוך, ולכן $\mathrm{MAX}\text{-}\mathrm{IS}\in\mathrm{NP}$. מכיוון ש-$\mathrm{IS}$ היא NP-שלמה, קיימת רדוקציה $\mathrm{MAX}\text{-}\mathrm{IS}\le_p\mathrm{IS}$.

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

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

תרגיל 1 (מטלה 1, שאלה 4): סידור שבע מחלקות סיבוכיות

הנוסח. נתונות שבע מחלקות סיבוכיות:

$\mathrm{P},\quad \mathrm{EXP},\quad \mathrm{DTime}\!\left(2^{(n^6)}\right),\quad \bigcup_{c\ge1}\mathrm{DTime}\!\left(n^{(2^c)}\right),\quad \bigcup_{c\ge1}\mathrm{DTime}\!\left(c^{cn}\right),\quad \bigcup_{c\ge1}\mathrm{DTime}\!\left(c^{n^c}\right),\quad \bigcup_{c\ge1}\mathrm{DTime}\!\left(n^{n^c}\right).$

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

התשובה.

$\bigcup_{c\ge1}\mathrm{DTime}\!\left(n^{2^c}\right)\;=\;\mathrm{P}\;\subsetneq\;\bigcup_{c\ge1}\mathrm{DTime}\!\left(c^{cn}\right)\;\subsetneq\;\mathrm{DTime}\!\left(2^{n^6}\right)\;\subsetneq\;\mathrm{EXP}\;=\;\bigcup_{c\ge1}\mathrm{DTime}\!\left(c^{n^c}\right)\;=\;\bigcup_{c\ge1}\mathrm{DTime}\!\left(n^{n^c}\right).$

כלומר: שלוש מהמחלקות מתמוטטות למחלקות מוכרות, ושלוש ההכלות שנשארות הן ממש.

שלב א: $\mathrm{P}=\bigcup_{c\ge1}\mathrm{DTime}(n^{2^c})$

כיוון ראשון. תהא $A\in\mathrm{P}$. לפי הגדרת $\mathrm{P}$ קיים $c\ge1$ כך ש-$A\in\mathrm{DTime}(n^c)$. לכל $c\ge1$ מתקיים $c\le 2^c$, ולכן לכל $n\ge1$ מתקיים $n^c\le n^{2^c}$, כלומר $n^c=O(n^{2^c})$. לפי משפט 1 נובע $A\in\mathrm{DTime}(n^{2^c})$, ובפרט $A\in\bigcup_{c\ge1}\mathrm{DTime}(n^{2^c})$.

כיוון שני. תהא $A\in\bigcup_{c\ge1}\mathrm{DTime}(n^{2^c})$. לפי הגדרת האיחוד קיים $c\ge1$ כך ש-$A\in\mathrm{DTime}(n^{2^c})$. נסמן $d=2^c$; זהו מספר טבעי המקיים $d\ge1$, ולכן $A\in\mathrm{DTime}(n^{d})\subseteq\bigcup_{d\ge1}\mathrm{DTime}(n^{d})=\mathrm{P}$. $\blacksquare$

הערה: בסיכום נכתב בשורה האחרונה $\bigcup_{d\ge1}\mathrm{DTime}(2^{d})=\mathrm{P}$. זו פליטת קולמוס: המחלקה $\mathrm{DTime}(2^d)$ עבור $d$ קבוע היא זמן קבוע, וההגדרה של $\mathrm{P}$ היא $\bigcup_{d\ge1}\mathrm{DTime}(n^{d})$. תוקן כאן.

מה הרעיון מאחורי התוצאה. $2^c$ נראה מפחיד, אבל הוא חזקה קבועה — כשמאחדים על כל $c$, "החזקה הקבועה הגדולה" מתגלה כסתם עוד חזקה קבועה. זה בדיוק מה שהמרצה חזר עליו בשיעור העוקב: "לא כל מה שיש לו צורה מעריכית הוא מעריכי; מה שמעניין הוא אם זה מעריכי כפונקציה של אורך הקלט" ([00:59:55], הקלטת שיעור 24).

שלב ב: $\mathrm{EXP}=\bigcup_{c\ge1}\mathrm{DTime}(n^{n^c})$

כיוון ראשון. תהא $A\in\mathrm{EXP}$, כלומר קיים $c\ge1$ עם $A\in\mathrm{DTime}(2^{n^c})$. לכל $n\ge2$ מתקיים $2\le n$ ולכן $2^{n^c}\le n^{n^c}$, כלומר $2^{n^c}=O(n^{n^c})$. לפי משפט 1, $A\in\mathrm{DTime}(n^{n^c})$, ובפרט $A$ באיחוד.

כיוון שני. תהא $A\in\bigcup_{c\ge1}\mathrm{DTime}(n^{n^c})$, ויהי $c\ge1$ עם $A\in\mathrm{DTime}(n^{n^c})$. נכתוב

$n^{n^c}=2^{\,n^c\cdot\lg n}.$

מכיוון ש-$\lg n\le n$ לכל $n\ge1$, מתקיים $n^c\cdot\lg n\le n^{c+1}$, ולכן $n^{n^c}\le 2^{\,n^{c+1}}$, כלומר $n^{n^c}=O\!\left(2^{n^{c+1}}\right)$. לפי משפט 1, $A\in\mathrm{DTime}\!\left(2^{n^{c+1}}\right)\subseteq\mathrm{EXP}$. $\blacksquare$

שלב ג: $\mathrm{EXP}=\bigcup_{c\ge1}\mathrm{DTime}(c^{n^c})$

הסיכום אינו מטפל במחלקה הזו; היא נסגרת באותה טכניקה בדיוק ולכן היא כתובה כאן במלואה.

כיוון ראשון ($\supseteq$). יהי $c\ge1$. אז $c^{n^c}=2^{\,(\lg c)\cdot n^c}$. הגודל $\lg c$ הוא קבוע שאינו תלוי ב-$n$, ולכן לכל $n$ גדול מספיק $(\lg c)\cdot n^c\le n^{c+1}$, כלומר $c^{n^c}=O\!\left(2^{n^{c+1}}\right)$. לפי משפט 1, $\mathrm{DTime}(c^{n^c})\subseteq\mathrm{DTime}\!\left(2^{n^{c+1}}\right)\subseteq\mathrm{EXP}$, ומכאן שגם האיחוד מוכל ב-$\mathrm{EXP}$.

כיוון שני ($\subseteq$). תהא $A\in\mathrm{EXP}$ עם $A\in\mathrm{DTime}(2^{n^c})$. נבחר $c'=\max\{c,2\}$. אז $2^{n^c}\le 2^{n^{c'}}\le (c')^{\,n^{c'}}$ (האי-שוויון האחרון כי $c'\ge2$), ולכן $A\in\mathrm{DTime}\!\left((c')^{n^{c'}}\right)$, שהוא אחד מאיברי האיחוד. $\blacksquare$

שלב ד: $\bigcup_{c\ge1}\mathrm{DTime}(c^{cn})$ — המחלקה שנופלת בין $\mathrm{P}$ ל-$\mathrm{DTime}(2^{n^6})$

גם המחלקה הזו אינה מטופלת בסיכום. נכתוב $c^{cn}=2^{\,c\lg c\cdot n}$, ולכן

$\bigcup_{c\ge1}\mathrm{DTime}\!\left(c^{cn}\right)=\bigcup_{k\ge1}\mathrm{DTime}\!\left(2^{kn}\right),$

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

• $\mathrm{P}\subseteq\mathcal E$: לכל $d$ קבוע מתקיים $n^d=O(2^n)$, ולכן $\mathrm{DTime}(n^d)\subseteq\mathrm{DTime}(2^n)$ לכל $d$, ומכאן $\mathrm{P}\subseteq\mathrm{DTime}(2^{n})\subseteq\mathcal E$.
• $\mathcal E\subseteq\mathrm{DTime}(2^{n^6})$: לכל $k$ קבוע ולכל $n$ גדול מספיק מתקיים $kn\le n^6$, ולכן $2^{kn}=O\!\left(2^{n^6}\right)$, ולפי משפט 1 גם $\mathrm{DTime}(2^{kn})\subseteq\mathrm{DTime}(2^{n^6})$.

שלב ה: ההכלה $\mathrm{DTime}(2^{n^6})\subseteq\mathrm{EXP}$

מיידית מההגדרה: $\mathrm{EXP}=\bigcup_{c\ge1}\mathrm{DTime}(2^{n^c})$ והמחלקה שלנו היא האיבר $c=6$.

שלב ו: שלוש ההכלות הן ממש

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

(1) $\mathrm{P}\subsetneq\mathcal E$. ראינו ש-$\mathrm{P}\subseteq\mathrm{DTime}(2^{n})$. נבחר $f(n)=2^{2n}$: היא ישימה בזמן, סופר-לינארית, ומתקיים $2^{n}=o(2^{2n})$ שכן $2^n/2^{2n}=2^{-n}\to0$. לפי משפט 2,

$\mathrm{DTime}(2^{n})\subsetneq\mathrm{DTime}\!\left(\left(2^{2n}\right)^2\right)=\mathrm{DTime}\!\left(2^{4n}\right)\subseteq\mathcal E,$

ולכן קיימת שפה ב-$\mathcal E$ שאינה ב-$\mathrm{DTime}(2^n)$ ובפרט אינה ב-$\mathrm{P}$.

(2) $\mathcal E\subsetneq\mathrm{DTime}(2^{n^6})$. ראשית, $\mathcal E\subseteq\mathrm{DTime}(2^{n^2})$: לכל $k$ קבוע ולכל $n\ge k$ מתקיים $kn\le n^2$. כעת נבחר $f(n)=2^{n^3}$ — ישימה בזמן וסופר-לינארית — ומתקיים $2^{n^2}=o\!\left(2^{n^3}\right)$. לפי משפט 2,

$\mathrm{DTime}\!\left(2^{n^2}\right)\subsetneq\mathrm{DTime}\!\left(2^{2n^3}\right)\subseteq\mathrm{DTime}\!\left(2^{n^6}\right),$

כאשר ההכלה האחרונה היא משפט 1 עם $2n^3\le n^6$ לכל $n\ge2$.

(3) $\mathrm{DTime}(2^{n^6})\subsetneq\mathrm{EXP}$. נבחר $f(n)=2^{n^7}$; אז $2^{n^6}=o\!\left(2^{n^7}\right)$, ולפי משפט 2

$\mathrm{DTime}\!\left(2^{n^6}\right)\subsetneq\mathrm{DTime}\!\left(2^{2n^7}\right)\subseteq\mathrm{DTime}\!\left(2^{n^8}\right)\subseteq\mathrm{EXP}.$

ההוכחה שהסיכום כותב במפורש: $\mathrm{P}\subsetneq\mathrm{DTime}(2^{n^6})$

הסיכום אינו עובר דרך $\mathcal E$ אלא מוכיח ישירות את ההכלה-ממש הזו, וכדאי לראות גם אותה כי היא מדגימה את הבחירה הנוחה של $f$:

תהא $A\in\mathrm{P}$, כלומר $A\in\mathrm{DTime}(n^c)$ עבור $c$ כלשהו. מתקיים $n^c=O\!\left(2^{n^5}\right)$, ולכן $\mathrm{P}\subseteq\mathrm{DTime}\!\left(2^{n^5}\right)$. כעת $2^{n^5}=o\!\left(2^{n^6/2}\right)$, והפונקציה $2^{n^6/2}$ סופר-לינארית וישימה בזמן, ולכן לפי משפט ההיררכיה בזמן

$\mathrm{DTime}\!\left(2^{n^5}\right)\subsetneq\mathrm{DTime}\!\left(\left(2^{n^6/2}\right)^{2}\right)=\mathrm{DTime}\!\left(2^{n^6}\right),$

ומכאן $\mathrm{P}\subsetneq\mathrm{DTime}(2^{n^6})$. $\blacksquare$

ובאותו אופן, השרשרת שהסיכום מסמן בכחול כתקציר של כל התרגיל:

$\mathrm{P}\subseteq\mathrm{DTime}\!\left(2^{n}\right)\subsetneq\mathrm{DTime}\!\left(2^{n^2}\right)\subseteq\mathrm{EXP}.$

תרגיל 2 (מטלה 1, שאלה 3): המחלקה $\mathrm{TISP}(f,g)$

הנוסח. עבור שתי פונקציות $f,g:\mathbb N\to\mathbb N$ נגדיר את מחלקת הסיבוכיות $\mathrm{TISP}(f,g)$ כמחלקת השפות $A\subseteq\Sigma^*$ עבורן קיימת מכונת טיורינג $M$ עם אלפבית קלט $\Sigma$ כך שקיימים קבועים $c,d>0$ כך ש-$M$ מכריעה את $A$ וגם לכל $x\in\Sigma^*$ מתקיים $\mathrm{time}_M(x)\le c\cdot f(|x|)$ וגם $\mathrm{space}_M(x)\le d\cdot g(|x|)$.

(א) הוכיחו או הפריכו: לכל פונקציה $f$ מתקיים $\mathrm{TISP}(f,f)=\mathrm{DTime}(f)$.

התשובה: הטענה נכונה. תהא $f:\mathbb N\to\mathbb N$.

כיוון ראשון: $\mathrm{TISP}(f,f)\subseteq\mathrm{DTime}(f)$. תהא $A\in\mathrm{TISP}(f,f)$. לפי ההגדרה קיימת מכונה $M$ וקיימים קבועים $c,d>0$ כך ש-$M$ מכריעה את $A$ ולכל $x\in\Sigma^*$ מתקיים $\mathrm{time}_M(x)\le c\cdot f(|x|)$ וגם $\mathrm{space}_M(x)\le d\cdot f(|x|)$. נתבונן ב-$M$ ונתבונן ב-$c$. $M$ מכריעה את $A$; יהי $x$; אז $\mathrm{time}_M(x)\le c\cdot f(|x|)$. אלה בדיוק שני התנאים בהגדרת $\mathrm{DTime}(f)$, ולכן $A\in\mathrm{DTime}(f)$.

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

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

$\mathrm{space}_M(x)\le\mathrm{time}_M(x)\le c\cdot f(|x|)=d\cdot f(|x|).$

לכן $M$ עם הקבועים $c,d$ מעידה על $A\in\mathrm{TISP}(f,f)$. $\blacksquare$

מה הרעיון. החסם המשותף $\mathrm{TISP}(f,f)$ אינו מוסיף כלום מעל חסם הזמן, מפני שחסם הזמן כבר כולל בתוכו חסם מקום זהה. המחלקה מתחילה להיות מעניינת רק כאשר $g$ קטנה ממש מ-$f$ — למשל $\mathrm{TISP}(2^{n},n^2)$, שבה יש מתח אמיתי בין שני המשאבים.

(ג) האם הטענה הבאה נכונה, אינה נכונה או שקולה לשאלה פתוחה? טענה: $\bigcup_{c\ge1}\mathrm{TISP}(n^c,n^c)=\mathrm{PSPACE}$.

התשובה: הטענה שקולה לשאלה פתוחה — לשאלה האם $\mathrm{P}=\mathrm{PSPACE}$.

הפתרון. לפי סעיף (א), לכל $c\ge1$ מתקיים $\mathrm{TISP}(n^c,n^c)=\mathrm{DTime}(n^c)$. שוויון בין איברי שני איחודים גורר שוויון בין האיחודים, ולכן

$\bigcup_{c\ge1}\mathrm{TISP}(n^c,n^c)=\bigcup_{c\ge1}\mathrm{DTime}(n^c)=\mathrm{P}.$

מכאן שהטענה $\bigcup_{c\ge1}\mathrm{TISP}(n^c,n^c)=\mathrm{PSPACE}$ שקולה בדיוק לטענה $\mathrm{P}=\mathrm{PSPACE}$, שהיא שאלה פתוחה. $\blacksquare$

חידוד שכדאי לכתוב במבחן. ההכלה $\mathrm{P}\subseteq\mathrm{PSPACE}$ ידועה (שיעור 2, משפט 5). לכן החלק הפתוח בטענה הוא רק ההכלה ההפוכה, $\mathrm{PSPACE}\subseteq\bigcup_c\mathrm{TISP}(n^c,n^c)$. הפירוק הזה — "איזה חלק מהשוויון ידוע ואיזה פתוח" — הוא בדיוק מה שהמרצה דרש בשיעור העוקב כשעסק בשאלה מאותו סוג ([01:22:18]–[01:23:54], הקלטת שיעור 24): "שוויון הוא טענת 'וגם', והוא מחביא בפנים שאחת הטענות ידועה והשנייה היא שאלה פתוחה".

תרגיל 3 (מטלה 1, שאלה 8): שני חסמים עליונים על $\mathrm{NP}$

הנוסח. (א) הוכיחו כי $\mathrm{NP}\subseteq\mathrm{EXP}$ בעזרת ההגדרה של $\mathrm{NP}$ עם מכונת הכרעה אי-דטרמיניסטית. (ב) הוכיחו כי $\mathrm{NP}\subseteq\mathrm{PSPACE}$ בעזרת ההגדרה של $\mathrm{NP}$ עם מכונת וידוא דטרמיניסטית.

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

(א) $\mathrm{NP}\subseteq\mathrm{EXP}$ דרך עץ הריצות

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

מה יש לנו ביד. לפי משפט 5, עץ כל הריצות האפשריות של $M$ על $x$ הוא עץ שבו:

• הקודקודים הם הקונפיגורציות המופיעות בריצות, והקשתות הן צעדי $\delta$;
• מספר הבנים של כל צומת חסום ב-$\alpha=|Q|\cdot|\Gamma|\cdot2$ — קבוע התלוי ב-$M$ בלבד ולא ב-$x$;
• עומק העץ חסום ב-$d\cdot|x|^c$;
• מספר הצמתים חסום ב-$\displaystyle 1+\alpha+\alpha^2+\dots+\alpha^{d|x|^c}=O\!\left(\alpha^{\,d|x|^c+1}\right)=O\!\left(2^{\,(\lg\alpha)\cdot d\cdot|x|^c\;+\;\lg\alpha}\right).$

הבנייה. נבנה מכונה דטרמיניסטית $\widehat M$ באופן הבא. על קלט $x$:

1. $\widehat M$ תעבור בסריקת DFS על כל הריצות האפשריות של $M$ על $x$. 1.1 אם קיים מסלול מקבל, כלומר קיימת ריצה אפשרית שבסופה $M$ במצב מקבל — $\widehat M$ מקבלת.
2. אחרת, $\widehat M$ דוחה.

איך מיישמים את ה-DFS. בכל רגע $\widehat M$ מחזיקה על סרט העבודה את הקונפיגורציה הנוכחית ואת מחסנית המסלול מהשורש אליה: לכל רמה במסלול נשמרת השלישייה $t\in Q\times\Gamma\times\{L,R\}$ שנבחרה שם, כלומר איזה ענף כבר נוסה. אורך המסלול חסום בעומק העץ, ולכן המחסנית מחזיקה לכל היותר $d\cdot|x|^c$ רשומות, כל אחת בגודל $O(|\langle M\rangle|)$.

נכונות. $M$ מכריעה את $A$ באופן אי-דטרמיניסטי, כלומר: $x\in A$ אם ורק אם קיימת ריצה אפשרית מקבלת של $M$ על $x$; וכן, בכל ריצה אפשרית $M$ עוצרת, ולכן העץ סופי ו-$\widehat M$ תמיד מסיימת את הסריקה. אם $x\in A$, קיימת ריצה מקבלת; היא מסלול בעץ, וה-DFS סורק את כל המסלולים ולכן יגיע אליה, ו-$\widehat M$ תקבל. אם $x\notin A$, אין ריצה מקבלת; שום עלה בעץ אינו מקבל, שלב 1.1 לא יופעל לעולם, ו-$\widehat M$ תדחה בשלב 2. לכן $\widehat M$ מכריעה את $A$.

ניתוח זמן ריצה. נפרק לשניים:

• מחיר של צומת בודד. כדי לחשב את הבנים של קונפיגורציה, $\widehat M$ צריכה לאתר את הרשומות הרלוונטיות בטבלת המעברים של $M$ ולכתוב את הקונפיגורציה החדשה. טבלת המעברים היא חלק מ-$\langle M\rangle$, וסריקה שלה עולה לכל היותר סדר גודל של $|\langle M\rangle|^2$. זהו קבוע — הוא תלוי ב-$M$ בלבד, לא ב-$x$.
• מספר הצמתים. חסום ב-$O\!\left(2^{(\lg\alpha)d|x|^c+\lg\alpha}\right)$ כפי שחישבנו.

בסך הכול, עם $d'=(\lg\alpha)\cdot d$ ועם בליעת הקבועים $|\langle M\rangle|^2$ ו-$2^{\lg\alpha}$,

$\mathrm{time}_{\widehat M}(x)=O\!\left(2^{\,d'\cdot|x|^{c}}\right).$

לבסוף, $d'\cdot|x|^c\le|x|^{c+1}$ לכל $|x|$ גדול מספיק, ולכן $\mathrm{time}_{\widehat M}(x)=O\!\left(2^{|x|^{c+1}}\right)$, כלומר $A\in\mathrm{DTime}\!\left(2^{n^{c+1}}\right)\subseteq\mathrm{EXP}$. $\blacksquare$

איפה בדיוק "נשרף" הזמן, ולמה זה בלתי נמנע בגישה הזו. לא בעומק העץ — הוא פולינומי — אלא ברוחב: מספר הענפים מוכפל ב-$\alpha$ בכל רמה, ולכן העץ גדל כמו $\alpha^{h}$, כאשר $h$ הוא עומק העץ. כל אחד מהגורמים הוא תמים בפני עצמו; המכפלה שלהם היא האקספוננט.

(ב) $\mathrm{NP}\subseteq\mathrm{PSPACE}$ דרך מכונת הווידוא

הסיכום מסמן בחץ כחול שהסעיף הזה נפתר בשיעור, ומתמצת את הפתרון בשלוש שורות: בניית מכונה שעוברת על כל העדים האפשריים; המכונה הזו רצה בזמן אקספוננציאלי; ולכן אותה הוכחה בדיוק מראה גם $\mathrm{NP}\subseteq\mathrm{EXP}$.

הפתרון — ההוכחה המלאה נמצאת בשיעור 8, משפט 1, ולא נחזור עליה כאן. בקצרה: תהא $A\in\mathrm{NP}$ עם מוודא דטרמיניסטי $M$ שזמן ריצתו חסום בפולינום $p$, ועם פולינום $q$ החוסם את אורך העד. נגדיר מכונה דטרמיניסטית $M_A$ שעל קלט $x$ מחשבת את $q(|x|)$ ועוברת בסדר לקסיקוגרפי על כל $w\in\{0,1\}^{q(|x|)}$, מריצה את $M$ על $(x,w)$, ומקבלת אם $M$ קיבלה; בסוף הלולאה היא דוחה. הנקודה הקריטית: מוחקים את סרט העבודה לפני כל איטרציה, ולכן כל האיטרציות משתמשות באותם תאים והמקום אינו מצטבר. בסך הכול $\mathrm{space}_{M_A}(x)=O\!\left(q(|x|)+p(|x|+q(|x|))\right)$, שהוא פולינום.

התוספת שהשיעור הזה עושה. נסתכל על אותה מכונה במשקפי זמן. מספר האיטרציות הוא $2^{q(|x|)}$, וכל איטרציה עולה $p(|x|+q(|x|))$, ולכן

$\mathrm{time}_{M_A}(x)=O\!\left(2^{q(|x|)}\cdot p\big(|x|+q(|x|)\big)\right)=O\!\left(2^{|x|^{k}}\right)$

עבור $k$ מתאים, שכן פולינום נבלע בקלות במעריך. לכן אותה בנייה מוכיחה גם $A\in\mathrm{EXP}$ — וזהו פתרון חלופי מלא לסעיף (א), שאינו נזקק לעץ הריצות כלל.

הערה: בהקלטת השיעור העוקב המרצה חוזר במפורש על הקשר הזה: כשנשאל למה מכונה שעוברת על כל העדים מזכירה משהו, הוא עונה "כשהראיתי ש-$\mathrm{NP}$ מוכלת ב-$\mathrm{PSPACE}$ אמרתי שאני יכול לעבור על כל העדים... כל איטרציה נעשית באותו מקום של האיטרציה הקודמת" ([01:02:35]–[01:03:39], הקלטת שיעור 24). המכניזם זהה; רק המשאב שסופרים משתנה.

תרגיל 4 (מבחן 2, שאלה 1א): $\mathrm{3SAT}\le_p\mathrm{4NAE}$

הנוסח. טענה: $\mathrm{3SAT}\le_p\mathrm{4NAE}$. אלגוריתם: בהינתן קידוד של נוסחה $\varphi$ מצורת 3CNF נוסיף לכל אחד מהסגרי $\varphi$ משתנה חדש $x$ (אותו משתנה לכל ההסגרים) ונחזיר את הנוסחה המתקבלת בצירוף השמה הנותנת ל-$x$ את הערך False.

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

ההפרכה. אם הקלט הוא נוסחה $\varphi$ מצורת 3CNF, האלגוריתם מחזיר זוג: נוסחה $\widehat\varphi$ מצורת 4CNF והשמה. אבל קלט חוקי של $\mathrm{4NAE}$ הוא נוסחת 4CNF בלבד; זוג של נוסחה והשמה אינו מופע של הבעיה. רדוקציה חייבת לשלוח מחרוזות למופעים של בעיית היעד, ולכן האלגוריתם הזה אינו מהווה רדוקציה בזמן פולינומי מ-$\mathrm{3SAT}$ ל-$\mathrm{4NAE}$.

מדוע בכלל נולד הרעיון להחזיר גם השמה, ולמה אין בו צורך. מי שכתב את האלגוריתם רצה "לכפות" על הפותר את הערך $x=\text{False}$, כי בלי זה לא ברור איך לחלץ השמה מספקת ל-$\varphi$. אבל את הכפייה הזו מקבלים בחינם מהתכונה הסימטרית של ספיקוּת NAE:

התכונה החשובה לגבי ספיקוּת באופן NAE: אם $\varphi$ נוסחה ו-$V$ השמה עבור משתני $\varphi$ המספקת אותה באופן NAE, אזי ההשמה $\widehat V$, ההפכית ל-$V$ בכל ערך, אף היא מספקת את $\varphi$ באופן NAE (משפט 6).

הרדוקציה המתוקנת ופתרונה המלא. האלגוריתם: בהינתן $\varphi=\bigwedge_{i=1}^{m}(\ell_{i,1}\vee\ell_{i,2}\vee\ell_{i,3})$ מצורת 3CNF, נוסיף משתנה חדש יחיד $x$ לכל ההסגרים ונחזיר רק את הנוסחה

$\widehat\varphi=\bigwedge_{i=1}^{m}\left(\ell_{i,1}\vee\ell_{i,2}\vee\ell_{i,3}\vee x\right).$

זמן ריצה. עוברים על ההסגרים ומוסיפים ליטרל אחד לכל הסגר; סך הכול $O(|\langle\varphi\rangle|)$, ובוודאי פולינומי.

כיוון ראשון. נניח $\varphi\in\mathrm{3SAT}$, ותהא $V$ השמה המספקת אותה. נרחיב אותה ל-$\widehat V$ על ידי $\widehat V(x)=\text{False}$. בכל הסגר של $\widehat\varphi$ יש ליטרל אמת (כי $V$ סיפקה את ההסגר המקורי) וגם ליטרל שקר (המשתנה $x$ עצמו), ולכן ערכי הליטרלים בהסגר אינם כולם שווים. מכאן $\widehat\varphi\in\mathrm{4NAE}$.

כיוון שני. נניח $\widehat\varphi\in\mathrm{4NAE}$, ותהא $U$ השמה המספקת אותה באופן NAE. אם $U(x)=\text{True}$, נחליף את $U$ בהשמה ההפכית $\widehat U$ — לפי משפט 6 גם היא מספקת את $\widehat\varphi$ באופן NAE, ובה $\widehat U(x)=\text{False}$. לכן אפשר להניח בלי הגבלת הכלליות $U(x)=\text{False}$. יהי $i$ הסגר. אילו כל שלושת הליטרלים $\ell_{i,1},\ell_{i,2},\ell_{i,3}$ היו מקבלים False תחת $U$, אז כל ארבעת הליטרלים בהסגר היו שווים ל-False — בסתירה לספיקוּת NAE. לכן לפחות אחד מהם אמת, כלומר $U$ מסופקת את ההסגר המקורי. הדבר נכון לכל הסגר, ולכן $U$ מצומצמת למשתני $\varphi$ מספקת את $\varphi$, ומכאן $\varphi\in\mathrm{3SAT}$. $\blacksquare$