10Vertex Cover, Max-Cut and Graph Colouring

בקצרה

• מרחיבים את "אוצר" הבעיות ה-NP-קשות: בשיעור שעבר היו לנו $\mathrm{SAT}$, $\mathrm{3SAT}$, $\mathrm{IS}$ ו-$\mathrm{CLIQUE}$; כאן מצטרפות $\mathrm{VC}$, $\mathrm{MAXCUT}$, $\mathrm{3COL}$ ו-$\mathrm{kCOL}$.
• הבחנה מרכזית: $U \subseteq V$ היא כיסוי בקודקודים של $G$ אם ורק אם $V \setminus U$ היא קבוצה בלתי תלויה. מההבחנה הזו נובעת רדוקציה כמעט־זהותית $\mathrm{IS} \le_p \mathrm{VC}$ שמשנה רק את המספר: $\langle G,k\rangle \mapsto \langle G,|V|-k\rangle$.
• מגדירים סיפוק במובן NAE (Not All Equal) ואת הבעיה $k\mathrm{NAE}$, ומקבלים (דרך רדוקציות שניתנו כתרגיל בית) ש-$\mathrm{3NAE}$ היא NP-קשה. משם ממשיכים.
• $\mathrm{3NAE} \le_p \mathrm{MAXCUT}$: קודקוד לכל ליטרל, קשת "כחולה" בין ליטרל לשלילתו, משולש "אדום" לכל פסוקית, ויעד $n+2m$. הקסם הוא שמשולש תורם לחתך בדיוק $2$ או בדיוק $0$ קשתות, ולכן חסם עליון על הקשתות האדומות כופה שכל הקשתות הכחולות בחתך.
• $\mathrm{3NAE} \le_p \mathrm{3COL}$: קודקוד לכל ליטרל, קודקוד מיוחד $N$ המחובר לכולם, ומשולש לכל פסוקית שקודקודיו מחוברים לליטרלים המתאימים. הצבע של $N$ "שורף" צבע אחד ומשאיר שני צבעים שמתפקדים כאמת/שקר.
• $\mathrm{3COL} \le_p \mathrm{4COL}$ אינה מוכחת כאן אלא בשיעור 11 (משפט 2 שם, לפי עמודים 2–3 בסיכום ההוא); בקובץ הזה נשארת הפניה בלבד. מהמפגש ההוא נשמרה כאן רק הטעות העקרונית שהמרצה הקדיש לה זמן רב: רדוקציה אינה רואה את הצביעה.
• לצד הקשיות: $\mathrm{2COL} \in \mathrm{P}$ (שקול לדו-צדדיות), וכן — אם $k$ הוא חלק מה-DNA של הבעיה ולא חלק מהקלט, בעיות מסוימות קורסות ל-$\mathrm{P}$ (למשל $\mathrm{IS}$ עם $k$ קבוע).
• כל רדוקציה כאן מוכחת בשני הכיוונים ובניתוח זמן ריצה מפורש. זהו הפורמט המדויק שנדרש במבחן.

רקע ותלויות

מה חייבים לדעת לפני השיעור.

משיעור 6 נדרשת ההגדרה של רדוקציית זמן פולינומי. נזכיר אותה במלואה, כי כל השיעור נשען עליה: לשפות $A,B \subseteq \Sigma^*$ נאמר ש-$A \le_p B$ אם קיימת פונקציה $f:\Sigma^* \to \Sigma^*$ הניתנת לחישוב בזמן פולינומי (כלומר קיימת מכונת טיורינג $M=(Q,q_{start},F,\Sigma,\Gamma,\delta)$ המחשבת אותה, כך ש-$\mathrm{time}_M(x) \le p(|x|)$ עבור פולינום $p$), המקיימת $\forall x \in \Sigma^*:\quad x \in A \iff f(x) \in B .$

הערה על כיוון: $A \le_p B$ נקרא "$A$ ניתנת לרדוקציה ל-$B$", ומשמעותו ש-$B$ היא הבעיה הקשה לפחות כמו $A$. כלומר החץ מצביע מהבעיה הידועה-כקשה אל הבעיה שאנחנו רוצים להוכיח שהיא קשה. בהקלטות אוטומטיות הכיוון הזה מתהפך כל הזמן; בכל רדוקציה בקובץ הזה נאמר את הכיוון גם במילים.

משיעור 7 נדרשים: ההגדרה $\mathrm{IS} = \{\langle G,k\rangle \mid G$ גרף, $k\in\mathbb{N}$, וקיימת ב-$G$ קבוצה בלתי תלויה בגודל לפחות $k\}$, כאשר $U \subseteq V$ נקראת בלתי תלויה אם לכל $x,y \in U$ מתקיים $xy \notin E$; וכן הרדוקציה $\mathrm{IS} \le_p \mathrm{CLIQUE}$ (מעבר לגרף המשלים).

משיעור 8–9 נדרש משפט קוק–לוין: $\mathrm{SAT}$ היא NP-קשה, ובעקבותיו שרשרת התזכורת שנפתח בה השיעור (עמוד 1 בסיכום):

$\mathrm{SAT} \text{ is NP-hard} \;\Longrightarrow\; \mathrm{SAT} \le_p \mathrm{3SAT} \;\Longrightarrow\; \mathrm{3SAT} \le_p \mathrm{IS} \;\Longrightarrow\; \mathrm{IS} \le_p \mathrm{CLIQUE}.$

הראשונה נראתה בכיתה, השנייה ניתנה כתרגיל בית (המרצה נתן את הרדוקציה ודרש רק את הוכחת הנכונות), השלישית הוכחה בשיעור. בסיכום נרשמה השורה השלישית כ-$\mathrm{SAT}\le_p \mathrm{IS}$; שתי הגרסאות נכונות, שכן $\le_p$ טרנזיטיבית.

התזכורת הטכנית שנשתמש בה שוב ושוב: אם $A$ היא NP-קשה ו-$A \le_p B$ אז $B$ היא NP-קשה. ההוכחה היא בדיוק טרנזיטיביות: לכל $C \in \mathrm{NP}$ מתקיים $C \le_p A \le_p B$, והרכבה של שתי פונקציות פולינומיות היא פולינומית (הפלט של הראשונה חסום פולינומית באורך הקלט, ולכן זמן הריצה של השנייה עליו הוא פולינום בפולינום).

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

הגדרות

הגדרה 1: כיסוי בקודקודים (Vertex Cover)

יהי $G=(V,E)$ גרף לא מכוון. קבוצה $U \subseteq V$ תיקרא כיסוי בקודקודים (vertex cover) אם

$\forall e \in E:\quad e \cap U \neq \emptyset .$

ההגדרה מנצלת את העובדה שקשת בגרף לא מכוון היא קבוצה של שני קודקודים — זוג לא סדור, כלומר $e = \{x,y\}$ — ולכן החיתוך $e \cap U$ הוא ביטוי חוקי. במילים: כל קשת מכילה לפחות קודקוד אחד מהכיסוי.

השפה המתאימה:

$\mathrm{VC} = \left\{ \langle G,k \rangle \;\middle|\; \begin{array}{l} G=(V,E) \text{ graph},\ k \in \mathbb{N},\\ \exists U \subseteq V \text{ a vertex cover of } G,\ |U| \le k \end{array} \right\}$

צורת כתיבה נוספת (עמוד 1 בסיכום, ואסייד ארוך ב-[00:04:50]–[00:11:13]). אפשר להגדיר את אותה בעיה בדיוק כך:

קלט: גרף $G=(V,E)$ ומספר טבעי $k \in \mathbb{N}$. שאלה: האם קיים כיסוי בקודקודים $U \subseteq V$ בגודל לכל היותר $k$?

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

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

דוגמה (עמוד 1 בסיכום). יהי $G$ הגרף על $V=\{a,b,u_1,u_2,c\}$ עם $E=\{\,au_1,\; bu_2,\; u_1u_2,\; u_1c,\; u_2c\,\}.$ אז $U=\{u_1,u_2\}$ היא כיסוי בקודקודים: $au_1 \ni u_1$, $bu_2 \ni u_2$, $u_1u_2 \ni u_1$, $u_1c \ni u_1$, $u_2c \ni u_2$. כלומר $\langle G,2\rangle \in \mathrm{VC}$.

אי-דוגמה. $U'=\{u_1\}$ אינה כיסוי: הקשת $bu_2$ מקיימת $bu_2 \cap U' = \emptyset$. ואכן $\langle G,1\rangle \notin \mathrm{VC}$, כי $au_1$ ו-$bu_2$ הן קשתות זרות ולכן דרושים לפחות שני קודקודים.

הגדרה 2: סיפוק במובן NAE, והבעיה $k\mathrm{NAE}$

תהי $\varphi$ נוסחה בצורת CNF ותהי $V$ הצבה לקבוצת המשתנים של $\varphi$ (הצבה = פונקציה מהמשתנים ל-$\{0,1\}$).

תזכורת (אינה חלק מההגדרה החדשה). $V$ מספקת את $\varphi$ אם ורק אם לכל פסוקית $C$ ב-$\varphi$ קיים ליטרל ב-$C$ ש-$V$ נותנת לו את הערך $1$.

ההגדרה החדשה. נאמר ש-$V$ מספקת את $\varphi$ במובן Not All Equal, ונסמן זאת בקיצור NAE, אם

לכל פסוקית $C$ ב-$\varphi$ קיים ליטרל ב-$C$ ש-$V$ נותנת לו $1$ וגם קיים ליטרל ב-$C$ ש-$V$ נותנת לו $0$.

הבעיה:

$k\mathrm{NAE}$ — קלט: נוסחה $\varphi$ מצורת $k\mathrm{CNF}$ (כלומר CNF שבכל פסוקית שלה יש $k$ ליטרלים). שאלה: האם קיימת הצבה $V$ למשתני $\varphi$ המספקת את $\varphi$ במובן NAE?

אינטואיציה. סיפוק רגיל אומר "בכל פסוקית יש לפחות אמת אחת". סיפוק במובן NAE אומר "בכל פסוקית יש גם אמת וגם שקר" — כלומר הפסוקית אינה מונוכרומטית מבחינת ערכי האמת. שימו לב היטב ([00:35:48], והמרצה חזר על זה שלוש פעמים): התכונה הזו היא תכונה של הזוג (נוסחה, הצבה), לא של הנוסחה לבדה. כשאומרים "$\varphi$ מסופקת במובן NAE" מתכוונים "קיימת הצבה שמספקת אותה במובן NAE".

אי-דוגמה מבנית ([00:36:21], שאלת סטודנט). אם ב-$\varphi$ יש פסוקית עם ליטרל יחיד, אז אף הצבה אינה מספקת את $\varphi$ במובן NAE, כי לא ייתכן שאותו ליטרל יקבל גם $1$ וגם $0$. זה לא סותר את ההגדרה — פשוט הנוסחה אינה ב-$\mathrm{NAE}$.

דוגמה (עמוד 3 בסיכום). תהי $\varphi = (x_1 \vee x_2 \vee x_3) \wedge (\overline{x_1} \vee x_2).$

• ההצבה $V$ הנותנת לכל משתנה את הערך $1$ מספקת את $\varphi$ אך אינה מספקת אותה במובן NAE: בפסוקית הראשונה כל שלושת הליטרלים מקבלים $1$.
• ההצבה $V(x_1)=0,\; V(x_2)=V(x_3)=1$ מספקת את $\varphi$ אך שוב לא במובן NAE: הפסוקית הראשונה מקבלת $(0,1,1)$ — מצוין — אבל השנייה מקבלת $(\overline{x_1}=1,\ x_2=1)$, כלומר שני ליטרלים בערך $1$.
• ההצבה $V(x_1)=0,\; V(x_2)=0,\; V(x_3)=1$ כן מספקת את $\varphi$ במובן NAE: הפסוקית הראשונה מקבלת $(0,0,1)$, השנייה מקבלת $(1,0)$. בשתיהן יש גם $1$ וגם $0$.

הגדרה 3: חתך מושרה ובעיית $\mathrm{MAXCUT}$

יהי $G=(V,E)$ מולטיגרף — גרף לא מכוון שבו מותרות קשתות מקבילות (יותר מקשת אחת בין אותו זוג קודקודים), ובאופן עקרוני גם לולאות. (גרף פשוט הוא גרף שבו בין כל שני קודקודים יש לכל היותר קשת אחת; כל גרף פשוט הוא בפרט מולטיגרף.)

תהי $U \subseteq V$. החתך המושרה ב-$G$ על ידי $U$ הוא קבוצת הקשתות

$\mathrm{cut}_G(U) = \{\, e \in E \;\mid\; |e \cap U| = 1 \,\},$

כלומר כל הקשתות שיש להן בדיוק קצה אחד ב-$U$. מקובל לומר ש-$U$ ו-$V\setminus U$ הם שני צדדי החתך, ושהקשתות בחתך חוצות אותו.

הבעיה:

$\mathrm{MAXCUT}$ — קלט: מולטיגרף $G=(V,E)$ ומספר $k \in \mathbb{N}$. שאלה: האם קיימת $U \subseteq V$ כך שהחתך המושרה על ידיה מכיל לפחות $k$ קשתות?

למה דווקא "לפחות" ([00:51:48], [00:55:09]). בכיסוי בקודקודים ובקבוצה בלתי תלויה יכולנו להחליף "לכל היותר"/"לפחות" ב-"בדיוק", כי מה שסופרים הוא בדיוק מה שבוחרים — קודקודים. כאן בוחרים קודקודים אבל סופרים קשתות, ואין שליטה עדינה: הזזה של קודקוד יחיד מדרגה גבוהה יכולה לשנות את גודל החתך דרמטית. ייתכן אפילו גרף שבו כל חתך הוא בגודל זוגי, ואז לא נוכל להגיע ל-$k$ אי-זוגי בדיוק גם אם קיים חתך גדול יותר. לכן ה-"לפחות" כאן קריטי ואי אפשר להחליפו.

דוגמה (עמוד 4 בסיכום, [00:47:35]–[00:49:39]). יהי $G$ על $V=\{a,b,c,d,e,f\}$ עם $E = \{\,ab,\ af,\ ac,\ bc,\ bd,\ cd,\ ce,\ de,\ ef\,\},$ ותהי $U=\{b,c,f\}$. אז

$\mathrm{cut}_G(U) = \{\,ab,\ af,\ ac,\ bd,\ cd,\ ce,\ ef\,\},\qquad |\mathrm{cut}_G(U)| = 7 .$

שתי הקשתות שאינן בחתך ממחישות את שני אופני הכישלון: $bc$ אינה בחתך כי שני קצותיה ב-$U$, ו-$de$ אינה בחתך כי אף אחד מקצותיה אינו ב-$U$.

הגדרה 4: צביעה חוקית ובעיות $\mathrm{kCOL}$

יהי $G=(V,E)$ גרף ויהי $k \in \mathbb{N}$. צביעה של $G$ ב-$k$ צבעים היא פונקציה $f : V \longrightarrow \{1,2,\dots,k\} = [k].$ הצביעה תיקרא חוקית אם לכל קשת $uv \in E$ מתקיים $f(u) \neq f(v)$. במילים אחרות: אין בגרף קשת מונוכרומטית (קשת ששני קצותיה צבועים באותו צבע).

הבעיה:

$\mathrm{kCOL}$ — קלט: גרף $G=(V,E)$. שאלה: האם קיימת צביעה חוקית של $G$ ב-$k$ צבעים?

נקודה עדינה מאוד ([01:38:26], שאלת סטודנטית). שימו לב ש-$k$ אינו חלק מהקלט — הוא חלק מה-DNA של הבעיה. יש בעיה בשם $\mathrm{2COL}$, בעיה אחרת בשם $\mathrm{3COL}$, בעיה שלישית בשם $\mathrm{4COL}$ וכן הלאה; לכל $k$ קבוע זו בעיה נפרדת. זה שונה מהותית מ-$\mathrm{IS}$, $\mathrm{CLIQUE}$ ו-$\mathrm{VC}$, שבהן $k$ הוא חלק מהקלט.

מה ההבדל עושה ([01:40:00]–[01:42:12]). נגדיר $\mathrm{IS}_k$ = הבעיה שבה הקלט הוא גרף בלבד והשאלה היא האם יש בו קבוצה בלתי תלויה בגודל $k$, כאשר $k$ קבוע. אז $\mathrm{IS}_k \in \mathrm{P}$: מספר תת-הקבוצות בגודל $k$ הוא $\binom{|V|}{k} \le |V|^k$, ולכל אחת מהן בדיקת אי-תלות עולה זמן פולינומי; מכיוון ש-$k$ קבוע, $|V|^k$ הוא פולינום בגודל הקלט. אותה בעיה עצמה, כאשר $k$ הוא חלק מהקלט, היא NP-שלמה. ההבדל אינו קוסמטי: $|V|^k$ עם $k$ מהקלט הוא אקספוננציאלי בגודל הקלט.

דוגמה. משולש $K_3$ אינו $2$-צביע (שלושה קודקודים המחוברים הדדית), אך הוא $3$-צביע. $K_4$ אינו $3$-צביע אך הוא $4$-צביע.

אי-דוגמה לתפיסה שגויה ([00:15:50] בהקלטה 17). צביעה ב-$k$ צבעים אינה חייבת להיות על: אין בהגדרה שום דרישה להשתמש בכל $k$ הצבעים. לכן גרף $3$-צביע הוא בפרט $4$-צביע — פשוט לא נשתמש בצבע הרביעי.

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

משפט 1 (ההבחנה המרכזית): $U$ כיסוי בקודקודים $\iff$ $V \setminus U$ בלתי תלויה

טענה. יהי $G=(V,E)$ גרף ותהי $U \subseteq V$. אז $U$ היא כיסוי בקודקודים של $G$ אם ורק אם $V \setminus U$ היא קבוצה בלתי תלויה ב-$G$.

הוכחה.

כיוון $\Longleftarrow$: נניח ש-$U$ היא כיסוי בקודקודים; נראה ש-$V\setminus U$ בלתי תלויה.

צריך להראות: לכל $x,y \in V\setminus U$ מתקיים $xy \notin E$. אז יהיו $x,y \in V \setminus U$.

נניח בשלילה ש-$xy \in E$. מכיוון ש-$U$ כיסוי בקודקודים, לקשת $xy$ יש קצה ב-$U$, כלומר $x \in U$ או $y \in U$. אבל שנינו הנחנו $x,y \in V\setminus U$, כלומר $x \notin U$ וגם $y \notin U$ — סתירה. לכן $xy \notin E$, ומכיוון ש-$x,y$ היו שרירותיים, $V \setminus U$ בלתי תלויה. $\square$ (כיוון ראשון)

כיוון $\Longrightarrow$: נניח ש-$V\setminus U$ בלתי תלויה; נראה ש-$U$ כיסוי בקודקודים.

צריך להראות: לכל קשת יש קצה ב-$U$. תהי $e = xy \in E$ קשת. מכיוון ש-$V\setminus U$ בלתי תלויה, לא ייתכן ש-$x,y$ שניהם ב-$V\setminus U$ (אחרת הייתה ביניהם קשת בסתירה לאי-תלות). לכן $x \notin V\setminus U$ או $y \notin V\setminus U$, כלומר $x \in U$ או $y \in U$, כלומר $e \cap U \neq \emptyset$. מכיוון ש-$e$ הייתה שרירותית, $U$ היא כיסוי בקודקודים. $\blacksquare$

הערה מתודית מהשיעור ([00:14:59]–[00:19:48]): המרצה עצר את הכיתה פעמיים על מבנה ההוכחה ולא על התוכן. (א) בכיוון הראשון סטודנט הציע מיד "נניח בשלילה". המרצה: אל תרוצו להוכחה בשלילה כשזה לא המבנה הנכון. המבנה הנכון מתחיל מ-"יהיו $x,y \in V\setminus U$", ורק אחרי שניסחנו מה בדיוק צריך להוכיח מגיעה השלילה, ורק על הצעד הנקודתי. "לדעת לנסח מה אנחנו רוצים להוכיח זה לפעמים 90% מהפתרון". (ב) בכיוון השני: כשההנחה שלנו היא טענת "לכל" (אי-תלות של $V\setminus U$) אין מה "לצטט" אותה — פשוט מפעילים אותה על העצם הקונקרטי שבידינו. כשההנחה היא טענת "קיים", כן כדאי לפתוח אותה ולתת שם למשתנה שהיא מספקת, כי נשתמש בו בהמשך.

משפט 2: $\mathrm{IS} \le_p \mathrm{VC}$, ולכן $\mathrm{VC}$ היא NP-שלמה

הכיוון במילים: אנחנו מבצעים רדוקציה מ-$\mathrm{IS}$ (הבעיה שכבר ידוע שהיא NP-קשה) אל $\mathrm{VC}$ (הבעיה שאנחנו רוצים להוכיח שהיא קשה). התוצאה היא ש-$\mathrm{VC}$ קשה לפחות כמו $\mathrm{IS}$.

הרדוקציה (עמוד 2 בסיכום). נתבונן באלגוריתם הבא:

קלט: גרף $G=(V,E)$ ומספר $k \in \mathbb{N}$.

1. החזר את $\langle G,\ |V|-k \rangle$.

זהו. אותו גרף בדיוק, רק המספר משתנה.

ניתוח זמן ריצה. האלגוריתם מעתיק את הקלט ומבצע חיסור יחיד. במודל RAM זה אפילו זמן קבוע; במכונת טיורינג יש לבצע חיסור בינארי על מספר שאורכו לכל היותר אורך הקלט, כלומר זמן פולינומי (למעשה $O(|\langle G,k\rangle|^2)$ בגישה נאיבית). בכל מקרה — פולינומי בגודל הקלט, וזה כל מה שנדרש; אין צורך להתחייב ליותר.

נכונות. יהיו $G=(V,E)$ גרף ו-$k\in\mathbb{N}$.

כיוון $\Longrightarrow$: נניח $\langle G,k\rangle \in \mathrm{IS}$.

אז קיימת $U \subseteq V$ בלתי תלויה ב-$G$ עם $|U| = k$. לפי משפט 1, $V \setminus U$ היא כיסוי בקודקודים של $G$, וגודלה $|V\setminus U| = |V| - |U| = |V| - k .$ לכן קיים ב-$G$ כיסוי בקודקודים בגודל $|V|-k$, ומכאן $\langle G, |V|-k\rangle \in \mathrm{VC}$.

כיוון $\Longleftarrow$: נניח $\langle G,|V|-k\rangle \in \mathrm{VC}$.

אז קיים כיסוי בקודקודים $U \subseteq V$ של $G$ עם $|U| = |V|-k$. לפי משפט 1, $V\setminus U$ היא קבוצה בלתי תלויה ב-$G$, וגודלה $|V \setminus U| = |V| - (|V|-k) = k .$ לכן $\langle G,k\rangle \in \mathrm{IS}$.

קיבלנו שלכל קלט $\langle G,k\rangle$ מתקיים $\langle G,k\rangle \in \mathrm{IS} \iff \langle G,|V|-k\rangle \in \mathrm{VC}$, והאלגוריתם רץ בזמן פולינומי; לכן זו רדוקציית זמן פולינומי מ-$\mathrm{IS}$ ל-$\mathrm{VC}$, ומכאן ש-$\mathrm{VC}$ היא NP-קשה. $\blacksquare$

נקודה טכנית שהמרצה הוסיף באדום ([00:30:14]–[00:31:46], שאלת סטודנטית). בהוכחה השתמשנו בגודל בדיוק $k$ ובגודל בדיוק $|V|-k$, בעוד שההגדרות מדברות על "לפחות $k$" ב-$\mathrm{IS}$ ועל "לכל היותר $k$" ב-$\mathrm{VC}$. זה חוקי, וזו למעשה טענת עזר שכדאי לזכור:

• ב-$\mathrm{VC}$: אם יש כיסוי בגודל $\le k$ (ו-$k \le |V|$), אפשר תמיד להוסיף קודקודים שרירותיים עד לגודל $k$ בדיוק — הוספת קודקוד לכיסוי לעולם אינה מקלקלת את היותו כיסוי. לכן "קיים כיסוי בגודל לכל היותר $k$" $\iff$ "קיים כיסוי בגודל בדיוק $k$".
• ב-$\mathrm{IS}$: אם יש קבוצה בלתי תלויה בגודל $\ge k$, אפשר תמיד להוציא קודקודים עד לגודל $k$ בדיוק — תת-קבוצה של קבוצה בלתי תלויה היא בלתי תלויה. לכן "קיימת קבוצה בלתי תלויה בגודל לפחות $k$" $\iff$ "בגודל בדיוק $k$".

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

$\mathrm{VC} \in \mathrm{NP}$ ([00:31:46]). בהינתן $\langle G,k\rangle$ והעד $U \subseteq V$ (שאורכו לכל היותר $|V|$, כלומר פולינומי בגודל הקלט), המאמת בודק ש-$|U| \le k$ ועובר על כל קשת $e \in E$ ומוודא ש-$e \cap U \neq \emptyset$. זמן: $O(|E|\cdot|U|)$, פולינומי. לכן $\mathrm{VC} \in \mathrm{NP}$, ויחד עם ה-NP-קשיות: $\mathrm{VC}$ היא NP-שלמה.

שאלת סטודנט ([00:21:22]): "למה לא לקחת פשוט את הזהות כרדוקציה?" התשובה כללה שני חלקים. ראשית, הכיוון: אנחנו לא רוצים רדוקציה מ-$\mathrm{VC}$, אלא אל $\mathrm{VC}$ — כי המטרה היא להוכיח ש-$\mathrm{VC}$ קשה. שנית, הזהות "כמעט" עובדת: הגרף אכן נשאר אותו גרף, אבל המספר חייב להשתנות, בדיוק בגלל הקשר בין גודל קבוצה לגודל המשלים שלה.

משפט 3: $\mathrm{3NAE}$ ו-$\mathrm{4NAE}$ הן NP-קשות

טענה (עמוד 3 בסיכום, נמסרה כתרגיל בית, [00:43:55]). מתקיימות שתי הרדוקציות $\mathrm{3SAT} \le_p \mathrm{4NAE}, \qquad \mathrm{4NAE} \le_p \mathrm{3NAE}.$

מסקנה. מכיוון ש-$\mathrm{3SAT}$ היא NP-קשה, הרדוקציה הראשונה נותנת ש-$\mathrm{4NAE}$ היא NP-קשה; והרכבה של השתיים (טרנזיטיביות של $\le_p$) נותנת $\mathrm{3SAT} \le_p \mathrm{3NAE}$, ולכן גם $\mathrm{3NAE}$ היא NP-קשה.

הערה: בהרצאה זה נאמר בקיצור — שתי הרדוקציות עצמן נמסרו כתרגיל בית והמרצה דילג עליהן. הפירוט שנדרש כאן הוא רק חשבון הטרנזיטיביות, שאותו נכתוב במלואו: אם $f$ מחשבת את $\mathrm{3SAT}\le_p \mathrm{4NAE}$ בזמן $p(n)$ ו-$g$ מחשבת את $\mathrm{4NAE}\le_p\mathrm{3NAE}$ בזמן $q(n)$, אז $|f(x)| \le p(|x|)$ (כי בזמן $p(|x|)$ אי אפשר לכתוב יותר מ-$p(|x|)$ תווים), ולכן חישוב $g(f(x))$ עולה $p(|x|) + q(p(|x|))$ — הרכבה של פולינומים, כלומר פולינום. וכן $x\in\mathrm{3SAT} \iff f(x)\in\mathrm{4NAE} \iff g(f(x)) \in \mathrm{3NAE}$.

מכאן ואילך נשתמש ב-$\mathrm{3NAE}$ כ"נקודת המוצא הקשה" לשתי הרדוקציות הבאות.

הנחת נורמליזציה שנשתמש בה ([00:54:03]). נניח שבכל פסוקית של נוסחת $\mathrm{3CNF}$ יש בדיוק שלושה ליטרלים (שונים). זו הנחה סטנדרטית שהצדקתה פורסמה לכיתה בשקף נפרד: תמיד אפשר לשכפל ליטרל או להוסיף משתנה עזר כדי להגיע לבדיוק שלושה.

משפט 4: $\mathrm{3NAE} \le_p \mathrm{MAXCUT}$, ולכן $\mathrm{MAXCUT}$ היא NP-קשה

הכיוון במילים: רדוקציה מ-$\mathrm{3NAE}$ (עולם הנוסחאות הבוליאניות) אל $\mathrm{MAXCUT}$ (עולם הגרפים). קלט הרדוקציה הוא נוסחה; הפלט הוא זוג $\langle$מולטיגרף, מספר$\rangle$.

הרדוקציה (עמוד 4 בסיכום). נתבונן באלגוריתם הבא:

קלט: נוסחה $\varphi$ מצורת $\mathrm{3CNF}$.

1. נסמן את משתני $\varphi$ ב-$x_1,\dots,x_n$ ואת מספר הפסוקיות ב-$m$.
2. נבנה מולטיגרף $G=(V,E)$ באופן הבא:
   • 2.1 לכל $1 \le i \le n$ נגדיר קודקוד עבור $x_i$ וקודקוד עבור $\overline{x_i}$. (סה"כ $2n$ קודקודים — קודקוד לכל ליטרל.)
   • 2.2 לכל $1 \le i \le n$ נוסיף קשת בין $x_i$ ל-$\overline{x_i}$. נקרא לקשתות אלה קשתות כחולות.
   • 2.3 לכל פסוקית $C$ נוסיף קשת בין כל שני ליטרלים שלה (משולש). נקרא לקשתות אלה קשתות אדומות.
3. החזר את $\langle G,\ n+2m \rangle$.

הצבעים אינם חלק מהמתמטיקה — הם מכשיר תיאורי, כדי שיהיה נוח לדבר על "קשתות מסוג ראשון" ו-"קשתות מסוג שני" בתוך ההוכחה ([00:58:27], שאלת סטודנט).

למה מולטיגרף ([00:58:58], [01:02:15]). אם שתי פסוקיות שונות מכילות את אותו זוג ליטרלים, נקבל שתי קשתות אדומות מקבילות; ואם פסוקית מכילה גם $x_i$ וגם $\overline{x_i}$, נקבל קשת אדומה מקבילה לקשת הכחולה. אלה קשתות שונות של המולטיגרף, וזה בדיוק מה שמאפשר לספור כל פסוקית בנפרד.

ניתוח זמן ריצה ([01:05:23]–[01:08:05], עמוד 5 בסיכום). נסמן ב-$|\varphi|$ את אורך הקלט.

• שלב 1 (סימון משתנים וספירת פסוקיות): מעבר יחיד על הנוסחה, $O(|\varphi|)$.
• שלב 2.1 (יצירת קודקודים): מספר המשתנים הוא לכל היותר $|\varphi|$, ולכן $O(|\varphi|)$.
• שלב 2.2 (קשתות כחולות): $n$ קשתות, $n \le |\varphi|$, כלומר $O(|\varphi|)$.
• שלב 2.3 (קשתות אדומות): כאן היחיד שדורש נימוק. מכיוון שהנוסחה היא $\mathrm{3CNF}$, כל פסוקית תורמת בדיוק שלוש קשתות (משולש על שלושה ליטרלים). לכן סך הקשתות האדומות הוא $3m \le 3|\varphi|$, כלומר $O(|\varphi|)$. שימו לב שזה אינו ריבועי — לו הפסוקיות היו באורך שרירותי, מספר הקשתות למשולש היה ריבועי באורך הפסוקית.
• שלב 3 (חישוב $n+2m$ וכתיבת הפלט): $O(|\varphi|)$.

סך הכול האלגוריתם רץ בזמן ליניארי באורך הקלט, ובפרט פולינומי. $\checkmark$

נכונות. תהי $\varphi$ נוסחה מצורת $\mathrm{3CNF}$, נסמן את משתניה $x_1,\dots,x_n$ ואת מספר פסוקיותיה $m$, ויהי $G$ הגרף שהאלגוריתם בונה.

כיוון $\Longrightarrow$: נניח $\varphi \in \mathrm{3NAE}$.

אז קיימת הצבה $V$ המספקת את $\varphi$ במובן NAE. נגדיר $U \;=\; \{\, \ell \;\mid\; \ell \text{ a literal vertex},\ V(\ell)=1 \,\},$ כלומר $U$ היא קבוצת קודקודי הליטרלים שההצבה נותנת להם $1$. נראה שהחתך המושרה על ידי $U$ מכיל לפחות $n+2m$ קשתות.

הקשתות הכחולות. לכל $1\le i\le n$, בדיוק אחד מבין $x_i,\overline{x_i}$ מקבל את הערך $1$ (כי $V(\overline{x_i}) = 1-V(x_i)$). לכן בדיוק אחד מהם ב-$U$, ולכן הקשת הכחולה $x_i\overline{x_i}$ מקיימת $|e\cap U| = 1$ — היא בחתך. סך הכול כל $n$ הקשתות הכחולות בחתך.

הקשתות האדומות. תהי $C$ פסוקית, ויהיו $\ell_1,\ell_2,\ell_3$ ליטרליה. מכיוון ש-$V$ מספקת את $C$ במובן NAE, קיים $j$ עם $V(\ell_j)=1$ ולכן $\ell_j \in U$, וקיים $j'$ עם $V(\ell_{j'})=0$ ולכן $\ell_{j'} \notin U$. שלושת הליטרלים יוצרים משולש, וכעת נספור: שני הקודקודים $\ell_j,\ell_{j'}$ נמצאים בצדדים שונים, ולכן הקשת ביניהם חוצה. נותר הקודקוד השלישי — לא משנה באיזה צד הוא נמצא, מבין שתי הקשתות הנותרות בדיוק אחת חוצה (זו המחברת אותו לקודקוד שבצד השני). לכן מבין שלוש הקשתות של המשולש בדיוק שתיים בחתך.

בסך הכול, מכיוון שהקשתות האדומות של פסוקיות שונות הן קשתות שונות במולטיגרף, אפשר לסכום בנפרד: $|\mathrm{cut}_G(U)| \;=\; \underbrace{n}_{\text{blue}} \;+\; \underbrace{2m}_{\text{red}} \;=\; n+2m \;\ge\; n+2m .$ לכן $\langle G,n+2m\rangle \in \mathrm{MAXCUT}$.

כיוון $\Longleftarrow$: נניח $\langle G,n+2m\rangle \in \mathrm{MAXCUT}$.

אז קיימת $U \subseteq V$ כך שבחתך המושרה על ידיה יש לפחות $n+2m$ קשתות. אנחנו רוצים לבנות ממנה הצבה שמספקת את $\varphi$ במובן NAE.

צעד 1 — חסם עליון על הקשתות האדומות. כאן דרוש טיעון "הפוך" מכל השאר: עד כה עבדנו עם "לפחות", וכעת נזדקק ל-"לכל היותר". תהי $C$ פסוקית כלשהי, והמשולש המתאים לה. לא משנה מהי $U$: או ששלושת קודקודי המשולש באותו צד (אז $0$ קשתות חוצות), או שהם מתחלקים $2$–$1$ (אז בדיוק $2$ חוצות). בשני המקרים $\#\{\text{red edges of } C \text{ in the cut}\} \le 2 .$ לכן בכל חתך שהוא, סך הקשתות האדומות בחתך הוא לכל היותר $2m$.

צעד 2 — כפיית הקשתות הכחולות. בחתך שלנו יש לפחות $n+2m$ קשתות, ומהן לכל היותר $2m$ אדומות; לכן יש בו לפחות $n$ קשתות כחולות. אבל בגרף יש בסך הכול בדיוק $n$ קשתות כחולות. לכן בחתך יש בדיוק $n$ קשתות כחולות — כולן. מכאן שלכל $1\le i\le n$ הקשת $x_i\overline{x_i}$ בחתך, כלומר בדיוק אחד מבין $x_i,\overline{x_i}$ שייך ל-$U$.

צעד 3 — הגדרת ההצבה. נגדיר הצבה $V$ על ידי $V(\ell) = 1 \iff \ell \in U \qquad \text{for every literal vertex } \ell .$ מצעד 2 נובע שההגדרה עקבית ומוגדרת היטב: מכל זוג $\{x_i,\overline{x_i}\}$ בדיוק אחד ב-$U$, ולכן בדיוק אחד מקבל $1$ והשני $0$, כנדרש מהצבה.

צעד 4 — כל פסוקית מסופקת במובן NAE. בחתך יש בדיוק $n$ קשתות כחולות, ולכן מתוך לפחות $n+2m$ קשתות, לפחות $2m$ הן אדומות. מצד שני כל פסוקית תורמת לכל היותר $2$. אילו פסוקית אחת הייתה תורמת פחות מ-$2$, סך התרומות האדומות היה קטן מ-$2m$ — סתירה. לכן כל פסוקית תורמת בדיוק שתי קשתות לחתך.

תהי $C$ פסוקית. אילו כל שלושת קודקודי המשולש שלה היו באותו צד, היא הייתה תורמת $0$ קשתות. לכן היא מתחלקת: קיים ליטרל $\ell \in C$ עם $\ell \in U$, ולכן $V(\ell)=1$, וקיים ליטרל $\ell' \in C$ עם $\ell' \notin U$, ולכן $V(\ell')=0$. זו בדיוק ההגדרה של סיפוק $C$ במובן NAE.

מכיוון ש-$C$ הייתה שרירותית, $V$ מספקת את $\varphi$ במובן NAE, ולכן $\varphi \in \mathrm{3NAE}$. $\blacksquare$

מסקנה. $\mathrm{3NAE} \le_p \mathrm{MAXCUT}$ ולכן $\mathrm{MAXCUT}$ היא NP-קשה. היא גם ב-NP (העד הוא $U$; המאמת עובר על כל הקשתות וסופר כמה מהן מקיימות $|e\cap U|=1$ — זמן פולינומי), ולכן NP-שלמה.

למה דווקא 3 ([01:20:43]–[01:22:19], שאלת סטודנט "האם זה עובד לכל $k\mathrm{CNF}$?"): הקסם כאן הוא שמשולש תורם לחתך בדיוק $2$ או בדיוק $0$ — אין אפשרויות אחרות. בפסוקית בגודל $4$ או $5$ הקודקודים ה"חופשיים" יכולים להתחלק במספר דרכים ומספר הקשתות החוצות אינו נקבע חד-משמעית; החסם העליון בצעד 1 היה נעשה רופף והכפייה בצעד 2 הייתה נשברת. המרצה אמר שהוא לא בדק אם אפשר להציל את זה, אבל שהמספר $3$ "משחק מאוד חזק לטובתי" כי מספר האפשרויות זעיר.

הערה על אסימטריה של רדוקציות ([01:24:24]): בכיוון $\Longleftarrow$ סטודנטים נטו לחשוב שצריך "ללכת אחורה ברדוקציה" ולבנות נוסחה מגרף. לא. הרדוקציה אינה סימטרית: התחלנו מנוסחה $\varphi$ שקיבלנו "מהשמיים", ממנה בנה האלגוריתם את $G$, וכעת שניהם בידינו. בפרט אנחנו יודעים בדיוק איך $G$ נראה, כי אנחנו בנינו אותו. אין שום שלב שבו אמרנו "יהי $G$ גרף".

משפט 5: $\mathrm{2COL} \in \mathrm{P}$

טענה. הבעיה $\mathrm{2COL}$ — האם גרף נתון ניתן לצביעה חוקית בשני צבעים — היא ב-$\mathrm{P}$.

הוכחה. נטען ש-$G$ הוא $2$-צביע אם ורק אם $G$ הוא דו-צדדי.

$(\Rightarrow)$ תהי $f:V\to\{1,2\}$ צביעה חוקית. נגדיר $A=f^{-1}(1)$ ו-$B=f^{-1}(2)$. אלה שתי קבוצות זרות שאיחודן $V$, ולכל קשת $uv\in E$ מתקיים $f(u)\neq f(v)$, כלומר קצה אחד ב-$A$ והשני ב-$B$. לכן אין קשת בתוך $A$ ואין קשת בתוך $B$ — זו בדיוק חלוקה דו-צדדית.

$(\Leftarrow)$ אם $V = A \,\dot\cup\, B$ חלוקה דו-צדדית, נגדיר $f(v)=1$ עבור $v\in A$ ו-$f(v)=2$ עבור $v\in B$; כל קשת עוברת בין הצדדים ולכן קצותיה בצבעים שונים.

מקורס האלגוריתמים ידוע שבדיקת דו-צדדיות היא בזמן פולינומי (ואף ליניארי): גרף הוא דו-צדדי אם ורק אם אין בו מעגל באורך אי-זוגי, ואלגוריתם BFS שצובע שכבות לסירוגין מגלה מעגל אי-זוגי או מפיק חלוקה דו-צדדית. לכן $\mathrm{2COL} \in \mathrm{P}$. $\blacksquare$

הערה מהשיעור ([01:43:26]–[01:46:33]): הסטודנטית שענתה "דו-צדדי" עשתה זאת מיידית והמרצה התלהב, אבל הוסיף במפורש: "מי שלא ראה את זה — לא להרגיש לא בנוח; אני הייתי מאלה שאף פעם לא קלטו את זה בזמן השיעור". לשלוט בחומר אין פירושו לשלוף אותו בשנייה.

משפט 6: $\mathrm{3NAE} \le_p \mathrm{3COL}$, ולכן $\mathrm{3COL}$ היא NP-שלמה

הכיוון במילים: רדוקציה מ-$\mathrm{3NAE}$ אל $\mathrm{3COL}$. הקלט הוא נוסחה $\mathrm{3CNF}$; הפלט הוא גרף בלבד — אין מספר, כי $k=3$ הוא חלק מה-DNA של הבעיה.

הרדוקציה (עמוד 7 בסיכום, [01:47:38]–[01:51:01]).

קלט: נוסחה $\varphi$ מצורת $\mathrm{3CNF}$, עם משתנים $x_1,\dots,x_n$ ו-$m$ פסוקיות.

1. נבנה גרף $G=(V,E)$ כך:
   • 1.1 קודקודים: לכל $1\le i\le n$ קודקוד עבור $x_i$ וקודקוד עבור $\overline{x_i}$ (קודקודי ליטרלים); קודקוד מיוחד נוסף $N$; ולכל פסוקית $C_j$ שלושה קודקודים נוספים, אחד לכל ליטרל שלה (קודקודי פסוקית). סה"כ $2n+1+3m$ קודקודים.
   • 1.2 קשתות: נחבר את $N$ לכל קודקודי הליטרלים (קשתות שחורות, $2n$ קשתות); נחבר כל ליטרל לשלילתו (קשתות כחולות, $n$ קשתות); ולכל פסוקית נחבר את שלושת קודקודי הפסוקית זה לזה (משולש) וכן כל קודקוד פסוקית לקודקוד הליטרל המתאים לו (קשתות אדומות, $3+3=6$ קשתות לפסוקית).
2. החזר את $G$.

שימו לב להבחנה שבלבלה את הכיתה ([01:55:50], [02:07:26]): לכל פסוקית יש שלושה קודקודים משלה, שהם עצמים נפרדים מקודקודי הליטרלים. קודקוד פסוקית "מתאים" לליטרל רק במובן שקיימת ביניהם קשת אדומה.

האינטואיציה מאחורי הבנייה ([01:53:40]–[01:54:41]). נניח שיש צביעה חוקית ב-$3$ צבעים. בלי הגבלת הכלליות $f(N)=1$ (אפשר תמיד להחליף שמות צבעים). מכיוון ש-$N$ מחובר לכל קודקודי הליטרלים, כל קודקוד ליטרל צבוע ב-$2$ או ב-$3$; ומכיוון ש-$x_i$ מחובר ל-$\overline{x_i}$, מכל זוג כזה בדיוק אחד צבוע ב-$2$ ובדיוק אחד ב-$3$. כלומר הצבעים $\{2,3\}$ מתפקדים בדיוק כמו $\{\text{true},\text{false}\}$, והקודקוד $N$ "שורף" עבורנו את הצבע הראשון. זה בדיוק ההפרדה שהייתה לנו ברדוקציה הקודמת. המשולשים של הפסוקיות הם המנגנון שאוכף את תנאי ה-NAE.

ניתוח זמן ריצה ([01:56:51]–[01:57:54]).

• קודקודים: $2n$ קודקודי ליטרלים $+\,1\,+\,3m$ קודקודי פסוקיות. מכיוון ש-$n,m \le |\varphi|$, זה $O(|\varphi|)$.
• קשתות שחורות: $2n = O(|\varphi|)$.
• קשתות כחולות: $n = O(|\varphi|)$.
• קשתות אדומות: בדיוק שש לכל פסוקית (שלוש במשולש ושלוש לליטרלים), כלומר $6m = O(|\varphi|)$.

סך הכול $|V|+|E| = O(|\varphi|)$ והאלגוריתם רץ בזמן ליניארי בגודל הקלט, ובפרט פולינומי. $\checkmark$

נכונות. תהי $\varphi$ נוסחה מצורת $\mathrm{3CNF}$ ויהי $G$ הגרף שהאלגוריתם בונה.

כיוון $\Longrightarrow$: נניח $\varphi \in \mathrm{3NAE}$.

אז קיימת הצבה $V$ המספקת את $\varphi$ במובן NAE. נבנה צביעה $f : V(G) \to \{1,2,3\}$:

1. $f(N) = 1$.
2. לכל $1\le i \le n$: אם $V(x_i)=1$ אז $f(x_i)=2$ ו-$f(\overline{x_i})=3$; אחרת $f(x_i)=3$ ו-$f(\overline{x_i})=2$.
3. תהי $C$ פסוקית עם ליטרלים $\ell_1,\ell_2,\ell_3$ וקודקודי פסוקית $c_1,c_2,c_3$ (כאשר $c_t$ מחובר ל-$\ell_t$). מכיוון ש-$V$ מספקת את $C$ במובן NAE, קיים $t$ עם $V(\ell_t)=1$ וקיים $t'$ עם $V(\ell_{t'})=0$; נבחר אחד מכל סוג. נצבע:
   • $f(c_t) = 3$ (הקודקוד המתאים לליטרל שקיבל $1$),
   • $f(c_{t'}) = 2$ (הקודקוד המתאים לליטרל שקיבל $0$),
   • $f(c_{t''}) = 1$ עבור הקודקוד השלישי.

הערה חשובה על שלב 2 ([02:02:33], שאלת סטודנט): אי אפשר לצבוע "את כל ה-$x_i$ ב-$2$ ואת כל ה-$\overline{x_i}$ ב-$3$". הצביעה חייבת להיות תלויה בהצבה, כי אחרת שני ליטרלים שההצבה נתנה להם ערכים שונים היו מקבלים אותו צבע והקשר בין צבע לערך אמת היה נשבר. נשים לב שההגדרה בשלב 2 שקולה לכלל האחיד:

f(\ell) = 2 \iff V(\ell)=1, \qquad f(\ell) = 3 \iff V(\ell)=0 \qquad \text{for every literal } \ell . \tag{$\ast$}

(אכן: אם $V(x_i)=1$ אז $f(x_i)=2$ ו-$V(\overline{x_i})=0$ עם $f(\overline{x_i})=3$; ואם $V(x_i)=0$ אז $f(x_i)=3$ ו-$V(\overline{x_i})=1$ עם $f(\overline{x_i})=2$.)

כעת נוודא שאף קשת אינה מונוכרומטית, קבוצה אחרי קבוצה:

• קשתות שחורות ($N$–ליטרל): $f(N)=1$ ולכל ליטרל $f(\ell) \in \{2,3\}$, ולכן $f(N) \neq f(\ell)$. $\checkmark$
• קשתות כחולות ($x_i$–$\overline{x_i}$): לפי הבנייה בשלב 2, אחד מהם צבוע $2$ והשני $3$. $\checkmark$
• קשתות המשולש של פסוקית ($c_t$–$c_{t'}$ וכו'): לפי שלב 3 שלושת הקודקודים קיבלו $3,2,1$ — שלושה צבעים שונים. $\checkmark$
• קשתות אדומות בין קודקוד פסוקית לליטרל שלו:
  • $c_t$ (הליטרל שקיבל $1$): $f(c_t)=3$, ולפי $(\ast)$ $f(\ell_t)=2$. שונים. $\checkmark$
  • $c_{t'}$ (הליטרל שקיבל $0$): $f(c_{t'})=2$, ולפי $(\ast)$ $f(\ell_{t'})=3$. שונים. $\checkmark$
  • $c_{t''}$: $f(c_{t''})=1$, ואילו $f(\ell_{t''}) \in \{2,3\}$. שונים. $\checkmark$ (הצבע $1$ תמיד פנוי לקודקוד פסוקית, כי הצבע $1$ ניתן רק ל-$N$, ו-$N$ אינו מחובר לקודקודי פסוקיות.)

לכן $f$ היא צביעה חוקית של $G$ בשלושה צבעים, ומכאן $G \in \mathrm{3COL}$.

שימו לב גם שכל משולש פסוקית נצבע בנפרד לחלוטין, בלי להתחשב בפסוקיות אחרות ([02:07:58]) — בדיוק כמו שברדוקציה ל-$\mathrm{MAXCUT}$ כל פסוקית תרמה קשתות משלה.

כיוון $\Longleftarrow$: נניח $G \in \mathrm{3COL}$.

הערה: את הכיוון הזה המרצה השאיר כתרגיל בית ורק שרטט אותו בדקה האחרונה של ההקלטה ([02:11:40]). להלן ההשלמה המלאה, לפי הסקיצה שלו.

תהי $f$ צביעה חוקית של $G$ בשלושה צבעים. מכיוון שהחלפת שמות הצבעים (פרמוטציה על $\{1,2,3\}$) שומרת על חוקיות הצביעה, נוכל להניח בלי הגבלת הכלליות ש-$f(N)=1$.

צעד 1. כל קודקוד ליטרל $\ell$ מחובר ל-$N$ בקשת שחורה, ולכן $f(\ell) \neq 1$, כלומר $f(\ell) \in \{2,3\}$.

צעד 2. לכל $1\le i\le n$ הקשת הכחולה $x_i\overline{x_i}$ מחייבת $f(x_i)\neq f(\overline{x_i})$. יחד עם צעד 1: בדיוק אחד מבין $x_i,\overline{x_i}$ צבוע ב-$2$ והשני ב-$3$.

צעד 3 (הגדרת ההצבה). נגדיר הצבה $V$ על ידי $V(x_i) = 1 \iff f(x_i) = 2 .$ מצעד 2 נובע שאז $f(\overline{x_i})=3$, ולכן שוב מתקיים הכלל האחיד $(\ast)$: לכל ליטרל $\ell$, $\;f(\ell)=2 \iff V(\ell)=1$ ו-$f(\ell)=3 \iff V(\ell)=0$. ההגדרה עקבית ומוגדרת היטב לכל משתנה.

צעד 4 (כל פסוקית מסופקת במובן NAE). תהי $C$ פסוקית עם ליטרלים $\ell_1,\ell_2,\ell_3$ וקודקודי פסוקית $c_1,c_2,c_3$. שלושת הקודקודים $c_1,c_2,c_3$ יוצרים משולש, ולכן בצביעה חוקית הם נושאים שלושה צבעים שונים, כלומר $\{f(c_1),f(c_2),f(c_3)\} = \{1,2,3\}$. בפרט:

• קיים $t$ עם $f(c_t)=2$. הקשת האדומה $c_t\ell_t$ מחייבת $f(\ell_t)\neq 2$, ומצעד 1 נובע $f(\ell_t)=3$, ולכן לפי $(\ast)$ מתקיים $V(\ell_t)=0$.
• קיים $s$ עם $f(c_s)=3$. הקשת האדומה $c_s\ell_s$ מחייבת $f(\ell_s)\neq 3$, ולכן $f(\ell_s)=2$, ולכן $V(\ell_s)=1$.

(ו-$t \neq s$ כי הצבעים שונים, ולכן $\ell_t \neq \ell_s$ הם שני ליטרלים שונים של $C$ — כאן נכנסת ההנחה שבכל פסוקית שלושה ליטרלים שונים.)

קיבלנו שב-$C$ יש ליטרל שההצבה נותנת לו $1$ וליטרל שההצבה נותנת לו $0$ — כלומר $V$ מספקת את $C$ במובן NAE. מכיוון ש-$C$ שרירותית, $V$ מספקת את $\varphi$ במובן NAE, ולכן $\varphi \in \mathrm{3NAE}$. $\blacksquare$

מסקנה. $\mathrm{3NAE}\le_p \mathrm{3COL}$, ולכן $\mathrm{3COL}$ היא NP-קשה. היא גם ב-NP (העד הוא הצביעה $f$, שאורכה $O(|V|\log 3)$; המאמת עובר על כל הקשתות ובודק אי-מונוכרומטיות), ולכן NP-שלמה.

הרחבה (מוכחת בשיעור 11): $\mathrm{3COL} \le_p \mathrm{4COL}$