9משפט קוק–לוין

בקצרה

• השיעור מוכיח את משפט קוק–לוין: $\mathrm{SAT}$ היא NP-complete. זו הבעיה ה-NP-שלמה הראשונה, וממנה נגזרות כל האחרות ברדוקציות.
• מה שצריך להראות הוא: לכל שפה $A\in \mathrm{NP}$ קיימת רדוקציית זמן פולינומי $A\le_p \mathrm{SAT}$. שימו לב לסדר הכמתים — לא "יש רדוקציה אחת שטובה לכל השפות", אלא לכל שפה רדוקציה משלה.
• הקושי: על $A$ לא ידוע דבר מלבד היותה ב-NP. כל מה שיש ביד הוא מכונה מוודאת $M$, פולינומים $p,q$, והקלט $x$ עצמו. את העד $w$ אין ביד — ובדיוק את אי-הידיעה הזאת אנחנו הופכים לחופש של ההשמה.
• הרעיון: לקודד את טבלת החישוב (tableau) של $M$ על $(x,w)$ — כל שורה היא קונפיגורציה שלמה, שורה לכל צעד זמן — במשתנים בוליאניים $x_{i,j,s}$, ולבנות נוסחת CNF שנוסחה $\varphi=\varphi_{table}\wedge\varphi_{start}\wedge\varphi_{accept}\wedge\varphi_{move}$ שספיקה אם ורק אם קיים $w$ שעליו $M$ מקבלת.
• ליבת ההוכחה: קידוד נאיבי של "שורה $i+1$ נובעת משורה $i$" דורש מספר מעריכי של גרירות ($|L|^{2r(n)+1}$ מילויים אפשריים לשורה). המוצא הוא לוקליות החישוב במכונת טיורינג: בין שתי שורות עוקבות משתנים לכל היותר שלושה תאים סמוכים, ולכן די לבדוק שכל חלון 2×3 בטבלה חוקי — בדיקה מקומית שכופה נכונות גלובלית.
• חשבון הגודל: $O(r(|x|)^2)$ משתנים ו-$O(r(|x|)^2)$ פסוקיות עד לקבועים התלויים רק ב-$M$, כאשר $r(n)=p(n+q(n))$ — כלומר פולינומי ב-$|x|$, ולכן הרדוקציה רצה בזמן פולינומי.
• שני הרעיונות שכדאי לקחת מהשיעור, גם מעבר למבחן [01:14:55]: מידול בעיה כנוסחת CNF, והחלפת גרירה גלובלית בבדיקה מקומית בגודל קבוע.

רקע ותלויות

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

1. מודל המכונה (ראו שיעור 4). מכונת טיורינג דטרמיניסטית היא $M=(Q,q_{start},F,\Sigma,\Gamma,\delta)$ כאשר $Q$ קבוצת המצבים, $q_{start}\in Q$ מצב ההתחלה, $F\subseteq Q$ המצבים המקבלים (נסמן ב-$q_{accept}$ את המצב המקבל, וניתן להניח שהוא יחיד), $\Sigma$ אלפבית הקלט, $\Gamma\supseteq\Sigma\cup\{B\}$ אלפבית הסרט הכולל את הסימן הריק $B$, ו-$\delta:Q\times\Gamma\to Q\times\Gamma\times\{L,R\}$ פונקציית המעברים. נסמן ב-$\mathrm{time}_M(a)$ את מספר הצעדים של $M$ על הקלט $a$, וב-$\mathrm{space}_M(a)$ את מספר התאים בהם ביקרה.

הערה: גם הסיכום וגם ההרצה אינם רושמים את החמישייה/השישייה במפורש בשיעור הזה. רשמנו אותה כאן עם $q_{start}$ בפנים, כי $q_{start}$ מופיע בנוסחה $\varphi_{start}$ ואי אפשר בלעדיו.

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

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

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

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

$B$ היא NP-hard אם לכל $A\in \mathrm{NP}$ מתקיים $A\le_p B$. $B$ היא NP-complete אם בנוסף $B\in \mathrm{NP}$.

4. $\mathrm{SAT}$ ונוסחאות CNF (ראו שיעור 7). $\mathrm{SAT}$ היא שפת נוסחאות הפסוקים הספיקות; אנחנו נבנה כאן נוסחת CNF, כלומר קוניונקציה של פסוקיות (דיסיונקציות של ליטרלים). הראנו כבר ש-$\mathrm{SAT}\in \mathrm{NP}$: העד הוא ההשמה עצמה, אורכה לינארי בגודל הנוסחה, ובדיקת ההשמה היא לינארית.

5. בעיית שמונה המלכות (ראו שיעור 7). המרצה חוזר אליה שוב ושוב [00:09:27], [00:20:03] וקורא לה "משפט קוק–לוין בקטן": לקחנו לוח שחמט, הגדרנו משתנה בוליאני לכל משבצת ("יש מלכה / אין מלכה"), וכתבנו שלוש תת-נוסחאות — לשורות, לעמודות ולאלכסונים — וחיברנו ב-$\wedge$. כאן נעשה בדיוק את אותו הדבר, רק עם עוד אינדקסים ועם ארבע תת-נוסחאות במקום שלוש. שווה לרענן אותה לפני שקוראים הלאה.

נקודת מפתח מתודית מההרצה [00:05:19]–[00:06:52]. לפני שבונים משהו, כדאי לשאול שאלה תחבירית: מי המשתנים שיש לי ביד? הכלל ש"קיים מביא לי משתנים, ולכל מוחק אותם בסוף הסקופ" (כמו פתיחת בלוק בקוד) נותן: יש לי את $M$, את $p$, את $q$ — ובזמן ריצת הרדוקציה גם את $x$, כי הרדוקציה מקבלת את $x$ כקלט. אין לי את $w$, כי הוא נמצא בתוך "לכל $x$" שנסגר. כל הבנייה שלהלן מקפידה על הכלל הזה, ואפשר לבדוק אותה בכל שלב בשאלה "האם השתמשתי כרגע רק במה שיש לי ביד?".

הגדרות

הגדרה 1: קידוד קונפיגורציה כשורה אחת

ניסוח. תהי $M$ מכונת טיורינג בקונפיגורציה שבה תוכן הסרט הוא $\gamma_1\gamma_2\cdots\gamma_m$, המצב הוא $q$ והראש מצביע על התא $k$. נקודד את הקונפיגורציה כמחרוזת אחת מעל האלפבית $\Gamma\cup Q$: $\gamma_1\cdots\gamma_{k-1}\,q\,\gamma_k\,\gamma_{k+1}\cdots\gamma_m$ כלומר: סימן המצב נדחף לתוך המחרוזת מיד לפני התא שהראש קורא.

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

דוגמה (מהלוח, עמוד 1 בסיכום). סרט $B\,B\,0\,1\,0\,B\,B$, הראש על ה-$1$, המצב $q_1$. הקידוד: $B\ B\ 0\ q_1\ 1\ 0\ B\ B$ נניח $\delta(q_1,1)=(q_3,0,R)$: המכונה כותבת $0$ במקום ה-$1$ וזזה ימינה. הקונפיגורציה הבאה מקודדת כ- $B\ B\ 0\ 0\ q_3\ 0\ B\ B$ כלומר שני התאים ששינו את תוכנם הם התא של המצב והתא שמימינו — הם התחלפו: $(q_1,1)\rightsquigarrow(0,q_3)$.

דוגמה נגדית (מה זה לא). המחרוזת $B\,B\,q_1\,0\,q_3\,B$ אינה קידוד של קונפיגורציה: מופיעים בה שני סימני מצב, ולקונפיגורציה יש מצב אחד ומיקום ראש אחד. גם המחרוזת $B\,B\,0\,1\,B$ (בלי אף סימן מצב) אינה קידוד חוקי. שתי הפסילות האלה הן בדיוק מה ש-$\varphi_{table}$ ו-$\varphi_{start}$ יצטרכו לדאוג לו.

הגדרה 2: טבלת החישוב (tableau)

ניסוח. בהינתן $M$ וקלט $a$, טבלת החישוב היא מטריצה שבה השורה ה-$i$ היא הקידוד (לפי הגדרה 1) של הקונפיגורציה של $M$ על $a$ אחרי $i-1$ צעדים. שורה 1 היא הקונפיגורציה ההתחלתית.

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

המידות. נניח $A\in \mathrm{NP}$ עם $M,p,q$ כלעיל, ויהי $x$ קלט באורך $n=|x|$. הקלט של $M$ הוא $(x,w)$ שאורכו $n+q(n)$, ולכן מספר הצעדים חסום ב-$p(n+q(n))$. נסמן $r(n)=p\big(n+q(n)\big)$ ואז:

• מספר השורות בטבלה הוא $r(n)$ — שורה לכל צעד זמן [00:13:43].
• מספר העמודות הוא $2r(n)+1$. למה פעמיים? [00:15:18]–[00:15:49] הזמן חוסם את המקום, ולכן הראש לא מתרחק יותר מ-$r(n)$ תאים מנקודת ההתחלה — אבל אינני יודע מראש לאיזה כיוון הוא ילך, ולכן אני שומר $r(n)$ תאים שמאלה ו-$r(n)$ ימינה. ה-$+1$ הוא התא שבו נכתב סימן המצב [00:17:59].

מסקנה: הראש מתחיל בעמודה $r(n)+1$, מבצע לכל היותר $r(n)-1$ צעדים, ולכן סימן המצב תמיד נמצא בעמודה $k$ עם $2\le k\le 2r(n)$ — לעולם לא בעמודות הקצה. זו עובדה שנשתמש בה בהוכחת הלמה המרכזית.

הערה חשובה — הטבלה דמיונית. המרצה חוזר על כך חמש פעמים לפחות [00:16:25], [00:18:31], [00:32:31]: הרדוקציה לא בונה את הטבלה ולא ממלאת אותה, כי כדי למלא אותה היה צריך את $w$ ואת $w$ אין לנו. הטבלה היא אובייקט שאנחנו חושבים עליו כדי לכתוב את הנוסחה; הרדוקציה כותבת רק נוסחה.

הגדרה 3: האלפבית $L$ והמשתנים $x_{i,j,s}$

ניסוח. נסמן $L=\Gamma_M\cup\{0,1\}\cup Q_M$ — קבוצת כל הסימנים שיכולים להופיע בתא של הטבלה [00:21:07]. (הסימנים $0,1$ מופיעים במפורש כי הם התווים של העד $w$; אם $\{0,1\}\subseteq\Gamma_M$ האיחוד מיותר, ואינו מזיק.) שימו לב ש-$|L|$ תלוי רק ב-$M$ ולא ב-$x$.

יהי $x=a_1a_2\cdots a_n$. לכל $1\le i\le r(n)$ — אינדקס השורה, כלומר צעד הזמן — ולכל $1\le j\le 2r(n)+1$ — אינדקס העמודה, כלומר התא — ולכל $s\in L$, נגדיר משתנה בוליאני יחיד $x_{i,j,s}$.

אינטואיציה — וזו הנקודה שבה נופלים. תחבירית, $x_{i,j,s}$ הוא פשוט משתנה. אין לו "משמעות"; שלושת האינדקסים הם רק שם, בדיוק כמו שאפשר לכתוב סכום עם שלושה אינדקסים [00:23:17]. סמנטית, כשתגיע השמה $v$, נחשוב על $v(x_{i,j,s})=1$ כאילו היא אומרת: "בתא $(i,j)$ של הטבלה כתוב הסימן $s$" [00:24:19]. שאלת סטודנט בהרצה [00:23:47] — "מה זה $s$?" — קיבלה תשובה בשני שלבים, ושווה לזכור את שניהם: פורמלית אין מה להסביר, זה אינדקס רץ על $L$; אינטואיטיבית זה הסימן שנטען שכתוב בתא.

מה עוד לא נאמר. כרגע ההשמה יכולה לתת $1$ גם ל-$x_{i,j,s}$ וגם ל-$x_{i,j,t}$ עם $s\ne t$ — כלומר "בתא כתובים שני סימנים" [00:24:52]. שום דבר עדיין לא אוסר את זה. בדיוק בשביל זה קיימת $\varphi_{table}$.

דוגמה. בטבלה של הדוגמה מסעיף "דוגמאות ותרגילים" למטה, בתא $(1,4)$ כתוב $q_{start}$; כלומר בהשמה המתאימה $v(x_{1,4,q_{start}})=1$ ו-$v(x_{1,4,s})=0$ לכל $s\ne q_{start}$.

הגדרה 4: חלון $2\times3$ וחלון חוקי

ניסוח. חלון בטבלה הוא תת-מטריצה של שתי שורות סמוכות ושלוש עמודות סמוכות. מאנדקסים חלון לפי התא השמאלי-עליון שלו [01:05:18]: החלון $(i,j)$ מורכב מהתאים $\begin{matrix} (i,j) & (i,j+1) & (i,j+2)\\ (i+1,j) & (i+1,j+1) & (i+1,j+2)\end{matrix}$ ותכולתו היא שישייה $(a_1,a_2,a_3,a_4,a_5,a_6)\in L^6$ לפי הסדר $\begin{array}{|c|c|c|}\hline a_1 & a_2 & a_3\\\hline a_4 & a_5 & a_6\\\hline\end{array}$

שישייה נקראת חוקית אם קיימת ריצה כלשהי של $M$ שבתיאור הטבלאי שלה מופיע חלון כזה [00:57:01]. שקול ומעשי יותר: השישייה חוקית אם ורק אם היא נובעת מ-$\delta$ — כלומר קיימות קונפיגורציה $C$ ועוקבתה $C'=\delta(C)$ ומיקום עמודה שבו החלון של שתי השורות המקודדות הוא בדיוק השישייה — או שהיא העתקה של שורה שמכילה מצב סופי [01:03:44]. נסמן את קבוצת השישיות החוקיות $\mathrm{Legal}(M)\subseteq L^6$.

אינטואיציה. "חלון חוקי" הוא בדיקת שפיות מקומית: האם מה שרואים דרך חור המנעול הזה יכול היה לקרות במכונה $M$? התשובה תלויה רק ב-$\delta$, כלומר רק ב-$M$, ולא ב-$x$, ולא ב-$n$ [01:06:22]. לכן אפשר לחשב את $\mathrm{Legal}(M)$ פעם אחת, עוד לפני שראינו את הקלט, על ידי מעבר על כל $|L|^6$ השישיות.

כמה שישיות יש? $|L|^6$ — לא $\binom{|L|}{6}$. הסטודנט בהרצה ניחש "$L$ מעל $6$" ותוקן [00:58:38]: השישיות אינן חייבות להיות מורכבות מסימנים שונים, ולכן זהו $|L|\cdot|L|\cdots|L|$ שש פעמים. חשוב לא להתבלבל בבסיס ובמעריך.

כלל הריפוד (התוספת "העתקה של מצב סופי"). חסם הזמן $p$ הוא חסם מלמעלה; אף אחד לא הבטיח שהמכונה תרוץ בדיוק $r(n)$ צעדים [01:03:12]. אם המכונה עצרה במצב מקבל אחרי $t<r(n)$ צעדים, אין לנו שורות להמשיך איתן. הפתרון: מכריזים שהעתקה מדויקת של שורה שמכילה $q_{accept}$ היא מעבר חוקי, וממלאים את שאר הטבלה באותה שורה שוב ושוב. המרצה מלווה את זה בבדיחה על ההוכחה של איש מדעי המחשב ש"כל האי-זוגיים ראשוניים": 3 ראשוני, 5 ראשוני, 7 ראשוני, 7 ראשוני, 7 ראשוני… [01:04:15]. זה בדיוק מה שקורה כאן, וכאן זה חוקי.

הערה: בהרצה נאמר כלל הריפוד רק עבור $q_{accept}$. אם המכונה עוצרת במצב דוחה לפני הזמן, אין שישייה חוקית שממשיכה את השורה ולכן $\varphi_{move}$ לא תסופק — וזה בסדר גמור, כי במקרה כזה אנחנו ממילא רוצים ש-$\varphi$ תהיה לא-ספיקה. אפשר גם להרחיב את כלל הריפוד לכל מצב עוצר; אז $\varphi_{move}$ תסופק אבל $\varphi_{accept}$ לא, והמסקנה זהה.

דוגמה נגדית לחוקיות. אם $M$ אף פעם לא זזה שמאלה, אז החלון $\begin{array}{|c|c|c|}\hline 0 & q_1 & 1\\\hline q_3 & 0 & 1\\\hline\end{array}$ אינו חוקי: סימן המצב בשורה התחתונה נמצא שמאלה מהמקום שבו היה, כלומר הראש זז שמאלה [01:02:11].

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

משפט 1: משפט קוק–לוין

$\mathrm{SAT}$ היא NP-complete. כלומר: (א) $\mathrm{SAT}\in \mathrm{NP}$, ו-(ב) לכל $A\in \mathrm{NP}$ מתקיים $A\le_p \mathrm{SAT}$.

סדר הכמתים — אזהרה מפורשת מההרצה [00:01:08]. הטענה היא "לכל שפה ב-NP קיימת רדוקציה ל-$\mathrm{SAT}$", ולא "קיימת רדוקציה שמתאימה לכל השפות". לכל שפה תהיה רדוקציה משלה, שנבנית מהמוודא הספציפי שלה. זה מקור נפוץ מאוד לשגיאה בניסוח.

חלק (א): $\mathrm{SAT}\in \mathrm{NP}$

בהינתן נוסחה $\psi$ מעל $m$ משתנים, העד הוא ההשמה המספקת $v\in\{0,1\}^m$. אורכה $m\le|\psi|$, כלומר פולינומי (אפילו לינארי) בגודל הקלט; ובדיקה שההשמה מספקת נעשית במעבר אחד על הנוסחה, בזמן $O(|\psi|)$. לכן $\mathrm{SAT}\in \mathrm{NP}$. זה הוכח כבר בשיעור 7 והובא כאן כדי לסגור את הטענה; הסיכום עוצר בסוף עמוד 3 על "$\mathrm{SAT}$ היא NP-קשה" ואינו חוזר על החלק הזה.

חלק (ב): הבנייה

תהי $A\in \mathrm{NP}$. לפי ההגדרה יש בידינו $M$, $p$ ו-$q$ המקיימים את שני התנאים מסעיף "רקע ותלויות". נסמן $n=|x|$, $L=\Gamma_M\cup\{0,1\}\cup Q_M$, $r(n)=p(n+q(n))$, ונשתמש במשתנים $x_{i,j,s}$ של הגדרה 3. נבנה $\varphi=\varphi_{table}\wedge\varphi_{start}\wedge\varphi_{accept}\wedge\varphi_{move}$

הרעיון המנחה, שכדאי להחזיק בראש לכל אורך הבנייה [00:07:56]: "**$x\in A$" פירושו "קיים $w$", ו"$\varphi$ ספיקה" פירושו "קיימת השמה". אנחנו רוצים לגרור את הכמת הקיומי הזה מצד אחד לצד השני. כל ארבע התת-נוסחאות נועדו לוודא שהחופש היחיד שנשאר להשמה הוא בדיוק החופש בבחירת $w$.

$\varphi_{table}$ — בכל תא בדיוק סימן אחד

$\varphi_{table}=\bigwedge_{\substack{1\le i\le r(n)\\ 1\le j\le 2r(n)+1}}\left(\ \left(\bigvee_{s\in L}x_{i,j,s}\right)\ \wedge\ \left(\bigwedge_{\substack{s,t\in L\\ s\ne t}}\big(\overline{x_{i,j,s}}\vee \overline{x_{i,j,t}}\big)\right)\right)$

מה זה אוכף ולמה. הקוניונקציה החיצונית רצה על כל תא בטבלה. עבור תא נתון: הפסוקית הראשונה, $\bigvee_{s\in L}x_{i,j,s}$, אומרת שלפחות אחד מהסימנים מקבל אמת בתא הזה. היא לבדה לא מספיקה — היא לא אוסרת שניים [00:29:23]. לכן באה הקבוצה השנייה של פסוקיות: לכל זוג סימנים שונים $s\ne t$, הפסוקית $\overline{x_{i,j,s}}\vee\overline{x_{i,j,t}}$ אומרת שלא ייתכן ששניהם אמת — כלומר לכל היותר אחד. יחד: בדיוק אחד. זו בדיוק אותה תבנית "בחר בדיוק אחד מבין $k$" שראינו בבעיית המלכות [00:29:55].

למה בכלל צריך את זה? שאלת סטודנטית בהרצה [00:34:09]: למה אסור שיהיו שניים? כי אני רוצה טבלה שמתארת סרט של מכונה, ובכל תא בסרט של מכונת טיורינג רשום בדיוק תו אחד, ובכל קונפיגורציה יש בדיוק מצב אחד. בלי האילוץ הזה, "הטבלה" שההשמה מתארת אינה טבלה בכלל.

טענה 1.1. לכל השמה $v$ המספקת את $\varphi_{table}$, ולכל $i,j$, קיים $s\in L$ יחיד כך ש-$v(x_{i,j,s})=1$. ולהפך: לכל מילוי של הטבלה בסימנים מ-$L$ קיימת השמה המספקת את $\varphi_{table}$ ומתאימה לו.

הוכחה. כיוון ראשון: $\varphi_{table}$ היא קוניונקציה, ולכן השמה מספקת מספקת כל אחד מהאיברים; נקבע $i,j$. האיבר המתאים הוא עצמו קוניונקציה של שני חלקים. מהחלק הראשון, $\bigvee_{s}x_{i,j,s}=1$, נובע שקיים $s$ עם $v(x_{i,j,s})=1$. מהחלק השני, לכל $s\ne t$ מתקיים $\overline{x_{i,j,s}}\vee\overline{x_{i,j,t}}=1$, כלומר לא ייתכן ש-$v(x_{i,j,s})=v(x_{i,j,t})=1$. ביחד: קיים ואין שניים, כלומר קיים יחיד [00:33:04]–[00:33:35].

כיוון שני: בהינתן מילוי $T:\{1..r(n)\}\times\{1..2r(n)+1\}\to L$, נגדיר $v(x_{i,j,s})=1$ אם ורק אם $T(i,j)=s$. כל פסוקית מהצורה $\bigvee_s x_{i,j,s}$ מסופקת (על ידי $s=T(i,j)$), וכל פסוקית $\overline{x_{i,j,s}}\vee\overline{x_{i,j,t}}$ מסופקת כי לכל היותר אחד מבין $s,t$ שווה ל-$T(i,j)$. $\square$

הערה: בהרצה הכיוון השני נאמר במשפט אחד — "ודרך אגב גם הפוך" [00:34:09] — ומיד אחריו הובהר למה הוא חשוב: "להפך חשוב בגלל הכיוון השני של הרדוקציה" [00:35:46]. בלי הכיוון השני אי אפשר להסיק מ"$x\in A$" ש-$\varphi$ ספיקה, כי צריך להמיר טבלה אמיתית להשמה. הפירוט לעיל הוא מה שההערה הזאת מייצגת.

חשוב מה $\varphi_{table}$ לא אומרת [00:32:01]: היא מבטיחה טבלה — אבל טבלה של ג'יבריש. שום דבר בה לא קושר את הטבלה למכונה $M$ או לקלט $x$. את זה עושות שלוש הנוסחאות הבאות.

$\varphi_{start}$ — השורה הראשונה היא הקונפיגורציה ההתחלתית

יהי $x=a_1\cdots a_n$. אז $\varphi_{start}= \underbrace{x_{1,1,B}\wedge x_{1,2,B}\wedge\cdots\wedge x_{1,r(n),B}}_{\text{blanks}}\ \wedge\ x_{1,r(n)+1,q_{start}}\ \wedge\ \underbrace{x_{1,r(n)+2,a_1}\wedge\cdots\wedge x_{1,r(n)+n+1,a_n}}_{x}$ $\wedge\ \underbrace{\big(x_{1,r(n)+n+2,0}\vee x_{1,r(n)+n+2,1}\big)\wedge\cdots\wedge\big(x_{1,r(n)+n+1+q(n),0}\vee x_{1,r(n)+n+1+q(n),1}\big)}_{w}\ \wedge\ \underbrace{x_{1,r(n)+n+2+q(n),B}\wedge\cdots\wedge x_{1,2r(n)+1,B}}_{\text{blanks}}$

מה זה אוכף ולמה. בשורה 1 אני יודע כל תו — חוץ מ-$w$ [00:36:22]:

• העמודות $1..r(n)$: תאים ריקים. אלה ה-$r(n)$ תאים שמשמאל לראש, השמורים למקרה שהראש ילך שמאלה [00:37:56].
• עמודה $r(n)+1$: $q_{start}$ — כאן מתחיל הראש.
• עמודות $r(n)+2$ עד $r(n)+n+1$: הקלט $x$, תו אחר תו.
• עמודות $r(n)+n+2$ עד $r(n)+n+1+q(n)$: העד $w$. כאן איני יודע מה כתוב, אבל אני כן יודע שני דברים: את האורך ואת זה שכל תא הוא $0$ או $1$ [00:39:31]. לכן במקום ליטרל יחיד יש פה פסוקית $(\,\cdot\,\vee\,\cdot\,)$.
• שאר העמודות עד $2r(n)+1$: תאים ריקים.

זו הנקודה שבה נכנס החופש. כל שאר הקוניונקציות הן ליטרלים יחידים ולכן כופות ערך; רק בתאי $w$ יש בחירה. לכן להשמה המספקת את $\varphi_{start}$ יש בדיוק $q(n)$ ביטי חופש, והם מתאימים אחד לאחד לתווי $w$ [00:43:23]. המרצה מדגיש: "זה החופש שאני רוצה, כי אני רוצה לקשר בין 'קיים $w$' ל'קיימת השמה'".

מה נדרש כדי לבנות אותה? [00:42:18] את $x$ עצמו (בשביל $a_1..a_n$), את $n$, ואת הפולינומים $r$ ו-$q$. הכול ביד. שימו לב לניואנס שהמרצה מדגיש כבדיקת שפיות: ב-$\varphi_{table}$ השתמשנו רק ב-$n=|x|$ ולא ב-$x$ עצמו; כאן אנחנו באמת צריכים את $x$ עצמו.

שאלה מהכיתה [01:03:12] סביב אילוץ המצב: למה $\varphi_{start}$ לא צריכה לומר גם "אין מצב אחר בשורה הראשונה"? כי $\varphi_{table}$ כבר אומרת שבכל תא כתוב בדיוק סימן אחד, וכל עמודה בשורה 1 קיבלה כאן ערך מפורש. עקרון העבודה הוא: כל תת-נוסחה עומדת בפני עצמה ודורשת רק את מה שהיא צריכה; העיקר שהן לא סותרות זו את זו [00:45:01].

$\varphi_{accept}$ — איפשהו בטבלה יש מצב מקבל

$\varphi_{accept}=\bigvee_{\substack{1\le i\le r(n)\\ 1\le j\le 2r(n)+1}}x_{i,j,q_{accept}}$

מה זה אוכף ולמה. זו פסוקית אחת ארוכה: קיים תא בטבלה שכתוב בו $q_{accept}$. זה הכול [00:44:30].

שתי הערות דקות.

1. אין צורך לדרוש יחידות — "בתא שכתוב בו $q_{accept}$ לא כתוב שום דבר אחר" מובטח כבר על ידי $\varphi_{table}$ [00:45:31].
2. מותר שיופיעו כמה תאים עם $q_{accept}$, ואף שכיח שכן: בגלל כלל הריפוד, ברגע שהגענו למצב מקבל אנחנו מעתיקים את השורה עד סוף הטבלה, ולכן $q_{accept}$ יופיע בכל שורה משם והלאה. יחידות נדרשת ברמת התא, לא ברמת הטבלה.

$\varphi_{move}$ — הלב של ההוכחה

קודם: למה הקידוד הנאיבי נכשל. [00:48:06]–[00:50:11] אינטואיטיבית אני רוצה לומר: "אם השורה הראשונה מולאה כך — אז השורה השנייה מולאה כך". גרירות אינן מפחידות אותנו, כי $\alpha\to\beta$ שקול ל-$\overline{\alpha}\vee\beta$ ולכן ניתן להמרה ל-CNF. הבעיה היא הכמות: כמה מילויים אפשריים יש לשורה אחת? לכל תא יש $|L|$ אפשרויות ויש $2r(n)+1$ תאים, כלומר $|L|^{2r(n)+1}$ מילויים. (הסטודנט שניחש "גודל שורה עצרת" תוקן: זו חזקה, לא עצרת [00:49:08].) אני לא יודע מראש איזו שורה תתקבל — כי אני לא יודע מה $w$ — ולכן אצטרך גרירה לכל מילוי אפשרי: מספר מעריכי של תת-נוסחאות. הנוסחה שלי חייבת להיות פולינומית ב-$n$. אז זה נופל.

המוצא: לוקליות. [00:50:11]–[00:51:15] "היופי של ההוכחה, והיופי של המודל הזה" — החישוב במכונת טיורינג הוא מקומי מאוד. במעבר משורה לשורה הבאה, רוב מוחלט של התאים לא משתנים; המקומות היחידים שיכולים להשתנות הם התא של סימן המצב ותא אחד ימינה או שמאלה ממנו. לכן אין צורך לגרור שורה שלמה על שורה שלמה — מספיק לעבור על חלונות $2\times3$ ולוודא שכולם חוקיים. זו בדיוק הסיבה שבגללה צריך מודל חישוב "פרימיטיבי אבל מדויק" כמו מכונת טיורינג [00:46:33].

הנוסחה. $\varphi_{move}=\bigwedge_{\substack{1\le i\le r(n)-1\\ 1\le j\le 2r(n)-1}}\left[\ \bigvee_{(a_1,\dots,a_6)\in \mathrm{Legal}(M)}\Big(\big(x_{i,j,a_1}\wedge x_{i+1,j,a_4}\big)\wedge\big(x_{i,j+1,a_2}\wedge x_{i+1,j+1,a_5}\big)\wedge\big(x_{i,j+2,a_3}\wedge x_{i+1,j+2,a_6}\big)\Big)\right]$

התחומים. [01:05:18]–[01:05:51] — זו הייתה שאלת סטודנטית והתשובה שווה זכירה. החלון מאונדקס לפי התא השמאלי-עליון שלו. התא השמאלי-עליון יכול להגיע לכל היותר עד השורה שלפני האחרונה, כי לחלון יש שתי שורות — ומכאן $i\le r(n)-1$. הוא יכול להגיע לכל היותר עד שתיים לפני העמודה האחרונה, כי לחלון יש שלוש עמודות ומספר העמודות הוא $2r(n)+1$ — ומכאן $j\le (2r(n)+1)-2=2r(n)-1$.

הצורה: מ-DNF ל-CNF. כפי שנכתבה, כל תת-נוסחה של חלון היא דיסיונקציה של קוניונקציות, כלומר DNF ולא CNF. יש לזה תיקון סטנדרטי ופשוט שכדאי להכיר, והוא גם מקצר את הנוסחה: במקום למנות את השישיות החוקיות, אוסרים את הלא-חוקיות. בהינתן $\varphi_{table}$ (שמבטיחה סימן יחיד בכל תא), החלון $(i,j)$ חוקי אם ורק אף שישייה לא-חוקית אינה מופיעה בו, ולכן אפשר לכתוב במקום זאת $\varphi_{move}'=\bigwedge_{\substack{1\le i\le r(n)-1\\ 1\le j\le 2r(n)-1}}\ \ \bigwedge_{(a_1,\dots,a_6)\notin \mathrm{Legal}(M)}\Big(\overline{x_{i,j,a_1}}\vee\overline{x_{i,j+1,a_2}}\vee\overline{x_{i,j+2,a_3}}\vee\overline{x_{i+1,j,a_4}}\vee\overline{x_{i+1,j+1,a_5}}\vee\overline{x_{i+1,j+2,a_6}}\Big)$ זו כבר CNF ישירה: לכל חלון לכל היותר $|L|^6$ פסוקיות, כל אחת בת 6 ליטרלים.

הערה: בהרצה נאמר רק שהמרת גרירות ל-CNF "לא מפחידה" [00:48:37], והסיכום משאיר את $\varphi_{move}$ בצורת DNF-לכל-חלון. הפירוט כאן הוא מה שההערה הזאת מייצגת. שתי הצורות שקולות מעל השמות המספקות את $\varphi_{table}$, ושתיהן פולינומיות; הצורה השנייה נוחה יותר כי היא CNF כפי שנדרש להגדרת $\mathrm{SAT}$ ולרדוקציה ל-$3\mathrm{SAT}$ בהמשך.

טענה 1.2 (למת הלוקליות) — למה בדיקה מקומית מספיקה

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

ניסוח. תהי $T$ טבלה (מילוי של $L$ בכל תא), ונניח:

1. השורה הראשונה של $T$ היא קידוד חוקי של הקונפיגורציה ההתחלתית של $M$ על $(x,w)$ עבור $w$ כלשהו, כלומר סימן מצב יחיד בעמודה $r(n)+1$;
2. כל חלון $2\times3$ ב-$T$ חוקי.

אז לכל $i$: השורה $i$ היא קידוד חוקי של קונפיגורציה, והשורה $i+1$ היא הקידוד של הקונפיגורציה העוקבת לה (או העתקה שלה, אם היא מכילה מצב סופי).

הוכחה, באינדוקציה על $i$. בסיס: תנאי 1 נותן שהשורה הראשונה היא קידוד קונפיגורציה, עם סימן מצב יחיד בעמודה $k_1=r(n)+1$.

צעד: נניח שהשורה $i$ היא קידוד של קונפיגורציה $C$, שבה סימן המצב יושב בעמודה $k$. כפי שהראינו בהגדרה 2, $2\le k\le 2r(n)$ — הראש לעולם אינו על עמודת קצה. נראה שהשורה $i+1$ נקבעת במלואה, והיא הקידוד של $\delta(C)$.

(א) תאים רחוקים מהראש נשמרים. יהי $j$ עם $|j-k|\ge 2$. נתבונן בחלון $(i,j-1)$, שעמודותיו $j-1,j,j+1$. אף אחת מהן אינה $k$ (כי $j-1=k$ היה מחייב $j=k+1$, ו-$j+1=k$ היה מחייב $j=k-1$; שניהם נשללו). לכן שורתו העליונה של החלון אינה מכילה סימן מצב. כל שישייה חוקית שהשורה העליונה שלה נטולת מצב מקיימת $a_5=a_2$, כלומר התא האמצעי אינו משתנה: הרי בשישייה חוקית נלקחת מעבר אמיתי של $M$; המעבר משנה רק את התא שתחת הראש ואת סימן המצב, שנשאר במרחק $\le1$ מ-$k$, ולכן תא בעמודה $j$ עם $|j-k|\ge2$ אינו יכול לא לשנות את תוכנו ולא לקבל סימן מצב חדש (הראש בזמן $i+1$ נמצא בעמודה $k\pm1$, שמרחקה מ-$j$ הוא לפחות 1). מסקנה: $T(i+1,j)=T(i,j)$ — בדיוק כמו בקונפיגורציה העוקבת.

(ב) תאים ליד הראש נקבעים על ידי $\delta$. נתבונן בחלון $(i,k-1)$ — הוא קיים בזכות $2\le k\le 2r(n)$. שורתו העליונה היא $(T(i,k-1),\,q,\,T(i,k+1))$, כלומר סימן המצב יושב במרכז. כיוון ש-$M$ דטרמיניסטית, $\delta(q,T(i,k+1))$ קובע באופן יחיד מה תהיה שורת החלון התחתונה:

• אם $\delta(q,\gamma)=(q',\gamma',R)$: $(T(i,k-1),\,q,\,\gamma)\ \rightsquigarrow\ (T(i,k-1),\,\gamma',\,q')$;
• אם $\delta(q,\gamma)=(q',\gamma',L)$: $(c,\,q,\,\gamma)\ \rightsquigarrow\ (q',\,c,\,\gamma')$.

בשני המקרים כל שלושת התאים $k-1,k,k+1$ בשורה $i+1$ נקבעים במלואם, ובדיוק כמו בקונפיגורציה העוקבת. (המקרה של מצב סופי מטופל בכלל הריפוד: השורה מועתקת.)

(א) ו-(ב) יחד מכסים את כל העמודות, ולכן השורה $i+1$ שווה בדיוק לקידוד של $\delta(C)$ — ובפרט היא בעצמה קידוד חוקי של קונפיגורציה, מה שמאפשר את המשך האינדוקציה. $\square$

הערה: הטיעון הזה נאמר בהרצה כאינטואיציה — "רוב התאים לא השתנו, המקום היחיד שהשתנה הוא ליד הראש" [00:50:42] — ובאמצעות דוגמאות על הלוח. הפירוט הפורמלי, כולל ההבחנה שהראש לעולם אינו על עמודת קצה (ולכן החלון $(i,k-1)$ תמיד קיים), הוא מה שההערה מייצגת.

למה דווקא 6 תאים? [00:58:07], [01:01:21] — תיאורטית אפשר היה חלון גדול יותר; אנחנו רוצים כמה שפחות, כי מספר הפסוקיות לחלון הוא $|L|$ בחזקת גודל החלון. פחות מ-$2\times3$ לא יספיק: בצעד יחיד יכולים להשתנות עד שלושה תאים סמוכים (במעבר שמאלה: $k-1,k,k+1$), ולכן חלון $2\times2$ עלול לפספס שינוי. שש הוא בדיוק המינימום שמכסה את כל השינויים האפשריים.

חשבון הגודל — למה הרדוקציה פולינומית

זהו החלק שהופך את הבנייה לרדוקציה. נסמן $r=r(n)=p(n+q(n))$ — פולינום ב-$n$, כי הרכבה של פולינומים היא פולינום.

המפתח: $|L|$ תלוי רק ב-$M$ ולא ב-$x$ ולא ב-$n$. לכן $|L|^6$ הוא גורם קבוע מבחינת גודל הקלט — הגם שהמרצה מסתייג מהמילה "קבוע" ומעדיף "לא תלוי ב-$n$" [01:07:23]. סך הכול $|\varphi|=O\big(r(n)^2\big)=O\big(p(n+q(n))^2\big)$ פולינומי ב-$n=|x|$, בדיוק כפי שנרשם בסיכום: $O(r(|x|)^2)$.

וגם זמן הבנייה פולינומי, לא רק הגודל. [00:26:30] המכונה $M_{CL}$ המבצעת את הרדוקציה מקבלת $x$ ו:

1. מחשבת $n=|x|$ ואת $r(n)=p(n+q(n))$ — חישוב אריתמטי על פולינומים ידועים;
2. מחשבת פעם אחת את הטבלה של $\mathrm{Legal}(M)$ על ידי מעבר על כל $|L|^6$ השישיות ובדיקת כל אחת מול $\delta$ — עבודה שלא תלויה כלל ב-$x$ [01:06:52];
3. פולטת את הפסוקיות של $\varphi_{table},\varphi_{start},\varphi_{accept},\varphi_{move}'$ בלולאות על $i,j$;
4. מחזירה $\varphi=\varphi_{table}\wedge\varphi_{start}\wedge\varphi_{accept}\wedge\varphi_{move}$.

כל פסוקית נכתבת בזמן קבוע, ומספר הפסוקיות פולינומי, ולכן $M_{CL}$ רצה בזמן פולינומי ב-$|x|$.

חזרה על מה שהמכונה כן ולא עושה [00:46:02]: $M_{CL}$ לא מחפשת השמה, לא מנחשת את $w$, לא מריצה את $M$. היא רק כותבת נוסחה. כל הסמנטיקה — הטבלה, ההשמה, ה"מלכה נמצאת/לא נמצאת" — היא בראש שלנו בזמן שאנחנו מוכיחים נכונות.

כיוון 1: $x\in A\ \Longrightarrow\ \varphi$ ספיקה

נניח $x\in A$. לפי הגדרת NP קיים $w\in\{0,1\}^{q(|x|)}$ כך ש-$M$ מקבלת את $(x,w)$, ומספר הצעדים חסום ב-$r(n)$.

נבנה טבלה $T$: השורה ה-$i$ היא הקידוד של הקונפיגורציה של $M$ על $(x,w)$ אחרי $i-1$ צעדים, ואם הריצה עצרה במצב מקבל אחרי $t<r(n)$ צעדים — כל השורות שמעבר לכך הן העתק של השורה שבה הופיע $q_{accept}$ (כלל הריפוד).

לפי טענה 1.1 (הכיוון השני) יש השמה $v$ המתאימה למילוי הזה: $v(x_{i,j,s})=1\iff T(i,j)=s$. נבדוק שהיא מספקת את כל ארבעת החלקים:

• $\varphi_{table}$: מיידי מהבנייה של $v$ — בכל תא בדיוק סימן אחד.
• $\varphi_{start}$: השורה הראשונה של $T$ היא הקונפיגורציה ההתחלתית: $r(n)$ תאים ריקים, $q_{start}$, אחריו $x$ תו-תו, אחריו $w$ תו-תו, אחריו תאים ריקים. הליטרלים היחידים מסופקים; ובכל אחת מהפסוקיות $\big(x_{1,j,0}\vee x_{1,j,1}\big)$ עבור $r(n)+n+2\le j\le r(n)+n+1+q(n)$, בדיוק אחד משני הליטרלים מקבל אמת — זה שמתאים ל-$w_{j-(r(n)+n+1)}$ [01:10:46]–[01:11:48].
• $\varphi_{accept}$: הריצה מקבלת, ולכן קיימת שורה שבה מופיע $q_{accept}$; התא הזה נותן ליטרל אמיתי בדיסיונקציה.
• $\varphi_{move}$: כל חלון בטבלה נלקח משתי שורות עוקבות של ריצה אמיתית של $M$ (או מזוג שורות זהות אחרי הקבלה), ולכן השישייה שבו חוקית לפי ההגדרה. לכן בכל חלון קיים איבר אחד בדיסיונקציה שמסופק.

לכן $v\models\varphi$, כלומר $\varphi\in \mathrm{SAT}$. $\square$

כיוון 2: $\varphi$ ספיקה $\Longrightarrow x\in A$

נניח שקיימת השמה מספקת $v$ עבור $\varphi$. נשחזר ממנה את $w$ ואת הריצה.

שלב 1 — הטבלה מוגדרת היטב. $v$ מספקת את $\varphi_{table}$, ולכן לפי טענה 1.1 לכל $(i,j)$ יש סימן יחיד $s$ עם $v(x_{i,j,s})=1$. נגדיר $T(i,j)=s$. קיבלנו טבלה.

שלב 2 — קריאת $w$. $v$ מספקת את $\varphi_{start}$, ולכן השורה הראשונה של $T$ היא: תאים ריקים, $q_{start}$, הקלט $x$, אחר כך $q(n)$ תאים שכל אחד מהם $0$ או $1$, ואז תאים ריקים. נגדיר $w_\ell=T\big(1,\ r(n)+n+1+\ell\big),\qquad \ell=1,\dots,q(n)$ זהו $w\in\{0,1\}^{q(|x|)}$, מוגדר היטב [01:17:02]–[01:18:09]. זה בדיוק מה שמסתתר מאחורי המשפט "נתבונן ב-$w$ לפי ערכי האמת למשתנים המתאימים" בעמוד 3 בסיכום.

שלב 3 — הטבלה מתארת את הריצה על $(x,w)$. $v$ מספקת את $\varphi_{move}$, ולכן כל חלון $2\times3$ ב-$T$ חוקי. יחד עם העובדה ששורה 1 היא הקונפיגורציה ההתחלתית על $(x,w)$, למת הלוקליות (טענה 1.2) נותנת באינדוקציה: לכל $i$, השורה $i+1$ היא הקונפיגורציה העוקבת לשורה $i$. כלומר $T$ היא בדיוק טבלת החישוב של $M$ על $(x,w)$.

זהו טיעון הדומינו של ההרצה [01:16:30]: ברגע שקבעתי את $w$, הדטרמיניזם של $M$ קובע את כל שאר הטבלה. "זה כמו אבן ראשונה של דומינו שמפילה את כל השאר." שימו לב שכאן נכנס לשימוש הדטרמיניזם — זו הסיבה שנוח לעבוד עם ההגדרה דרך מוודא דטרמיניסטי.

שלב 4 — הריצה מקבלת. $v$ מספקת את $\varphi_{accept}$, ולכן קיים תא ב-$T$ שבו כתוב $q_{accept}$. לפי שלב 3, $T$ מתארת את הריצה האמיתית של $M$ על $(x,w)$, ולכן הריצה הזאת מגיעה למצב $q_{accept}$ — כלומר $M$ מקבלת את $(x,w)$.

לכן קיים $w\in\{0,1\}^{q(|x|)}$ שעליו $M$ מקבלת את $(x,w)$, ומהגדרת NP נובע $x\in A$. $\square$

סיכום ההוכחה

$M_{CL}$ רצה בזמן פולינומי ומקיימת $x\in A\iff \varphi=M_{CL}(x)\in \mathrm{SAT}$, כלומר $A\le_p \mathrm{SAT}$. זה נכון לכל $A\in \mathrm{NP}$, ולכן $\mathrm{SAT}$ היא NP-hard; יחד עם חלק (א), $\mathrm{SAT}$ היא NP-complete. $\blacksquare$

הערה על off-by-one: מספר השורות שנקבע בסיכום הוא $r(n)$, אבל $r(n)$ שורות מתארות רק $r(n)-1$ צעדים, בעוד חסם הזמן מתיר $r(n)$ צעדים. התיקון הקל: לקחת $r(n)+1$ שורות (או להבחין ש-$p$ תמיד ניתן להגדלה בקבוע). שום דבר בהוכחה לא משתנה — כל התחומים והחסמים נשארים באותו סדר גודל.

משפט 2 (מסקנה): $\mathrm{CNF}\text{-}\mathrm{SAT}$ היא NP-complete, ובעקבותיה $3\mathrm{SAT}$

הנוסחה שבנינו (בצורת $\varphi_{move}'$) היא כבר CNF, ולכן ההוכחה מראה יותר: $\mathrm{CNF}\text{-}\mathrm{SAT}$ היא NP-hard. מכאן, בעזרת הרדוקציה $\mathrm{SAT}\le_p 3\mathrm{SAT}$ שראינו בשיעור 7 (פיצול פסוקיות ארוכות באמצעות משתנים חדשים), מקבלים ש-$3\mathrm{SAT}$ היא NP-complete.

זו נקודת המוצא לכל התחום: המרצה מציין [01:20:20] שאחרי המאמר של קוק ולוין בא ריצ'רד קארפ עם 21 בעיות אלגוריתמיות שהראה שכולן NP-שלמות — למשל $\mathrm{SAT}\le_p 3\mathrm{SAT}\le_p \mathrm{IS}\le_p \mathrm{CLIQUE}$ — והיום ידועות אלפים.

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

דוגמה 1: הקידוד של צעד יחיד (מהלוח, עמוד 1 בסיכום)

מכונה בקונפיגורציה: סרט $B\,B\,0\,1\,0\,B\,B$, ראש על ה-$1$, מצב $q_1$, ו-$\delta(q_1,1)=(q_3,0,R)$.

שאלת סטודנט בהרצה [00:12:07]: "אפשר להסביר את המעבר הזה?" התשובה: בשרטוט הרגיל הראש עמד על ה-$1$, כתב $0$ וזז ימינה. בקידוד, המצב נרשם תמיד תא אחד לפני מה שהראש קורא — ולכן $q_1$ שישב לפני ה-$1$ מתחלף: התא שלו מקבל את הסימן שנכתב ($0$), והתא שמימינו מקבל את $q_3$, כי עכשיו הראש קורא את התא שאחריו.

דוגמה 2: הרדוקציה מקצה לקצה על אינסטנס קונקרטי

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

השפה. $A=\{x\in\{0,1\}^*:\ x$ contains at least one $1\}$. זו כמובן שפה ב-P, אבל היא מוגדרת כאן דרך מוודא כדי שהבנייה תהיה מוחשית.

המוודא. $q(n)=n$; העד $w\in\{0,1\}^n$ אמור להצביע על מיקום של $1$ בקלט. $M$ מקבלת קלט $(x,w)$ הכתוב על הסרט כ-$x$ ואחריו $w$. עבור $n=1$ מספיק: $\Sigma=\{0,1\},\quad \Gamma=\{0,1,B\},\quad Q=\{q_{start},q_1,q_{accept},q_{reject}\}$ $\delta(q_{start},1)=(q_1,1,R),\quad \delta(q_{start},0)=(q_{reject},0,R),\quad \delta(q_1,1)=(q_{accept},1,R),\quad \delta(q_1,0)=(q_{reject},0,R)$ כלומר: קרא את $x_1$; אם הוא $0$ — דחה; אם הוא $1$ — עבור ל-$q_1$ ובדוק ש-$w_1=1$ (כלומר שהעד באמת מצביע על המיקום הזה).

הפרמטרים. $n=|x|=1$, $q(1)=1$, אורך הקלט של $M$ הוא $n+q(n)=2$. ניקח $p(m)=m+1$, ואז $r(1)=p(1+1)=3$ מספר שורות $=3$, מספר עמודות $=2\cdot3+1=7$, $L=\{0,1,B,q_{start},q_1,q_{accept},q_{reject}\}$ כך ש-$|L|=7$.