22MaxIS — Maximum Independent Set: NP-hard and coNP-hard

בקצרה

• מגדירים את $\mathrm{MaxIS}$: בהינתן גרף $G$ ומספר $k$, האם הגודל המקסימלי של קבוצה בלתי תלויה ב-$G$ הוא $k$. זו איננה בעיית $\mathrm{IS}$ הרגילה — היא מחביאה בתוכה טענת קיום וטענת לכל גם יחד.
• מוכיחים $\mathrm{SAT}\le_p\mathrm{MaxIS}$ ולכן $\mathrm{MaxIS}$ היא NP-קשה. זו אותה רדוקציה מוכרת של $\mathrm{SAT}$ ל-$\mathrm{IS}$ (קודקוד לכל ליטרל, קליקה בתוך פסוקית, קשת בין ליטרל לשלילתו), אבל הפעם צריך להוכיח גם את חסם המקסימליות $\alpha(G_\varphi)\le m$.
• מוכיחים $\overline{\mathrm{IS}}\le_p\mathrm{MaxIS}$ ולכן $\mathrm{MaxIS}$ היא גם coNP-קשה. הרדוקציה: מוסיפים $k-1$ קודקודים חדשים ומחברים כל אחד מהם לכל קודקוד ישן, ומחזירים $\langle\hat G,k-1\rangle$.
• המסקנה החריפה: $\mathrm{MaxIS}\in\mathrm{NP}\cup\mathrm{coNP}$ אם ורק אם $\mathrm{NP}=\mathrm{coNP}$. כלומר עצם ההוכחה ש-$\mathrm{MaxIS}$ בעלת אימות קצר (או שמשלימתה כזו) תפתור בעיה פתוחה. בפרט אסור לקרוא ל-$\mathrm{MaxIS}$ "NP-שלמה" — אין לנו מושג אם היא ב-$\mathrm{NP}$.
• לעומת זאת $\mathrm{IS}\in\mathrm{P}\Rightarrow\mathrm{MaxIS}\in\mathrm{P}$ בקלות (סריקה על $k$), כך שהקושי כאן הוא קושי של מבנה הטענה, לא של כמות החישוב.
• לאורך כל השיעור המרצה מלמד סגנון: טענת "לכל" מתחילה תמיד ב"תהא/יהי"; להוכחה יש גישה להשמה ולקבוצה — לאלגוריתם אין; והוכחת קיום אינה חייבת להיות אלגוריתמית.

רקע ותלויות

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

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

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

$L$ היא NP-קשה אם לכל $A\in\mathrm{NP}$ מתקיים $A\le_p L$, והיא NP-שלמה אם בנוסף $L\in\mathrm{NP}$. באופן סימטרי, $L$ היא coNP-קשה אם לכל $A\in\mathrm{coNP}$ מתקיים $A\le_p L$.

סגירות: אם $A\le_p B$ ו-$B\in\mathrm{NP}$ אז $A\in\mathrm{NP}$; אותו דבר עבור $\mathrm{P}$. וכן $\le_p$ טרנזיטיבית: $A\le_p B\le_p C \Rightarrow A\le_p C$. משתי אלה נובע הכלל שנשתמש בו שוב ושוב: כדי להראות ש-$L$ היא NP-קשה מספיק להראות $B\le_p L$ עבור $B$ אחת שכבר ידועה כ-NP-קשה.

משיעור 9 — קוק–לוין. $\mathrm{SAT}$ היא NP-שלמה. בפרט היא NP-קשה, ולכן רדוקציה מ-$\mathrm{SAT}$ אל בעיה כלשהי מוכיחה שהבעיה ההיא NP-קשה. כמו כן ראינו את השרשרת $\mathrm{SAT}\le_p 3\mathrm{SAT}\le_p\mathrm{IS}$, ולכן $\mathrm{IS}$ היא NP-שלמה.

משיעור 10 — "לפחות $k$" מול "בדיוק $k$". קבוצה בלתי תלויה היא תכונה תורשתית: כל תת-קבוצה של קבוצה בלתי תלויה היא בלתי תלויה. לכן אם יש ב-$G$ קבוצה בלתי תלויה בגודל $\ge k$, אפשר להוריד ממנה קודקודים עד לגודל $k$ בדיוק. מכאן:

קיימת ב-$G$ קבוצה בלתי תלויה בגודל לפחות $k$ אם ורק אם קיימת ב-$G$ קבוצה בלתי תלויה בגודל בדיוק $k$.

בשיעור הזה נשתמש בשוויון הזה בלי הודעה מוקדמת, בשני הכיוונים.

משיעור 21 — מחלקות משלימות. $\mathrm{coNP}=\{L \mid \overline{L}\in\mathrm{NP}\}$. שלוש עובדות משם, שכולן ישוחזרו כאן במלואן במקום שבו הן משמשות:

1. למת המשלימים: $f$ היא רדוקציה מ-$A$ ל-$B$ אם ורק אם אותה $f$ עצמה היא רדוקציה מ-$\overline{A}$ ל-$\overline{B}$ (הוכחה בלמה 3.1 להלן).
2. $\mathrm{coNP}$ סגורה תחת $\le_p$: אם $A\le_p B$ ו-$B\in\mathrm{coNP}$ אז $A\in\mathrm{coNP}$.
3. אם קיימת שפה שהיא גם NP-קשה וגם שייכת ל-$\mathrm{coNP}$ (או סימטרית: גם coNP-קשה וגם ב-$\mathrm{NP}$), אז $\mathrm{NP}=\mathrm{coNP}$.

הערת רקע על ההקלטה. ההקלטה הרלוונטית ([27], video_id AGUI69L7aDA) נפתחת מיד בחומר של השיעור הזה — אין בה קטע חזרה. בסוף ההקלטה הקודמת המרצה אף מודיע במפורש: "השיעור הבא יעסוק ב-MaxIS, נראה שהיא coNP-קשה גם".

הגדרות

הגדרה 1: הבעיה $\mathrm{MaxIS}$

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

שאלה: האם הגודל המקסימלי של קבוצה בלתי תלויה ב-$G$ הוא $k$?

כשפה: $\mathrm{MaxIS}=\{\langle G,k\rangle \mid \alpha(G)=k\}.$

הפירוק שבסיכום (שתי ההערות המודגשות בעמוד 1). הדרישה "$\alpha(G)=k$" נראית תמימה, אבל היא מחביאה בתוכה שתי טענות מסוגים שונים, והסיכום מסמן אותן בשני חצים:

• טענת קיום: קיימת ב-$G$ קבוצה בלתי תלויה בגודל $k$;
• וגם טענת "לכל": כל קבוצה בלתי תלויה ב-$G$ היא בגודל לכל היותר $k$.

זו הנקודה שכל השיעור נשען עליה. המרצה מתעכב עליה [00:01:36]–[00:03:43]: "מקסימום זה לא משהו שאני רוצה לעבוד איתו — אני רוצה לפרק את זה לפרימיטיבים". שימו לב גם לסדר: קודם אומרים שהקבוצה קיימת, ורק אחר כך מדברים עליה. סטודנט התחיל את הניסוח ב"קבוצה אחרת קטנה ממנה", והמרצה עצר: "מי זה 'ממנה'? אין פה קבוצה עדיין" [00:01:36].

דוגמה. $G=K_3$ (משולש על $a,b,c$). כל שני קודקודים מחוברים, ולכן קבוצה בלתי תלויה מכילה קודקוד אחד לכל היותר, ו-$\{a\}$ אכן בלתי תלויה. לכן $\alpha(K_3)=1$, כלומר $\langle K_3,1\rangle\in\mathrm{MaxIS}$.

אי-דוגמה (וזה בדיוק ההבדל מ-$\mathrm{IS}$). $\langle K_3,0\rangle\notin\mathrm{MaxIS}$ כי $\alpha(K_3)=1\ne 0$, וגם $\langle K_3,2\rangle\notin\mathrm{MaxIS}$ כי $1\ne 2$. לעומת זאת $\langle K_3,0\rangle\in\mathrm{IS}$ (הקבוצה הריקה בלתי תלויה) וגם $\langle K_3,1\rangle\in\mathrm{IS}$. כלומר $\mathrm{IS}$ "סובלנית כלפי מטה" ו-$\mathrm{MaxIS}$ לא — ולכן, שלא כמו ב-$\mathrm{IS}$, הטיעון התורשתי משיעור 10 אינו מאפשר להחליף כאן "$=k$" ב-"$\ge k$".

הגדרה 2: הפירוק של $\mathrm{MaxIS}$ לחיתוך שתי שפות

הפירוק שלמעלה הוא בדיוק חיתוך של שתי שפות (עמוד 5 בסיכום): $\mathrm{MaxIS}=\mathrm{IS}\ \cap\ \mathrm{IS}^{\le},$

כאשר $\mathrm{IS}$ היא אוסף הזוגות $\langle G,k\rangle$ שבהם קיימת ב-$G$ קבוצה בלתי תלויה בגודל $k$, ו-$\mathrm{IS}^{\le}$ היא אוסף הזוגות $\langle G,k\rangle$ שבהם כל קבוצה בלתי תלויה ב-$G$ היא בגודל $\le k$.

השוויון של הגורם השמאלי ל-$\mathrm{IS}$ הוא בדיוק הלמה התורשתית משיעור 10 ("בגודל $k$" $\equiv$ "בגודל לפחות $k$"). הגורם הימני, $\mathrm{IS}^{\le}$, הוא "כמעט $\overline{\mathrm{IS}}$": המרצה מנסח זאת [01:26:30] כ"עד כדי קוסמטיקה", כי $\overline{\mathrm{IS}^{\le}}=\{\langle G,k\rangle \mid \alpha(G)\ge k+1\},$ וזו בדיוק $\mathrm{IS}$ עם $k+1$ במקום $k$. בפרט $\mathrm{IS}^{\le}\in\mathrm{coNP}$ — ראו את הוכחת משפט 4.

למה זה חשוב. $\mathrm{MaxIS}$ היא חיתוך של שפה ב-$\mathrm{NP}$ עם שפה ב-$\mathrm{coNP}$. חיתוך כזה, במצב הידע הנוכחי, אינו יושב באף אחת מהמחלקות. כל השיעור הוא בעצם פירוט של ההערה הזאת.

הגדרה 3: הגרף $G_\varphi$ — הבנייה של הרדוקציה מ-$\mathrm{SAT}$

תהא $\varphi$ נוסחה בצורת CNF עם $m$ פסוקיות. נגדיר גרף $G_\varphi=(V,E)$:

1. קודקודים. לכל פסוקית ב-$\varphi$, ולכל ליטרל בפסוקית, ניצור קודקוד. נסמן ב-$V$ את קבוצת הקודקודים. שימו לב [00:08:58]: ליטרל שמופיע בכמה פסוקיות מקבל כמה קודקודים, אחד לכל מופע. הקודקוד מייצג מופע, לא משתנה.
2. קשתות אדומות (בתוך פסוקית). לכל פסוקית ב-$\varphi$, נחבר בקשת כל שני קודקודים שנוצרו מאותה פסוקית. כלומר כל פסוקית הופכת לקליקה.
3. קשתות שחורות (בין ליטרל לשלילתו). לכל ליטרל ב-$\varphi$, נחבר בקשת את הקודקודים המתאימים לו עם הקודקודים המתאימים לשלילתו.

הפלט של הרדוקציה הוא $\langle G_\varphi,m\rangle$.

האינטואיציה מאחורי כל צבע [00:13:53]:

• הקשתות האדומות מבטיחות שקבוצה בלתי תלויה תיקח לכל היותר קודקוד אחד מכל פסוקית. זה מה שיחסום את המקסימום מלמעלה ב-$m$.
• הקשתות השחורות מבטיחות שקבוצה בלתי תלויה לא תיקח בו-זמנית ליטרל ואת שלילתו — כלומר שהבחירה שלה עקבית ומתורגמת להשמה חוקית.

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

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

משפט 1: אם $\mathrm{IS}\in\mathrm{P}$ אז $\mathrm{MaxIS}\in\mathrm{P}$

זו לא טענה עמוקה, והמרצה פותח בה [00:04:14] כדי לנקות את השאלה "האם $\mathrm{MaxIS}$ קשה יותר בגלל שיש בה יותר חישוב". התשובה: לא, ההבדל הוא במבנה הלוגי בלבד.

טענה. אם קיים אלגוריתם דטרמיניסטי $A$ המכריע את $\mathrm{IS}$ בזמן $t(n)$, אז קיים אלגוריתם המכריע את $\mathrm{MaxIS}$ בזמן $O\!\left(|V|\cdot t(n)+n\right)$. בפרט אם $t$ פולינומי אז גם זמן הריצה של השני פולינומי.

הוכחה. בהינתן $\langle G,k\rangle$ עם $G=(V,E)$:

1. לכל $j=0,1,2,\dots,|V|$ נריץ את $A$ על $\langle G,j\rangle$.
2. נסמן ב-$j^\*$ את ה-$j$ הגדול ביותר שעבורו $A$ ענתה "כן".
3. נחזיר "כן" אם ורק אם $j^\*=k$.

נאותות. לפי ההגדרה $A$ עונה "כן" על $\langle G,j\rangle$ אם ורק אם $\alpha(G)\ge j$. לכן קבוצת ה-$j$-ים שעבורם התשובה "כן" היא בדיוק $\{0,1,\dots,\alpha(G)\}$ — קטע רצוף שמתחיל ב-$0$ (הקבוצה הריקה תמיד בלתי תלויה) ונגמר ב-$\alpha(G)$. מכאן ש-$j^\*$ מוגדר היטב ו-$j^\*=\alpha(G)$. לכן האלגוריתם עונה "כן" אם ורק אם $\alpha(G)=k$, כלומר אם ורק אם $\langle G,k\rangle\in\mathrm{MaxIS}$.

זמן ריצה. $|V|+1$ קריאות ל-$A$, כל אחת על קלט שאורכו $O(n)$, ועוד עבודה לינארית לניהול הלולאה. סך הכול $O(|V|\cdot t(n)+n)$. $\blacksquare$

הערה: בהרצאה הניסוח היה "אני עובר על כל ה-$k$ מאחד עד $n$ ורואה מתי הפעם הראשונה שאני מקבל 'לא'" [00:04:48]. זו בדיוק אותה סריקה, רק מלמטה למעלה. הפירוט של המונוטוניות — שקבוצת התשובות "כן" היא קטע רצוף — נאמר בהרצאה במשפט אחד, וכאן הוא כתוב מפורשות, כי בלעדיו אין הצדקה ל"הפעם הראשונה שקיבלתי 'לא'".

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

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

הרדוקציה. בהינתן נוסחה $\varphi$ בצורת CNF עם $m$ פסוקיות, נחזיר את $\langle G_\varphi,m\rangle$ כפי שהוגדר בהגדרה 3.

שימו לב שהקלט הוא CNF כללי — לא $3\mathrm{CNF}$. פסוקית יכולה להיות מכל גודל, והמרצה בחר בכוונה דוגמה שבה פסוקית אחת היא בגודל 2 "כדי שלא יבלבל אתכם שזה חייב להיות שלוש" [00:12:16].

2א. ניתוח זמן ריצה

• שלב 1 (יצירת הקודקודים) דורש $O(|\varphi|)$ צעדים: עוברים פעם אחת על הנוסחה ומייצרים קודקוד לכל מופע ליטרל. בפרט מתקיים $|V|\le|\varphi|$ — מספר הקודקודים חסום באורך הנוסחה, כי כל קודקוד נולד ממופע ליטרל אחד.
• שלבים 2 ו-3 (הקשתות) דורשים $O\!\left(\binom{|V|}{2}\right)$ צעדים: עוברים על כל הזוגות של קודקודים ומחליטים לכל זוג אם להוסיף קשת (אדומה אם באו מאותה פסוקית, שחורה אם הם ליטרל ושלילתו). לכל זוג ההחלטה היא בדיקה מקומית בזמן קבוע. ומכיוון ש-$\binom{|V|}{2}=\frac{|V|(|V|-1)}{2}=O(|V|^2)$, ובפרט $|V|\le|\varphi|$, זה $O(|\varphi|^2)$.
• סך הכול: $O(|\varphi|^2)$, כלומר הרדוקציה פולינומית באורך הקלט.

הערה: בהרצאה נשאלה שאלה [00:17:40] "למה $\binom{V}{2}$ הופך ל-$V$ בריבוע?" והתשובה: $\binom{n}{2}=\frac{n(n-1)}{2}$. באופן כללי $\binom{n}{k}\le n^k$, ולכל $k$ קבוע זה פולינומי.

2ב. ניתוח נאותות — כיוון $\Longrightarrow$

תהא $\varphi$ נוסחה בצורת CNF, ונסמן ב-$\langle G_\varphi,m\rangle$ את פלט הרדוקציה. נניח $\varphi\in\mathrm{SAT}$.

אזי קיימת השמה $\mathcal{V}$ המספקת את $\varphi$. לפי ההגדרה של סיפוק CNF:

לכל פסוקית ב-$\varphi$ קיים לפחות ליטרל אחד ש-$\mathcal{V}$ נותנת לו את הערך $1$.

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

נסמן ב-$U$ קבוצה המורכבת מקודקוד אחד כזה מכל פסוקית: מכל פסוקית בוחרים ליטרל אחד שהשמתו $1$, ולוקחים את הקודקוד המתאים לו. מכיוון שיש $m$ פסוקיות ובחרנו קודקוד אחד מכל אחת, ומכיוון שקודקודים של פסוקיות שונות שונים זה מזה (כל קודקוד נוצר ממופע יחיד), $|U|=m.$

טענה: $U$ בלתי תלויה. יהיו $x,y\in U$ שונים. צריך להראות שאין ביניהם קשת. יש שני סוגי קשתות בלבד:

• קשת אדומה? ב-$U$ יש בדיוק קודקוד אחד המשויך לכל פסוקית, ולכן $x$ ו-$y$ נוצרו מפסוקיות שונות. קשת אדומה מחברת רק קודקודים מאותה פסוקית, ולכן אין ביניהם קשת אדומה.
• קשת שחורה? לפי בחירת $U$, ההשמה $\mathcal{V}$ נותנת לשני הליטרלים המתאימים ל-$x$ ול-$y$ את הערך $1$. אבל ליטרל ושלילתו לעולם לא מקבלים שניהם $1$ תחת אותה השמה. לכן לא ייתכן ש-$x$ ו-$y$ הם ליטרל ושלילתו, ולכן אין ביניהם קשת שחורה.

מכאן ש-$U$ בלתי תלויה, וקיבלנו קבוצה בלתי תלויה בגודל $m$ ב-$G_\varphi$.

עדיין לא סיימנו [00:25:12]. עד כאן הוכחנו רק את חצי הטענה — את חלק ה"קיים". זה בדיוק הנקודה שבה תרגיל הבית על $\mathrm{SAT}\le_p\mathrm{IS}$ מסתיים; כאן צריך גם את חלק ה"לכל".

טענה 2.1 (חסם המקסימליות): כל קבוצה בלתי תלויה ב-$G_\varphi$ היא בגודל לכל היותר $m$.

הוכחה (הגרסה הישירה, [00:29:26]). תהא $\hat U$ קבוצה בלתי תלויה ב-$G_\varphi$. כל שני קודקודים המשויכים לאותה פסוקית מחוברים בקשת אדומה, ומכיוון ש-$\hat U$ בלתי תלויה, אין ב-$\hat U$ שני קודקודים מאותה פסוקית. לכן $\hat U$ מכילה לכל היותר קודקוד אחד מכל פסוקית, ויש $m$ פסוקיות, ולכן $|\hat U|\le m$.

הוכחה (הגרסה בשלילה, כפי שנרשמה בסיכום). נניח בשלילה $|\hat U|>m$. לפי עקרון שובך היונים, מכיוון שיש $m$ פסוקיות ו-$|\hat U|>m$ קודקודים, קיימת פסוקית שעבורה קיימים שני ליטרלים ממנה שהקודקודים המתאימים להם שייכים ל-$\hat U$. אבל שניהם מאותה פסוקית, ולכן יש ביניהם קשת אדומה — בסתירה לכך ש-$\hat U$ בלתי תלויה. $\square$

הערה מתודית חשובה [00:26:14]–[00:29:56]. סטודנטית הציעה לפתוח את ההוכחה ב"נניח בשלילה שיש קבוצה גדולה יותר", והמרצה עצר: הטענה שרוצים להוכיח היא טענת "לכל" ("לכל קבוצה בלתי תלויה..."), ולכן ההוכחה חייבת להתחיל ב"תהא $\hat U$ קבוצה בלתי תלויה". רק אחרי שהמשתנה הוצג אפשר להניח בשלילה. "אם הטענה מתחילה ב'לכל', לעולם ההוכחה תתחיל ב'יהי/תהא'... זה מה שמציג לי את המשתנה שאני אעבוד איתו אחר כך."

שילוב שתי הטענות: קיימת קבוצה בלתי תלויה בגודל $m$, וכל קבוצה בלתי תלויה היא בגודל $\le m$. לכן $\alpha(G_\varphi)=m$, כלומר $\langle G_\varphi,m\rangle\in\mathrm{MaxIS}.$

הערה: שימו לב שטענה 2.1 נכונה לכל $\varphi$, גם לא ספיקה. היא תלויה אך ורק בקשתות האדומות. נשתמש בה שוב בכיוון ההפוך.

2ג. ניתוח נאותות — כיוון $\Longleftarrow$

נניח $\langle G_\varphi,m\rangle\in\mathrm{MaxIS}$, כלומר $\alpha(G_\varphi)=m$. אזי קיימת $U$ בלתי תלויה ב-$G_\varphi$ כך ש-$|U|=m$.

1. $U$ בלתי תלויה, ולכן בין כל שני קודקודים ב-$U$ אין קשת אדומה. מכאן ש-$U$ מכילה לכל היותר קודקוד אחד מכל פסוקית.
2. מכיוון ש-$|U|=m$ ויש בדיוק $m$ פסוקיות, ולכל פסוקית לכל היותר קודקוד אחד — לפי שובך יונים (הפעם בכיוון הצפוף) $U$ מכילה בדיוק קודקוד אחד מכל פסוקית.

הערה [00:31:51]–[00:32:54]. אלה שני טיעונים נפרדים, לא אחד: הראשון (אין שניים) מגיע מאי-התלות, השני (יש בדיוק אחד) מגיע מספירה. המרצה עמד על ההפרדה: "כמה שאני יותר אפרק את הטיעון שלי, אני פחות פרון לעשות טעויות".

3. $U$ בלתי תלויה, ולכן לכל $x,y\in U$ אין ביניהם קשת שחורה. לכן אין ב-$U$ שני קודקודים המתאימים לליטרל ולשלילתו.
4. אוסף הליטרלים המתאימים לקודקודי $U$ הוא אפוא אוסף עקבי: אין בו משתנה שמופיע גם חיובי וגם שלילי. לכן קיימת השמה $\mathcal{V}$ המספקת את כל הליטרלים המתאימים לקודקודים ב-$U$ (למשל: לכל משתנה שמופיע באוסף נותנים את הערך שמספק את המופע שלו; לשאר המשתנים נותנים ערך שרירותי, נניח $0$).
5. לפי סעיף 2, ב-$U$ יש קודקוד מכל פסוקית, ולכן $\mathcal{V}$ מספקת לפחות ליטרל אחד בכל פסוקית של $\varphi$, כלומר $\mathcal{V}$ מספקת את $\varphi$.

מכאן $\varphi\in\mathrm{SAT}$.

הערה — "קיימת" ולא "ניתן לקבוע" [00:34:31]–[00:35:37]. סטודנט הציע לומר "אפשר לקבוע את ההשמה", והמרצה סירב: הניסוח הזה רומז ליחידות, ואין כאן יחידות. בדוגמה הקונקרטית שלמטה יש שתי השמות שמספקות את הליטרלים של $U$, כי המשתנה $x_4$ אינו מופיע ב-$U$ כלל וערכו חופשי. הניסוח הנכון הוא "קיימת השמה".

הערה — הוכחת קיום מול הוכחה אלגוריתמית [00:36:38]–[00:37:39]. בסעיף 4 ההוכחה מפסיקה להיות אלגוריתמית: לא הראינו איך בוחרים את $\mathcal{V}$, רק שהיא קיימת. וזה מספיק — הרדוקציה מחייבת אותנו להוכיח קיום גורר קיום, וטיעון אלגוריתמי הוא רק דרך אחת להוכיח קיום. המרצה הביא בהשוואה את המשפט "בכל עץ יש עלה", שההוכחה שלו (סכימת דרגות) אינה אלגוריתמית כלל.

2ד. סיכום המשפט

הראינו: הרדוקציה מוגדרת היטב, פולינומית, ולכל $\varphi$ מתקיים $\varphi\in\mathrm{SAT}\iff\langle G_\varphi,m\rangle\in\mathrm{MaxIS}$. לכן $\mathrm{SAT}\le_p\mathrm{MaxIS}$. מכיוון ש-$\mathrm{SAT}$ היא NP-קשה ו-$\le_p$ טרנזיטיבית — לכל $A\in\mathrm{NP}$ מתקיים $A\le_p\mathrm{SAT}\le_p\mathrm{MaxIS}$ ולכן $A\le_p\mathrm{MaxIS}$ — מכאן ש-$\mathrm{MaxIS}$ היא NP-קשה. $\blacksquare$

הערה טכנית (השלמה שלנו, לא במקורות). אם ב-$\varphi$ יש פסוקית ריקה, אין לה קודקודים כלל, ואז $\alpha(G_\varphi)\le m-1<m$ ולכן $\langle G_\varphi,m\rangle\notin\mathrm{MaxIS}$ — וזה נכון, כי נוסחה עם פסוקית ריקה איננה ספיקה. אם פסוקית מכילה ליטרל ואת שלילתו, הזוג המתאים מחובר גם בקשת אדומה וגם בקשת שחורה; זו אותה קשת בגרף פשוט וההוכחה אינה משתנה.

משפט 3: $\overline{\mathrm{IS}}\le_p\mathrm{MaxIS}$, ולכן $\mathrm{MaxIS}$ היא coNP-קשה

3א. למת המשלימים, ולמה בכלל מתחילים מ-$\overline{\mathrm{IS}}$

למה 3.1 (הקופסה הכחולה בעמוד 3; משיעור 21). תהא $f$ פונקציה הניתנת לחישוב בזמן פולינומי. אז

$f$ היא רדוקציה מ-$A$ ל-$B$ אם ורק אם $f$ היא רדוקציה מ-$\overline{A}$ ל-$\overline{B}$.

הוכחה. $f$ רדוקציה מ-$A$ ל-$B$ פירושו: לכל $x$, מתקיים $x\in A\iff f(x)\in B$. שקילות לוגית שקולה לשקילות של שני השלילות: $x\notin A\iff f(x)\notin B$, כלומר $x\in\overline{A}\iff f(x)\in\overline{B}$ — וזה בדיוק "$f$ רדוקציה מ-$\overline{A}$ ל-$\overline{B}$". החישוביות בזמן פולינומי היא תכונה של $f$ בלבד ואינה מושפעת. $\square$

בניסוח של ההרצאה [00:46:13]: "כל מה שב-$A$ הולך ל-$B$, וכל מה שלא ב-$A$ הולך ללא-$B$. עכשיו תסתכל על זה מהזווית ההפוכה — זו אותה רדוקציה בדיוק."

מסקנה 3.2. מכיוון ש-$\mathrm{IS}$ היא NP-שלמה, $\overline{\mathrm{IS}}$ היא coNP-שלמה. אכן, יהא $A\in\mathrm{coNP}$. אז $\overline{A}\in\mathrm{NP}$, ולכן קיימת רדוקציה $f$ מ-$\overline{A}$ ל-$\mathrm{IS}$. לפי למה 3.1 אותה $f$ היא רדוקציה מ-$A$ ל-$\overline{\mathrm{IS}}$. לכן לכל $A\in\mathrm{coNP}$ מתקיים $A\le_p\overline{\mathrm{IS}}$.

מסקנה 3.3. לכן, אם נוכיח $\overline{\mathrm{IS}}\le_p\mathrm{MaxIS}$, נקבל מטרנזיטיביות שלכל $A\in\mathrm{coNP}$ מתקיים $A\le_p\overline{\mathrm{IS}}\le_p\mathrm{MaxIS}$, ומכאן ש-$\mathrm{MaxIS}$ היא coNP-קשה.

למה דווקא $\overline{\mathrm{IS}}\le_p\mathrm{MaxIS}$ ולא $\mathrm{IS}\le_p\overline{\mathrm{MaxIS}}$? [00:46:44]–[00:49:22]. לפי למה 3.1 אלה אותה רדוקציה בדיוק, אז זו שאלה של נוחות כתיבה — והמרצה מסביר את הבחירה, וזה אחד הרגעים הכי מלמדים בשיעור. שייכות ל-$\mathrm{MaxIS}$ היא טענת "וגם" ("קיים... וגם לכל..."). השלילה של טענת "וגם" היא טענת "או", ואת אלה לא נעים להוכיח. אם נכתוב $\overline{\mathrm{IS}}\le_p\mathrm{MaxIS}$, אז בכיוון אחד נצטרך להוכיח שייכות ל-$\mathrm{MaxIS}$ (טענת "וגם" — מוכיחים שני חלקים, כל אחד לחוד), ובכיוון השני להשתמש בשייכות ל-$\mathrm{MaxIS}$ (שוב "וגם" — מקבלים שני דברים). לעומת זאת $\mathrm{IS}\le_p\overline{\mathrm{MaxIS}}$ היה מחייב אותנו להתעסק עם טענות "או". האנלוגיה של המרצה: טענת "וגם" היא כמו תרגיל כפל שכל אחד מהכופלים בו הוא תרגיל חיבור — שני חלקים מוכרים; טענת "או" היא חיה אחרת.

3ב. הרדוקציה

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

1. נוסיף ל-$G$ עוד $k-1$ קודקודים חדשים. נסמן ב-$\hat V$ את קבוצת הקודקודים החדשה (כלומר $\hat V$ הוא $V$ יחד עם הקודקודים החדשים, ו-$\hat V\setminus V$ הם החדשים בלבד, $|\hat V\setminus V|=k-1$).
2. נוסיף קשתות מכל קודקוד חדש אל כל אחד מהקודקודים ב-$V$. נסמן ב-$\hat E$ את קבוצת הקשתות המתקבלת. שימו לב: בין הקודקודים החדשים לבין עצמם אין קשתות, ובין קודקודי $V$ לבין עצמם לא הוספנו ולא הסרנו כלום.
3. נחזיר את $\langle\hat G,k-1\rangle$ כאשר $\hat G=(\hat V,\hat E)$.

האינטואיציה [00:51:47]–[00:53:21]. אנחנו רוצים ש-$\langle G,k\rangle\in\overline{\mathrm{IS}}$ (כלומר: אין ב-$G$ קבוצה בלתי תלויה בגודל $k$) יתורגם לשאלת מקסימום. אם אין ב-$G$ קבוצה בלתי תלויה בגודל $k$, אז המקסימום ב-$G$ הוא לכל היותר $k-1$ — אבל אין לנו ערובה שהוא בדיוק $k-1$. לכן "שותלים" קבוצה בלתי תלויה בגודל $k-1$ בדיוק. סטודנט הציע להוסיף $k-1$ קודקודים מבודדים, והמרצה: "זה כמעט נכון" — קודקודים מבודדים היו מצטרפים לקבוצות הישנות ומגדילים את המקסימום. לכן מחברים כל קודקוד חדש לכל הקודקודים הישנים: כך הקבוצה החדשה קיימת אך אינה מתערבבת.

טיפול ב-$k=0$ (השלמה שלנו — אינו מופיע באף אחד מהמקורות). לכל גרף מתקיים $\langle G,0\rangle\in\mathrm{IS}$ (הקבוצה הריקה בלתי תלויה ו-$|\emptyset|=0\ge0$), ולכן $\langle G,0\rangle\notin\overline{\mathrm{IS}}$. נגדיר אפוא שעל קלט עם $k=0$ הרדוקציה מחזירה מחרוזת קבועה שאיננה ב-$\mathrm{MaxIS}$, למשל $\langle K_1,0\rangle$ (גרף בעל קודקוד יחיד, ו-$\alpha(K_1)=1\ne0$). מכאן ואילך נניח $k\ge1$, ואז $k-1\ge0$ והבנייה חוקית.

3ג. ניתוח זמן ריצה

• הוספת הקודקודים: $O(|V|)$. כאן נדרשת הבחנה עדינה [00:59:54]–[01:00:24]: בגודל הייצוג של הקלט, המספר $k$ תופס רק $\log k$ ביטים, ולכן אסור לחסום שום דבר "באמצעות $k$". אבל מותר להניח בלי הגבלת הכלליות $k\le|V|$: אם $k>|V|$ אז בוודאי אין ב-$G$ קבוצה בלתי תלויה בגודל $k$, כי אין בו בכלל $k$ קודקודים, והרדוקציה יכולה להחזיר במקרה זה מחרוזת קבועה ששייכת ל-$\mathrm{MaxIS}$ (למשל $\langle K_1,1\rangle$). לכן $k-1<|V|$ והוספת הקודקודים היא $O(|V|)$.
• הוספת הקשתות: לכל אחד מ-$k-1$ הקודקודים החדשים מוסיפים $|V|$ קשתות (אחת לכל קודקוד ישן), כלומר $(k-1)\cdot|V|=O(|V|^2)$ קשתות. זה גם מסדר גודל $O(|V|^2)$ צעדים.
• סך הכול: $O\!\left(|\langle G,k\rangle|^2\right)$, כלומר פולינומי בגודל הקלט.

הערה [00:56:09]. סטודנט חשב שכל קודקוד חדש מקבל $k$ קשתות; המרצה הבהיר: כל קודקוד חדש מקבל קשת לכל קודקוד ישן, כלומר $|V|$ קשתות, ובסך הכול $(k-1)\cdot|V|$.

3ד. ניתוח נאותות — כיוון $\Longrightarrow$

יהי $G=(V,E)$ ו-$k\in\mathbb{N}$, ונניח $\langle G,k\rangle\in\overline{\mathrm{IS}}$ — כלומר אין ב-$G$ קבוצה בלתי תלויה בגודל $k$. צריך להוכיח $\langle\hat G,k-1\rangle\in\mathrm{MaxIS}$, כלומר את שני חלקי ה"וגם".

(א) חלק הקיום. הקבוצה $\hat V\setminus V$ (הקודקודים החדשים) היא קבוצה בלתי תלויה ב-$\hat G$: הרדוקציה לא הוסיפה שום קשת בין שני קודקודים חדשים. גודלה בדיוק $k-1$. לכן קיימת ב-$\hat G$ קבוצה בלתי תלויה בגודל $k-1$. $\checkmark$

(ב) חלק ה"לכל". תהא $U\subseteq\hat V$ קבוצה בלתי תלויה ב-$\hat G$.

ב-$\hat G$ יש קשת בין כל קודקוד ב-$\hat V\setminus V$ ובין כל קודקוד ב-$V$ — כך בנינו. לכן $U$ אינה יכולה להכיל בו-זמנית קודקוד חדש וקודקוד ישן, ומכאן שמתקיים אחד משניים: $U\subseteq\hat V\setminus V$

או

$U\subseteq V.$

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

בשני המקרים $|U|\le k-1$. $\checkmark$

משני החלקים: המקסימום ב-$\hat G$ הוא בדיוק $k-1$, כלומר $\langle\hat G,k-1\rangle\in\mathrm{MaxIS}$.

הערה — שאלת סטודנט (עומר), [01:09:51]–[01:11:54]. למה מ"אין קבוצה בגודל $k$" נובע "אין קבוצה בגודל $>k$"? התשובה: הרדוקציה בכלל לא נוגעת בקבוצות הבלתי תלויות — היא מטפלת בגרף בלבד. הטיעון על התורשתיות הוא טיעון של ההוכחה, לא של האלגוריתם: ברמת ההוכחה אני לוקח קבוצה בלתי תלויה בגודל $k+1$, מוריד ממנה קודקוד אחד, ומקבל קבוצה בלתי תלויה בגודל $k$. המרצה חזר על ההבחנה הזו פעמיים: "האלגוריתם לא נוגע בפתרון לבעיה, הוא רק מטפל בגרף".

3ה. ניתוח נאותות — כיוון $\Longleftarrow$

נניח $\langle\hat G,k-1\rangle\in\mathrm{MaxIS}$. צריך להוכיח $\langle G,k\rangle\in\overline{\mathrm{IS}}$, כלומר: לכל קבוצה בלתי תלויה $U$ ב-$G$ מתקיים $|U|\ne k$. זו טענת "לכל", ולכן — כמו שהמרצה עמד על כך שוב [01:04:54] — נתחיל ב"תהא".

תהא $U\subseteq V$ קבוצה בלתי תלויה ב-$G$.

1. הרדוקציה לא הוסיפה שום קשת בין קודקודי $V$ (הקשתות היחידות שהוספנו יוצאות מהקודקודים החדשים). לכן $U$, כתת-קבוצה של $\hat V$, היא גם קבוצה בלתי תלויה ב-$\hat G$.
2. מהנחתנו $\alpha(\hat G)=k-1$, ולכן כל קבוצה בלתי תלויה ב-$\hat G$ היא בגודל $\le k-1$. בפרט $|U|\le k-1$.
3. מכאן בפרט $|U|\ne k$.

מכיוון שזה נכון לכל $U$ בלתי תלויה ב-$G$, אין ב-$G$ קבוצה בלתי תלויה בגודל $k$, כלומר $\langle G,k\rangle\in\overline{\mathrm{IS}}$.

3ו. סיכום המשפט

הרדוקציה מוגדרת היטב, פולינומית, ולכל קלט $\langle G,k\rangle$ מתקיים $\langle G,k\rangle\in\overline{\mathrm{IS}}\iff\langle\hat G,k-1\rangle\in\mathrm{MaxIS}$. לכן $\overline{\mathrm{IS}}\le_p\mathrm{MaxIS}$, ולפי מסקנות 3.2–3.3 — $\mathrm{MaxIS}$ היא coNP-קשה. $\blacksquare$

מסקנה מיידית. $\mathrm{MaxIS}$ היא גם NP-קשה וגם coNP-קשה. שתי התכונות האלה יחד הן שיוצרות את המצב המוזר של המשפט הבא.

משפט 4: $\mathrm{MaxIS}\in\mathrm{NP}\cup\mathrm{coNP}$ אם ורק אם $\mathrm{NP}=\mathrm{coNP}$

זהו התרגיל שהמרצה נתן בכיתה [01:12:44] וגם פתר. שימו לב לצורת השאלה: מבקשים להראות שטענה על מחלקות סיבוכיות שקולה לבעיה פתוחה. המרצה מדגיש [01:13:17]: הצעד הראשון בתרגיל כזה הוא לבחור את הבעיה הפתוחה הנכונה. כאן המועמדת הטבעית היא $\mathrm{NP}=\mathrm{coNP}$ ולא $\mathrm{P}=\mathrm{NP}$, "כי $\mathrm{P}$ לא מוזכרת פה בכלל".

4א. כיוון $\Longrightarrow$: אם $\mathrm{MaxIS}\in\mathrm{NP}\cup\mathrm{coNP}$ אז $\mathrm{NP}=\mathrm{coNP}$

נשתמש פעמיים בלמת עזר:

למה 4.1. $\mathrm{coNP}$ סגורה תחת $\le_p$: אם $A\le_p B$ ו-$B\in\mathrm{coNP}$ אז $A\in\mathrm{coNP}$. הוכחה. תהא $f$ הרדוקציה מ-$A$ ל-$B$. לפי למה 3.1, $f$ היא גם רדוקציה מ-$\overline{A}$ ל-$\overline{B}$. מכיוון ש-$B\in\mathrm{coNP}$, מתקיים $\overline{B}\in\mathrm{NP}$, ומכיוון ש-$\mathrm{NP}$ סגורה תחת $\le_p$ (שיעור 7) נקבל $\overline{A}\in\mathrm{NP}$, כלומר $A\in\mathrm{coNP}$. $\square$

למה 4.2. אם $\mathrm{coNP}\subseteq\mathrm{NP}$ אז $\mathrm{NP}=\mathrm{coNP}$, וכן להפך. הוכחה. נניח $\mathrm{coNP}\subseteq\mathrm{NP}$, ותהא $L\in\mathrm{NP}$. אז $\overline{L}\in\mathrm{coNP}\subseteq\mathrm{NP}$, ולכן $\overline{L}\in\mathrm{NP}$, ולכן לפי ההגדרה $L\in\mathrm{coNP}$. קיבלנו $\mathrm{NP}\subseteq\mathrm{coNP}$, ויחד עם ההנחה — שוויון. הכיוון השני סימטרי לחלוטין. $\square$

כעת נניח $\mathrm{MaxIS}\in\mathrm{NP}\cup\mathrm{coNP}$, ונחלק לשני מקרים.

מקרה 1: $\mathrm{MaxIS}\in\mathrm{NP}$. לפי משפט 3, $\mathrm{MaxIS}$ היא coNP-קשה, כלומר לכל $A\in\mathrm{coNP}$ מתקיים $A\le_p\mathrm{MaxIS}$. מכיוון ש-$\mathrm{NP}$ סגורה תחת $\le_p$ ו-$\mathrm{MaxIS}\in\mathrm{NP}$, נקבל $A\in\mathrm{NP}$ לכל $A\in\mathrm{coNP}$, כלומר $\mathrm{coNP}\subseteq\mathrm{NP}$. לפי למה 4.2, $\mathrm{NP}=\mathrm{coNP}$.

מקרה 2: $\mathrm{MaxIS}\in\mathrm{coNP}$. לפי משפט 2, $\mathrm{MaxIS}$ היא NP-קשה, כלומר לכל $A\in\mathrm{NP}$ מתקיים $A\le_p\mathrm{MaxIS}$. לפי למה 4.1, $A\in\mathrm{coNP}$. לכן $\mathrm{NP}\subseteq\mathrm{coNP}$, ולפי למה 4.2 שוב $\mathrm{NP}=\mathrm{coNP}$.

בשני המקרים $\mathrm{NP}=\mathrm{coNP}$. $\checkmark$

הערה [01:19:33]–[01:22:15]. סטודנט שאל למה מקרה 2 עובד. התשובה של המרצה: זה "משחק משלימים" — אם $\mathrm{MaxIS}\in\mathrm{coNP}$ אז $\overline{\mathrm{MaxIS}}\in\mathrm{NP}$, והיא coNP-קשה, וחוזרים למקרה 1. שתי הדרכים נכונות; כאן הובאה הגרסה הישירה עם למה 4.1.

4ב. כיוון $\Longleftarrow$: אם $\mathrm{NP}=\mathrm{coNP}$ אז $\mathrm{MaxIS}\in\mathrm{NP}\cup\mathrm{coNP}$

תחילה הבחנה [01:22:49]: אם $\mathrm{NP}=\mathrm{coNP}$ אז $\mathrm{NP}\cup\mathrm{coNP}=\mathrm{NP}$, ולכן די להוכיח $\mathrm{MaxIS}\in\mathrm{NP}$.

נשתמש בפירוק מהגדרה 2: $\mathrm{MaxIS}=\mathrm{IS}\ \cap\ \mathrm{IS}^{\le},$

כאשר $\mathrm{IS}^{\le}$ היא אוסף הזוגות $\langle G,k\rangle$ שבהם כל קבוצה בלתי תלויה ב-$G$ היא בגודל $\le k$.

(א) $\mathrm{IS}\in\mathrm{NP}$ — משיעור 7 (העד הוא קבוצת הקודקודים; האימות בודק שגודלה $\ge k$ ושאין בין אבריה קשת, בזמן פולינומי).

(ב) $\mathrm{IS}^{\le}\in\mathrm{coNP}$. נראה ש-$\overline{\mathrm{IS}^{\le}}\in\mathrm{NP}$. לפי ההגדרה, $\overline{\mathrm{IS}^{\le}}$ היא אוסף הזוגות $\langle G,k\rangle$ שבהם קיימת ב-$G$ קבוצה בלתי תלויה בגודל לפחות $k+1$. זו בדיוק $\mathrm{IS}$ עם $k+1$ במקום $k$. אפשר לומר זאת בשתי דרכים, ושתיהן הוזכרו בהרצאה [01:28:04]:

• באמצעות רדוקציה: הפונקציה $\langle G,k\rangle\mapsto\langle G,k+1\rangle$ ניתנת לחישוב בזמן פולינומי (הוספת $1$ למספר בייצוג בינארי), והיא רדוקציה מ-$\overline{\mathrm{IS}^{\le}}$ ל-$\mathrm{IS}$. מכיוון ש-$\mathrm{IS}\in\mathrm{NP}$ ו-$\mathrm{NP}$ סגורה תחת $\le_p$, נקבל $\overline{\mathrm{IS}^{\le}}\in\mathrm{NP}$.
• באמצעות מאמת ישיר: העד הוא קבוצת קודקודים $U$; המאמת בודק ש-$|U|\ge k+1$ ושלכל $x,y\in U$ מתקיים $xy\notin E$. אורך העד $O(|V|\log|V|)$ פולינומי, וזמן האימות $O(|U|^2)$ פולינומי.

לכן $\mathrm{IS}^{\le}\in\mathrm{coNP}$.

(ג) הפעלת ההנחה. מההנחה $\mathrm{NP}=\mathrm{coNP}$ נובע $\mathrm{IS}^{\le}\in\mathrm{NP}$.

(ד) סגירות לחיתוך. $\mathrm{NP}$ סגורה תחת חיתוך. בפירוט: אם $L_1,L_2\in\mathrm{NP}$ עם מאמתים $M_1,M_2$ ואורכי עדים $p_1(n),p_2(n)$, נגדיר מאמת ל-$L_1\cap L_2$ שמקבל עד $w=\langle w_1,w_2\rangle$ באורך $p_1(n)+p_2(n)+O(\log n)$, מפצל אותו, ומריץ את $M_1$ על $\langle x,w_1\rangle$ ואת $M_2$ על $\langle x,w_2\rangle$, ומקבל אם ורק אם שניהם קיבלו. הזמן והאורך פולינומיים, ו-$x\in L_1\cap L_2$ אם ורק אם קיימים שני עדים כאלה.

לכן $\mathrm{MaxIS}=\mathrm{IS}\cap\mathrm{IS}^{\le}\in\mathrm{NP}\subseteq\mathrm{NP}\cup\mathrm{coNP}$. $\blacksquare$

4ג. מה זה אומר בפועל

מסקנה 4.3. אילו ידענו ש-$\mathrm{MaxIS}\in\mathrm{NP}$, היינו מקבלים מיד $\mathrm{NP}=\mathrm{coNP}$ — בעיה פתוחה. לכן:

• אסור לומר ש-$\mathrm{MaxIS}$ היא NP-שלמה. NP-שלמות דורשת שייכות ל-$\mathrm{NP}$, וזו בדיוק הנקודה שאנחנו לא יודעים. המרצה נשאל על כך ישירות [00:42:27] וענה "אני באמת לא יודע — זו שאלה פתוחה".
• מסקנה 4.4. אם $\mathrm{MaxIS}\in\mathrm{P}$ אז $\mathrm{P}=\mathrm{NP}$. אכן, $\mathrm{P}$ סגורה תחת $\le_p$, ו-$\mathrm{MaxIS}$ היא NP-קשה, ולכן כל $A\in\mathrm{NP}$ מקיימת $A\le_p\mathrm{MaxIS}\in\mathrm{P}$ ולכן $A\in\mathrm{P}$. (יחד עם משפט 1 זה נותן: אם $\mathrm{IS}\in\mathrm{P}$ אז $\mathrm{MaxIS}\in\mathrm{P}$ ואז $\mathrm{P}=\mathrm{NP}$ — עקבי עם NP-שלמותה של $\mathrm{IS}$.)

התמונה הכללית של הבעיות הפתוחות [01:14:19]–[01:15:52]. המרצה שרטט את מה שידוע ומה שלא: $\mathrm{P}\subseteq\mathrm{NP}\cap\mathrm{coNP}\subseteq\mathrm{NP},\qquad \mathrm{P}\subseteq\mathrm{NP}\cap\mathrm{coNP}\subseteq\mathrm{coNP}.$ שלוש שאלות פתוחות בו-זמנית: האם $\mathrm{P}=\mathrm{NP}$? האם $\mathrm{NP}=\mathrm{coNP}$? והאם $\mathrm{NP}\cap\mathrm{coNP}=\mathrm{P}$? "תיאורטית יכול להיות שיש בעיה שהיא גם ב-$\mathrm{NP}$ וגם ב-$\mathrm{coNP}$ והיא לא ב-$\mathrm{P}$. המצב פה הרבה יותר מורכב ממה שהיה בחישוביות, שם $\mathrm{R}=\mathrm{RE}\cap\mathrm{coRE}$ בדיוק."

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

דוגמה 1: הרצת הרדוקציה $\mathrm{SAT}\le_p\mathrm{MaxIS}$ מקצה לקצה

זו הדוגמה שעל הלוח ובעמוד 1 בסיכום. הנוסחה: $\varphi=(\overline{x_1}\vee x_2\vee\overline{x_3})\wedge(x_1\vee\overline{x_2}\vee x_4)\wedge(x_3\vee x_4\vee x_2)\wedge(x_1\vee x_3).$ כאן $m=4$. הפסוקית הרביעית היא בגודל $2$ בכוונה, כדי להזכיר שהרדוקציה עובדת ל-CNF כללי.

שלב 1 — קודקודים. מופע ליטרל $\to$ קודקוד. $11$ קודקודים, מסודרים בשורות לפי פסוקית:

שלב 2 — קשתות אדומות (קליקה בכל שורה), $10$ קשתות: $u_1u_2,\ u_1u_3,\ u_2u_3;\quad u_4u_5,\ u_4u_6,\ u_5u_6;\quad u_7u_8,\ u_7u_9,\ u_8u_9;\quad u_{10}u_{11}.$

שלב 3 — קשתות שחורות (ליטרל $\leftrightarrow$ שלילתו), $6$ קשתות:

סך הכול $|V|=11$, $|E|=16$. הפלט: $\langle G_\varphi,4\rangle$.

כיוון $\Longrightarrow$ (מהשמה לקבוצה). ההשמה שנבחרה בכיתה [00:22:31]: $\mathcal{V}(x_1)=1,\quad \mathcal{V}(x_2)=1,\quad \mathcal{V}(x_3)=1,\quad \mathcal{V}(x_4)=0.$ נבדוק שהיא מספקת: $C_1$ — $x_2=1$ $\checkmark$; $C_2$ — $x_1=1$ $\checkmark$; $C_3$ — $x_3=1$ $\checkmark$; $C_4$ — $x_1=1$ $\checkmark$.