7CLIQUE ו-Independent Set, רדוקציות בזמן פולינומי, NP-קשה ו-NP-שלמה

בקצרה

• מרחיבים את אוסף השפות שאנחנו יודעים שהן ב-NP בשתי בעיות גרפים: CLIQUE (קיימת קליקה בגודל $K$?) ו-IS = Independent Set (קיימת קבוצה בלתי תלויה בגודל $K$?). כל אחת מוכחת בדרך אחרת — האחת דרך מכונה אי-דטרמיניסטית, השנייה דרך verifier — כך שנראה את שתי ההגדרות השקולות של NP בפעולה.
• מוכיחים שמותר מכאן ואילך לכתוב פסאודו-קוד במקום מכונת טיורינג: זמן על מכונת טיורינג שקול פולינומית לזמן על מכונת RAM, והרזולוציה שמעניינת אותנו ("פולינומי / לא פולינומי") גסה מספיק כדי לא להבחין בהפרש.
• מגדירים את הכלי המרכזי של כל שארית הקורס: רדוקציה בזמן פולינומי $A \le_p B$. הכיוון קריטי — $A \le_p B$ אומר ש-$B$ היא לפחות קשה כמו $A$, כי אלגוריתם ל-$B$ פותר גם את $A$.
• מוכיחים $\mathrm{IS} \le_p \mathrm{CLIQUE}$ (ובאותה רדוקציה גם $\mathrm{CLIQUE} \le_p \mathrm{IS}$) על ידי מעבר לגרף המשלים, כולל הנימוק למה ניסיונות נאיביים יותר — למחוק את כל הקשתות או להוסיף את כל הקשתות — נכשלים.
• מגדירים NP-קשה ("כל שפה ב-NP נרדקת אליי") ו-NP-שלמה ("NP-קשה וגם שייכת ל-NP"). זהו בדיוק ההבדל בין שני המושגים, והוא נבדק במבחנים.
• מוכיחים את משפט ההעברה: אם $A$ היא NP-קשה ו-$A \le_p B$ אז גם $B$ היא NP-קשה. זהו המשפט שהופך את החיים לאפשריים — בלעדיו כל הוכחת NP-קושי הייתה מחייבת לטפל בכל שפה ב-NP מחדש.

רקע ותלויות

השיעור הזה יושב כולו על ההגדרות שנבנו בשיעורים 4–6, ומשתמש בהן בלי לחזור עליהן. לכן נציג אותן כאן במלואן.

מחלקות הזמן (ראו שיעור 4). לכל פונקציה $f$, המחלקה $\mathrm{DTime}(f(n))$ היא אוסף השפות שניתן להכריע במכונת טיורינג דטרמיניסטית בזמן $O(f(n))$, ומכאן $P=\bigcup_{c\in\mathbb{N}}\mathrm{DTime}(n^c).$

NP — ההגדרה הבסיסית (ראו שיעור 6). באופן מקביל, $\mathrm{NTime}(f(n))$ היא אוסף השפות שמכונה אי-דטרמיניסטית מכריעה בזמן $O(f(n))$, ו- $\mathrm{NP}=\bigcup_{c\in\mathbb{N}}\mathrm{NTime}(n^c).$ "מכריעה" עבור מכונה אי-דטרמיניסטית $M$ פירושו: $x\in L$ אם ורק אם קיימת ריצה של $M$ על $x$ שמקבלת; אם $x\notin L$ אז כל הריצות דוחות; וכל ריצה אפשרית עוצרת, ובזמן פולינומי באורך הקלט.

NP — ההגדרה השקולה עם verifier (ראו שיעור 6). $A\in \mathrm{NP}$ אם ורק אם קיימת מכונת טיורינג דטרמיניסטית $M$ שרצה בזמן פולינומי, וקיים פולינום $p$, כך שלכל $x$: $x\in A \iff \exists\, w\in\{0,1\}^{\le p(|x|)}\ \text{s.t. } M \text{ accepts } \langle x,w\rangle .$ המכונה $M$ נקראת מוודא בזמן פולינומי (polynomial-time verifier) עבור $A$. שימו לב לניסוח המדויק: $M$ אינה מכריעה את $A$ — היא מכריעה שפה של זוגות. שני התנאים שהיא צריכה לקיים הם "לקלטים בקבוצה יש עדות קצרה שמשכנעת אותה" ו"קלטים שאינם בקבוצה — אי אפשר לרמות אותה עליהם". שתי ההגדרות הוכחו שקולות בשיעור 6.

רדוקציות מחישוביות. בחישוביות אמרנו ש-$A$ נרדקת ל-$B$ אם קיימת פונקציה $f$ חשיבה־מלאה כך ש-$x\in A \iff f(x)\in B$; שקול לכך, קיימת מכונת טיורינג $M$ שעוצרת על כל קלט ומקיימת את התכונה הזו. גם ראינו שם ש-$R$ ו-$\mathrm{RE}$ סגורות כלפי מטה תחת רדוקציות, ושהיחס טרנזיטיבי (ההוכחה: שרשור מכונות / הרכבת פונקציות). כל מה שנעשה כאן הוא להוסיף לדרישה הסמנטית הזו דרישת יעילות.

מודל החישוב — למה מותר לעבור לפסאודו-קוד. ניתן להוכיח כי הזמן על מכונת טיורינג שקול פולינומית לזמן על מכונת RAM (Random Access Memory) — המודל שבו מותר לגשת ישירות לתא בזיכרון בלי לצעוד אליו, כלומר בדיוק המודל שבו נכתב פסאודו-קוד בקורסי מבני נתונים ואלגוריתמים. בחישוביות עניינה אותנו שקילות סמנטית ("מה אפשר לחשב"); בסיבוכיות אנחנו מוסיפים על הסמנטיקה גם את היעילות, ואומרים שהמודלים שקולים עד כדי פולינום. מכאן:

כל עוד הרזולוציה שמעניינת אותנו היא "האם הסיבוכיות היא $n^c$ עבור $c$ כלשהו", כלומר "פולינומי או לא פולינומי", אפשר לעבוד בפסאודו-קוד.

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

מוסכמה על גרפים. מכאן ואילך "גרף" פירושו תמיד גרף פשוט ולא מכוון, אלא אם נאמר אחרת. גרף נכתב $G=(V,E)$, וקשת בין $x$ ל-$y$ נסמן $xy$. כשמדובר בקלט לבעיית הכרעה, $G$ הוא כמובן קידוד של הגרף; לא נעסוק בקידוד עצמו, רק נדרוש שיהיה סביר (כלומר שהגודל שלו יהיה פולינומי במספר הקדקודים והקשתות).

הגדרות

הגדרה 1: קליקה

יהי $G=(V,E)$ גרף. קבוצה $U\subseteq V$ נקראת קליקה (clique) כאשר לכל $x,y\in U$ שונים מתקיים $xy\in E$.

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

מופע. בגרף $P_5$ עם $V=\{a,b,c,d,e\}$ ו-$E=\{ab,bc,cd,de\}$, הקבוצה $\{a,b\}$ היא קליקה (בגודל 2), וכך גם כל קשת בודדת. הקבוצה $\{a\}$ היא קליקה טריוויאלית, וגם $\varnothing$.

אי-מופע. באותו גרף, $\{a,b,c\}$ אינה קליקה: $ac\notin E$. שימו לב שדי בזוג אחד חסר כדי להרוס את התכונה.

הגדרה 2: השפה CLIQUE

$\mathrm{CLIQUE}=\Big\{\langle G,K\rangle \ \Big|\ G=(V,E)\text{ graph},\ K\in\mathbb{N},\ \exists\, U\subseteq V:\ |U|=K \text{ and } U \text{ is a clique in } G\Big\}.$

כלומר, הקלט הוא זוג $\langle G,K\rangle$ ואנחנו צריכים להכריע האם בגרף $G$ קיימת קליקה בגודל $K$.

מופע. בגרף שהודגם בשיעור — משולש שאליו מחוברים עוד קדקודים — הזוג $\langle G,3\rangle$ שייך ל-CLIQUE, כי שלושת קדקודי המשולש הם קליקה בגודל 3.

אי-מופע. עבור אותו גרף בדיוק, $\langle G,4\rangle\notin \mathrm{CLIQUE}$: כל ארבעה קדקודים שנבחר — יימצאו בהם שניים שאין ביניהם קשת.

הגדרה 3: קבוצה בלתי תלויה

יהי $G=(V,E)$ גרף ותהי $U\subseteq V$. הקבוצה $U$ נקראת בלתי תלויה (independent set) כאשר לכל $x,y\in U$ שונים מתקיים $xy\notin E$.

אינטואיציה. זו קבוצת קדקודים שאין ביניהם אף קשת. חשבו על קבוצת משימות שאף שתיים מהן אינן מתנגשות.

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

מופע. ב-$P_5$ שלמעלה, $\{a,c,e\}$ בלתי תלויה: $ac,ae,ce\notin E$.

אי-מופע. $\{a,b\}$ אינה בלתי תלויה, כי $ab\in E$.

הגדרה 4: השפה IS

$\mathrm{IS}=\Big\{\langle G,K\rangle \ \Big|\ G=(V,E)\text{ graph},\ K\in\mathbb{N},\ \exists\, U\subseteq V:\ |U|=K \text{ and } U \text{ is independent in } G\Big\}.$

השפה מזכירה מאוד את CLIQUE — רק שבמקום "יש קשת" נדרש "אין קשת".

הגדרה 5: רדוקציה בזמן פולינומי

תהיינה $A,B$ שפות. רדוקציה בזמן פולינומי מ-$A$ ל-$B$ היא מכונת טיורינג (דטרמיניסטית, חד-סרטית סטנדרטית) $M$ המקיימת:

1. $M$ רצה בזמן פולינומי בגודל הקלט;
2. לכל קלט $x$:
   • אם $x\in A$ אז $M(x)\in B$, וגם
   • אם $x\notin A$ אז $M(x)\notin B$.

אם קיימת רדוקציה כזו נסמן $A \le_p B$.

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

אם $A\le_p B$, אז $A$ "אינה קשה מ-" $B$ עד כדי פולינום.

כלומר $B$ היא הבעיה הקשה יותר, ולא להפך. הסימון $\le$ נבחר בדיוק כדי לקודד את זה, וה-$p$ הקטנה מציינת שההמרה עצמה חסומה בפולינום. זו נקודת הכשל הנפוצה ביותר בשיעור הזה ובכל מה שבא אחריו.

מה רדוקציה איננה. רדוקציה אינה פותרת אף אחת מהבעיות. בזמן בניית הרדוקציה איני יודע — ואיני יכול לדעת בזמן פולינומי — האם הקלט שקיבלתי שייך ל-$A$ או לא. ההמרה חייבת לעבוד "בעיוורון". רק בשלב ההוכחה, שהוא לא-אלגוריתמי, אני מרשה לעצמי להניח "נניח $x\in A$, אז קיימת...".

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

הגדרה 6: NP-קשה

תהי $A$ שפה. $A$ נקראת NP-קשה (NP-hard) כאשר לכל שפה $B\in \mathrm{NP}$ מתקיים $B\le_p A$.

אינטואיציה. $A$ קשה לפחות כמו כל בעיה ב-NP: לו ידענו לפתור את $A$ בזמן פולינומי, היינו יודעים לפתור בזמן פולינומי כל בעיה ב-NP, ומקבלים $P=\mathrm{NP}$. שימו לב לכיוון: הרדוקציות מגיעות מכל שפה ב-NP אל $A$.

הערה על ההגדרה. $A$ עצמה אינה נדרשת להיות ב-NP. שפה NP-קשה יכולה להיות קשה הרבה יותר — למשל בלתי כריעה לחלוטין.

הגדרה 7: NP-שלמה

תהי $A$ שפה. $A$ נקראת NP-שלמה (NP-complete) כאשר:

1. $A$ היא NP-קשה, וגם
2. $A\in \mathrm{NP}$.

ההבדל בין השתיים בשורה אחת. NP-קשה = "לפחות קשה כמו כל דבר ב-NP". NP-שלמה = NP-קשה ובנוסף שייכת בעצמה ל-NP, כלומר היא הבעיה הקשה ביותר בתוך NP. תנאי (2) הוא שהופך את $A$ לנציגה של המחלקה ולא רק לחסם עליון עליה.

הערה: מי שלמד חישוביות בקורס שבו לא ניתן שם למושג "$\mathrm{RE}$-קושי" — למד בדיוק את התכונה הזו, פשוט בלי לתת לה שם: במקום להגדיר "$\mathrm{RE}$-קשה" בנפרד, נכתב תנאי הרדוקציה ישירות בתוך הגדרת ה-$\mathrm{RE}$-שלמות. אין כאן שום הבדל מהותי, רק פירוק ההגדרה לשני מרכיבים.

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

משפט 1: $\mathrm{CLIQUE}\in \mathrm{NP}$

ההוכחה מתבצעת לפי ההגדרה הבסיסית של NP, באמצעות מכונה אי-דטרמיניסטית. כפי שהוסבר ברקע, מותר לנו לתאר אלגוריתם ולא מכונה.

האלגוריתם. על קלט $\langle G,K\rangle$, כאשר $G=(V,E)$ גרף ו-$K\in\mathbb{N}$:

1. באופן אי-דטרמיניסטי בחר קבוצה $U\subseteq V$ כך ש-$|U|=K$.
2. לכל $x,y\in U$ שונים: אם $xy\notin E$ — דחה.
3. קבל.

שימו לב שרק שלב 1 אי-דטרמיניסטי; שלבים 2–3 הם לולאה דטרמיניסטית לגמרי. מכונה אי-דטרמיניסטית רשאית להכיל חלקים דטרמיניסטיים, וגם רשאית לפזר את הבחירות האי-דטרמיניסטיות שלה לאורך הריצה ולא לרכז את כולן בהתחלה.

נכונות — כיוון ראשון. יהי $G=(V,E)$ גרף ויהי $K\in\mathbb{N}$. נניח $\langle G,K\rangle\in \mathrm{CLIQUE}$. אזי, לפי ההגדרה, קיימת $U\subseteq V$ כך ש-$|U|=K$ וגם $U$ קליקה ב-$G$. חשוב לתת שם לאובייקט הזה כדי שנוכל להתייחס אליו בהמשך. כעת, קיימת עבור האלגוריתם ריצה אפשרית שבה הוא בוחר בשלב 1 בדיוק את $U$. בריצה זו, לכל $x,y\in U$ שונים מתקיים $xy\in E$ (כי $U$ קליקה), ולכן התנאי בשלב 2 לעולם אינו מתקיים, האלגוריתם אינו דוחה, ומגיע לשלב 3 ומקבל. לכן קיימת ריצה מקבלת.

נכונות — כיוון שני. נניח $\langle G,K\rangle\notin \mathrm{CLIQUE}$. את המשמעות של זה יש לנסח על הזוג לפני שמדברים על האלגוריתם: $\forall\, U\subseteq V:\quad |U|=K \ \Longrightarrow\ U \text{ is not a clique in } G .$ כעת: בכל ריצה אפשרית של האלגוריתם הוא בוחר בשלב 1 קבוצה $U\subseteq V$ בגודל $K$; לפי הנוסח שלמעלה $U$ אינה קליקה ב-$G$, כלומר קיימים $x,y\in U$ שונים עם $xy\notin E$; כשהלולאה בשלב 2 תגיע לזוג הזה היא תדחה. לכן כל ריצה אפשרית דוחה.

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

ניתוח זמן ריצה. על קלט $\langle G,K\rangle$:

• בחירת $U$ דורשת $O(|V|)$ צעדים: במקרה הגרוע צריך לעבור על כל קדקוד ולהחליט אם הוא בקבוצה או לא.
• הלולאה בשלב 2 עוברת על כל הזוגות מתוך $U$, כלומר $\binom{K}{2}=O(K^2)$ זוגות.
• בלי הגבלת הכלליות $K\le |V|$: אם $K>|V|$ אפשר לדחות מיד (אין $|V|+1$ קדקודים). לכן $O(K^2)\subseteq O(|V|^2)$.

סך הכול $O\!\left(|\langle G,K\rangle|^2\right)$, ובפרט פולינומי בגודל הקלט. לכן $\mathrm{CLIQUE}\in \mathrm{NP}$. $\blacksquare$

הערה על החסם $K\le|V|$ — נקודה עדינה שעלתה בשתי המסירות. המספר $K$ מקודד בבינארית ותופס $\Theta(\log K)$ ביטים. לכן אלגוריתם שעושה $K$ צעדים עושה מספר צעדים מעריכי בגודל הקידוד של $K$! אם $K$ היה מגיע לבדו כקלט, שום דבר כאן לא היה פולינומי. מה שמציל אותנו הוא שלצד $K$ מגיע גם הגרף: אחרי הצמצום $K\le|V|$, כל חסם ב-$K$ הופך לחסם ב-$|V|$, ו-$|V|$ הוא כן לינארי בגודל הקידוד של הקלט. במילים אחרות — "הגרף משלם את המחיר של $K$". בכל ניתוח זמן ריצה של בעיות מהסוג הזה חייבים לבטא את הכול כפונקציה של גודל הקלט, ולא של הפרמטרים המספריים שבתוכו.

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

משפט 2: $\mathrm{IS}\in \mathrm{NP}$

הפעם נוכיח דרך ההגדרה השקולה, עם verifier. אפשר היה כמובן להעתיק את הוכחת משפט 1 ולהחליף בשלב 2 את התנאי $xy\notin E$ ב-$xy\in E$; אנחנו בוחרים בדרך השנייה כדי לתרגל את שתי ההגדרות.

המוודא. על קלט $\langle G,K\rangle$ עם $G=(V,E)$ גרף, $K\in\mathbb{N}$, ועדות $U\subseteq V$:

1. ודא ש-$|U|=K$ (אחרת דחה).
2. לכל $x,y\in U$ שונים: אם $xy\in E$ — דחה.
3. קבל.

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

נכונות. נראה שלכל גרף $G=(V,E)$ ולכל $K\in\mathbb{N}$: $\langle G,K\rangle\in \mathrm{IS} \iff \exists\, w \text{ of size polynomial in } |\langle G,K\rangle| \text{ s.t. the algorithm accepts } \langle G,K\rangle, w .$

($\Rightarrow$) נניח $\langle G,K\rangle\in \mathrm{IS}$. אזי קיימת $U\subseteq V$ כך ש-$|U|=K$ ו-$U$ בלתי תלויה ב-$G$. את $U$ ניתן לקודד במחרוזת של $|V|$ ביטים — ביט לכל קדקוד, "בפנים / בחוץ" — וזה פולינומי (ואף לינארי) בגודל הקלט. על העדות הזו האלגוריתם עובר את שלב 1 (הגודל נכון), ואינו דוחה בשלב 2 (כי לכל שני קדקודים שונים ב-$U$ אין קשת), ולכן מקבל.

($\Leftarrow$) נראה את הניגוד: נניח $\langle G,K\rangle\notin \mathrm{IS}$. אז לכל $U\subseteq V$, אם $|U|=K$ אז $U$ אינה בלתי תלויה ב-$G$, כלומר קיימים בה $x,y$ שונים עם $xy\in E$, והאלגוריתם דוחה בשלב 2. ואם $|U|\ne K$ האלגוריתם דוחה כבר בשלב 1. לכן לכל עדות $w$ כלשהי האלגוריתם דוחה, ובפרט אין עדות מקבלת.

הערה — למה בכלל טרחנו לומר "פולינומי בגודל הקלט" על העדות? זו לא פדנטיות. תנאי אורך העדות הוא חלק בלתי נפרד מהגדרת ה-verifier, והוא מה שמונע רמאות. דוגמה נגדית שניתנה בשיעור: אפשר לבנות "מוודא" ל-SAT שמקבל נוסחה יחד עם טבלת האמת המלאה שלה, ופשוט קורא את התשובה מהטבלה. המוודא הזה אכן מוודא נכון — אבל טבלת האמת היא מעריכית בגודל הנוסחה, ולכן הבנייה חסרת ערך ואינה מוכיחה $\mathrm{SAT}\in \mathrm{NP}$. הדרישה "עדות באורך $p(|x|)$" היא בדיוק מה שפוסל אותה. אצלנו העדות היא $|V|$ ביטים בלבד — לינארי — ולכן הכול תקין.

ניתוח זמן ריצה. על קלט $\langle\langle G,K\rangle, U\rangle$:

• הבדיקה $|U|=K$ דורשת $O(|V|)$ צעדים (פשוט ספירת האיברים).
• הלולאה דורשת $O(K^2)\subseteq O(|V|^2)$ צעדים, שוב לפי $K\le|V|$.

סך הכול $O\!\left(\big|\langle\langle G,K\rangle,U\rangle\big|^2\right)$ — פולינומי. לכן $\mathrm{IS}\in \mathrm{NP}$. $\blacksquare$

משפט 3: $\mathrm{IS} \le_p \mathrm{CLIQUE}$

כיוון הטענה. אנחנו טוענים שאלגוריתם ל-CLIQUE פותר גם את IS. איננו טוענים דבר על הקושי של אף אחת מהן בפני עצמה, ואיננו מכריעים כאן אף אחת מהן.

איך מגיעים לרדוקציה — הניסיונות שנכשלו. הקלט של IS הוא זוג $\langle G,K\rangle$, והפלט צריך להיות גם הוא זוג "גרף ומספר", כי זה הפורמט של קלטי CLIQUE. השאלה היא איזה גרף.

• הצעה ראשונה בכיתה: "נמחק את קשתות הקליקה". נפסלה מיד — אני לא יודע למצוא קליקה. כל העניין הוא שאיני יודע לפתור את הבעיה; אם הייתי יודע, לא הייתי צריך רדוקציה. (אותה מלכודת הופיעה בחישוביות: ברדוקציה מ-$\mathrm{HALT}$ ל-$\mathrm{HALT}_0$ לא יכולנו לבדוק אם הקלט ב-$\mathrm{HALT}$; היינו צריכים להעביר את התכונה בלי לדעת.)
• הצעה שנייה: "נמחק את כל הקשתות מהגרף". אז הפלט לעולם אינו ב-CLIQUE (עבור $K\ge 2$) — לא משנה מה היה הקלט. זה הורס את כיוון ה"אם".
• ההצעה המשלימה: "נוסיף את כל הקשתות". אז הפלט תמיד ב-CLIQUE, ללא קשר לקלט. זה הורס את הכיוון השני.

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

הרדוקציה. על קלט $\langle G,K\rangle$ כאשר $G=(V,E)$ גרף ו-$K\in\mathbb{N}$:

1. בנה את הגרף המשלים $\bar G=(V,\bar E)$ של $G$, כאשר $\bar E=\Big\{xy \ \Big|\ x,y\in V,\ x\ne y\Big\}\setminus E = \binom{V}{2}\setminus E .$
2. החזר $\langle \bar G, K\rangle$.

$K$ נשאר ללא שינוי.

ניתוח זמן ריצה. על קלט $\langle G,K\rangle$: בניית הגרף המשלים דורשת $O(|V|^2)$ צעדים — עוברים על כל זוג קדקודים (יש $\binom{|V|}{2}$ כאלה), בודקים אם הקשת קיימת ומכניסים ל-$\bar E$ בהתאם. סך הכול $O\!\left(|\langle G,K\rangle|^2\right)$, ובפרט פולינומי. (בהחלט לא ניסינו להיות יעילים; לצורך הרדוקציה מספיק "פולינומי".)

נכונות — כיוון ראשון: $\langle G,K\rangle\in \mathrm{IS} \Rightarrow \langle\bar G,K\rangle\in \mathrm{CLIQUE}$.

יהי $G=(V,E)$ גרף ויהי $K\in\mathbb{N}$. נניח $\langle G,K\rangle\in \mathrm{IS}$. אזי קיימת $U\subseteq V$ כך ש-$|U|=K$ וגם $U$ בלתי תלויה ב-$G$.

נתבונן באותה $U$ בתוך $\bar G$ (מותר — לשני הגרפים אותה קבוצת קדקודים $V$). אז $U\subseteq V$ וגם $|U|=K$. נותר להראות ש-$U$ קליקה ב-$\bar G$. יהיו $x,y\in U$ שונים. מכיוון ש-$U$ בלתי תלויה ב-$G$, מתקיים $xy\notin E$. לפי הגדרת המשלים, כל זוג קדקודים שונים שאינו קשת ב-$E$ הוא קשת ב-$\bar E$; לכן $xy\in\bar E$. מכאן ש-$U$ קליקה ב-$\bar G$, ולכן $\langle\bar G,K\rangle\in \mathrm{CLIQUE}$.

נכונות — כיוון שני: $\langle\bar G,K\rangle\in \mathrm{CLIQUE} \Rightarrow \langle G,K\rangle\in \mathrm{IS}$.

נניח $\langle\bar G,K\rangle\in \mathrm{CLIQUE}$. אזי קיימת $U\subseteq V$ כך ש-$|U|=K$ וגם $U$ קליקה ב-$\bar G$ (שימו לב: חייבים לומר "ב-$\bar G$" ולא סתם "קליקה" — יש כאן שני גרפים).

נתבונן באותה $U$ בתוך $G$. אז $U\subseteq V$ וגם $|U|=K$. יהיו $x,y\in U$ שונים. מכיוון ש-$U$ קליקה ב-$\bar G$ מתקיים $xy\in\bar E$, ולפי הגדרת המשלים $xy\notin E$. מכאן ש-$U$ בלתי תלויה ב-$G$, ולכן $\langle G,K\rangle\in \mathrm{IS}$.

סיכום. האלגוריתם רץ בזמן פולינומי ומקיים $x\in \mathrm{IS} \iff M(x)\in \mathrm{CLIQUE}$, ולכן הוא רדוקציה בזמן פולינומי, כלומר $\mathrm{IS}\le_p \mathrm{CLIQUE}$. $\blacksquare$

הערה על מבנה ההוכחה. ההגדרה של רדוקציה דורשת שני תנאים ($x\in A\Rightarrow M(x)\in B$ ו-$x\notin A\Rightarrow M(x)\notin B$). מותר, ולרוב נוח יותר, להוכיח במקום התנאי השני את הניגוד שלו: $M(x)\in B\Rightarrow x\in A$. זה מה שעשינו. שני הניסוחים שקולים. תמיד לעבוד עם השלד של ההגדרה — "מה הנחתי, מה אני צריך להוכיח" — לפני שמפרקים את ההגדרות; השלד הוא המעקה ששומר על ההוכחה.

משפט 4: $\mathrm{CLIQUE} \le_p \mathrm{IS}$

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

הרדוקציה. על קלט $\langle H,K\rangle$ עם $H=(V,F)$ גרף: החזר $\langle \bar H, K\rangle$.

זמן ריצה. זהה: $O(|V|^2)\subseteq O(|\langle H,K\rangle|^2)$.

נכונות. המפתח הוא שהמשלים הוא אינוולוציה: $\overline{\bar H}=H$, כי $\binom{V}{2}\setminus\left(\binom{V}{2}\setminus F\right)=F$.

($\Rightarrow$) נניח $\langle H,K\rangle\in \mathrm{CLIQUE}$, כלומר קיימת $U\subseteq V$ בגודל $K$ שהיא קליקה ב-$H$. יהיו $x,y\in U$ שונים; אז $xy\in F$, ולכן $xy\notin\bar F$, כלומר $U$ בלתי תלויה ב-$\bar H$. לכן $\langle\bar H,K\rangle\in \mathrm{IS}$.

($\Leftarrow$) נניח $\langle\bar H,K\rangle\in \mathrm{IS}$, כלומר קיימת $U\subseteq V$ בגודל $K$ בלתי תלויה ב-$\bar H$. יהיו $x,y\in U$ שונים; אז $xy\notin\bar F$, ולכן $xy\in F$, כלומר $U$ קליקה ב-$H$. לכן $\langle H,K\rangle\in \mathrm{CLIQUE}$. $\blacksquare$

הערה: בהרצאה זה נאמר בקיצור — "באופן דומה אפשר להראות רדוקציה בכיוון ההפוך; למעשה אותה רדוקציה עצמה" — והפירוט כאן. המסקנה: שתי הבעיות שקולות תחת $\le_p$. אחת מהן ב-$P$ אם ורק אם השנייה ב-$P$; אחת מהן NP-שלמה אם ורק אם השנייה NP-שלמה.

משפט 5: טרנזיטיביות של $\le_p$

טענה. לכל שלוש שפות $A,B,C$: אם $A\le_p B$ וגם $B\le_p C$ אז $A\le_p C$.

הוכחה. תהיינה $M_1$ רדוקציה בזמן פולינומי מ-$A$ ל-$B$ ו-$M_2$ רדוקציה בזמן פולינומי מ-$B$ ל-$C$. יהיו $p_1,p_2$ פולינומים החוסמים את זמני הריצה שלהן בהתאמה; בלי הגבלת הכלליות שניהם מונוטוניים עולים. נגדיר את $M$ כשרשור: על קלט $x$, הרץ $M_1$ על $x$, קבל $y=M_1(x)$, הרץ $M_2$ על $y$ והחזר $M_2(y)$. (במונחי פונקציות: הרכבה, $f=f_2\circ f_1$.)

סמנטיקה. לכל $x$: $x\in A \iff M_1(x)\in B \iff M_2(M_1(x))\in C$, כאשר השקילות הראשונה היא נכונות $M_1$ והשנייה נכונות $M_2$ (מופעלת על הקלט $M_1(x)$). לכן $x\in A \iff M(x)\in C$.

זמן ריצה — כאן נמצא כל החידוש לעומת חישוביות. השלב הראשון עולה $p_1(|x|)$. השלב השני עולה $p_2(|y|)$, ולכן צריך לחסום את $|y|$. מכונה שרצה $t$ צעדים אינה יכולה לכתוב יותר מ-$t$ תווים, ולכן $|y|=|M_1(x)|\le p_1(|x|)$ (עד כדי תוספת $|x|$, אם נספור גם את הקלט ההתחלתי — עדיין פולינומי). מכאן שסך זמן הריצה חסום על ידי $p_1(|x|)+p_2\big(p_1(|x|)\big),$ וזהו פולינום ב-$|x|$, כי הרכבה של פולינומים היא פולינום וסכום של פולינומים הוא פולינום. לכן $M$ היא רדוקציה בזמן פולינומי מ-$A$ ל-$C$. $\blacksquare$

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

משפט 6: סגירות כלפי מטה תחת $\le_p$

טענה. המחלקות $P$, $\mathrm{NP}$ ו-$\mathrm{PSPACE}$ סגורות כלפי מטה תחת רדוקציות בזמן פולינומי. במפורש, עבור $P$: $\forall A,B:\quad A\in P \ \text{and}\ B\le_p A \ \Longrightarrow\ B\in P .$ ובאותו אופן עבור $\mathrm{NP}$ ועבור $\mathrm{PSPACE}$.

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

הוכחה עבור $P$. נניח $A\in P$ ו-$B\le_p A$. תהי $M_A$ מכונה דטרמיניסטית המכריעה את $A$ בזמן $q(n)$ פולינומי, ותהי $R$ רדוקציה מ-$B$ ל-$A$ בזמן $p(n)$ פולינומי. נגדיר מכונה $M_B$: על קלט $x$, חשב $y=R(x)$, ואז הרץ את $M_A$ על $y$ והחזר את תשובתה.

נכונות. $x\in B \iff R(x)\in A \iff M_A$ מקבלת את $R(x)$ $\iff M_B$ מקבלת את $x$.

זמן ריצה. $|y|\le p(|x|)$ (מכונה שרצה $p(|x|)$ צעדים אינה יכולה לכתוב פלט ארוך יותר), ולכן הזמן הכולל חסום על ידי $p(|x|)+q\big(p(|x|)\big)$ — פולינום. לכן $B\in P$.

עבור $\mathrm{NP}$ ההוכחה זהה מילה במילה, למעט ש-$M_A$ היא מכונה אי-דטרמיניסטית פולינומית; $M_B$ יורשת ממנה את האי-דטרמיניזם, וכל ריצה שלה נמשכת $p(|x|)+q(p(|x|))$ צעדים לכל היותר. $x\in B$ אם ורק אם $R(x)\in A$ אם ורק אם קיימת ריצה מקבלת של $M_A$ על $R(x)$ אם ורק אם קיימת ריצה מקבלת של $M_B$ על $x$.

עבור $\mathrm{PSPACE}$ אותו שרשור, אלא שכעת סופרים מקום: הרדוקציה רצה בזמן פולינומי ולכן צורכת גם מקום פולינומי ומייצרת פלט באורך פולינומי, ו-$M_A$ צורכת מקום פולינומי באורך הפלט הזה — כלומר פולינומי ב-$|x|$. $\blacksquare$

הערה: גם משפט זה הוכרז בהרצאה כדחוי לשיעור הבא, והסיכום מציין אותו כטענה "ללא הוכחה" ומפנה לתרגיל. הרעיון המרכזי שנאמר בעל פה — "הרכבה של פולינומים היא פולינום" — הוא בדיוק מה שכתוב כאן במלואו. הרשימה $\{P, \mathrm{NP}, \mathrm{PSPACE}\}$ אינה ממצה; אלו המחלקות שיעניינו אותנו.

משפט 7: משפט ההעברה של NP-קושי

טענה. תהיינה $A,B$ שפות. אם $A$ היא NP-קשה וגם $A\le_p B$, אז $B$ היא NP-קשה.

הוכחה. נניח ש-$A$ היא NP-קשה וגם $A\le_p B$. לפי הגדרה 6, כדי להוכיח ש-$B$ היא NP-קשה עלינו להראות שלכל $C\in \mathrm{NP}$ מתקיים $C\le_p B$.

תהי $C\in \mathrm{NP}$ (חייבים לתת לה שם, כדי שנוכל להתייחס אליה בהמשך).

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

מאחר ש-$C\in \mathrm{NP}$ הייתה שרירותית, הראינו שלכל שפה ב-NP קיימת רדוקציה בזמן פולינומי ממנה אל $B$. זו בדיוק הגדרה 6, ולכן $B$ היא NP-קשה. $\blacksquare$

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

זו בדיוק התוכנית להמשך: בשיעור הבא נוכיח את משפט Cook–Levin, שאומר ש-$\mathrm{SAT}$ היא NP-קשה — זו ה"בעיה הראשונה" שנעבוד קשה כדי להשיג. משם והלאה נעשה רדוקציות מ-$\mathrm{SAT}$ אל בעיות נוספות, ומהן אל בעיות נוספות, וכל בעיה חדשה מצטרפת למאגר ומותר להשתמש גם בה כנקודת מוצא. כך "מעשירים את עולם הבעיות ה-NP-קשות".

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

דוגמה 1: הכרעה ידנית ב-CLIQUE

בשיעור הוצג גרף ונשאלו שתי שאלות עליו. נשחזר את הרעיון על גרף קונקרטי: $V=\{1,2,3,4,5\}$, $E=\{12,13,23,34,45\}$ — משולש על $\{1,2,3\}$, ואליו נגררת שרשרת $3-4-5$.

• $\langle G,3\rangle\in \mathrm{CLIQUE}$? כן. $U=\{1,2,3\}$: $12,13,23\in E$, ו-$|U|=3$.
• $\langle G,4\rangle\in \mathrm{CLIQUE}$? לא. יש רק 5 קדקודים, כלומר $\binom{5}{4}=5$ קבוצות אפשריות; בכל אחת מהן נמצא זוג לא-מחובר. למשל ב-$\{1,2,3,4\}$ חסרה $14$; ב-$\{1,2,3,5\}$ חסרה $15$; ב-$\{2,3,4,5\}$ חסרה $25$; ב-$\{1,3,4,5\}$ חסרה $14$; ב-$\{1,2,4,5\}$ חסרה $14$.

שימו לב שאותו גרף בדיוק נותן קלט חיובי ושלילי בהתאם ל-$K$ — $K$ הוא חלק מהקלט, וזה בדיוק מה שיהפוך את הניתוח לרגיש בהמשך.

דוגמה 2: מעקב מלא אחרי הרדוקציה, בשני הכיוונים

זהו התרגיל המרכזי. ניקח את המסלול $P_5$: $V=\{a,b,c,d,e\},\qquad E=\{ab,\ bc,\ cd,\ de\}.$

חישוב הגרף המשלים. כל הזוגות האפשריים הם $\binom{5}{2}=10$: $\binom{V}{2}=\{ab,ac,ad,ae,bc,bd,be,cd,ce,de\}.$ מחסרים את $E$ ומקבלים $\bar E=\{ac,\ ad,\ ae,\ bd,\ be,\ ce\}.$

כיוון $\mathrm{IS}\to \mathrm{CLIQUE}$. נבדוק את הקלט $\langle G,3\rangle$ עבור IS.

1. הקלט אכן ב-IS: הקבוצה $U=\{a,c,e\}$ מקיימת $|U|=3$, ו-$ac\notin E$, $ae\notin E$, $ce\notin E$. לכן $\langle G,3\rangle\in \mathrm{IS}$.
2. מפעילים את הרדוקציה: $f(\langle G,3\rangle)=\langle\bar G,3\rangle$ עם $\bar E$ שלמעלה. $K$ לא השתנה.
3. בודקים את הפלט: אותה $U=\{a,c,e\}$ — $ac\in\bar E$, $ae\in\bar E$, $ce\in\bar E$, ולכן $U$ קליקה ב-$\bar G$ ו-$\langle\bar G,3\rangle\in \mathrm{CLIQUE}$. ✓

כיוון $\mathrm{CLIQUE}\to \mathrm{IS}$ (הכיוון השני של אותה רדוקציה, ובו זמנית הדגמה של משפט 4). ניקח כעת את $\bar G$ כקלט ל-CLIQUE.

1. הקלט ב-CLIQUE: $\{a,c,e\}$ היא קליקה ב-$\bar G$ כפי שראינו. למעשה זו הקליקה היחידה בגודל 3 ב-$\bar G$: לזוג $\{a,d\}$ אין קדקוד שלישי משותף ($ac\in\bar E$ אבל $cd\notin\bar E$; $ae\in\bar E$ אבל $de\notin\bar E$; $ab\notin\bar E$), ולזוג $\{b,d\}$ חסר $de$.
2. מפעילים את הרדוקציה: $f(\langle\bar G,3\rangle)=\langle\overline{\bar G},3\rangle=\langle G,3\rangle$ — חוזרים בדיוק ל-$G$ המקורי, כי המשלים הוא אינוולוציה.
3. בודקים: $\{a,c,e\}$ בלתי תלויה ב-$G$. ✓

בדיקת קלט שלילי (חובה — אחרת לא הראינו "אם ורק אם"). ניקח $K=4$.

• $\langle G,4\rangle\notin \mathrm{IS}$: הקבוצה הבלתי תלויה המקסימלית ב-$P_5$ היא בגודל 3. כל קבוצה של 4 קדקודים מתוך 5 חייבת להכיל שני קדקודים סמוכים במסלול (למשל $\{a,b,c,d\}$ מכילה את $ab$; $\{a,c,d,e\}$ מכילה את $cd$; וכן הלאה).
• והפלט: $\langle\bar G,4\rangle\notin \mathrm{CLIQUE}$ — הקליקה המקסימלית ב-$\bar G$ היא בגודל 3, כפי שספרנו בשלב 1 למעלה.

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

תרגיל 3 (מהשיעור): למה האלגוריתם הנאיבי ל-CLIQUE אינו פולינומי?

השאלה. נניח שאני מכריע את CLIQUE דטרמיניסטית על ידי מעבר על כל תת-הקבוצות בגודל $K$. מה זמן הריצה, ולמה אין די בכך?

פתרון. מספר הקבוצות הוא $\binom{|V|}{K}$, ולכן זמן הריצה הוא $\Omega\!\left(\binom{|V|}{K}\right)$. נחסום מלמטה: $\binom{|V|}{K}=\frac{|V|(|V|-1)\cdots(|V|-K+1)}{K!}\ \ge\ \left(\frac{|V|}{K}\right)^{K},$ כי מדובר במכפלה של $K$ גורמים מהצורה $\frac{|V|-i}{K-i}$, וכל אחד מהם לפחות $\frac{|V|}{K}$.

למה זה לא פולינום? פולינום הוא "משתנה בחזקת קבוע". כאן המעריך הוא $K$ — ו-$K$ מגיע כחלק מהקלט, כלומר אינו קבוע. אין שום $c$ קבוע שעבורו הביטוי הזה חסום על ידי $|\langle G,K\rangle|^{c}$, כי החזקה עצמה גדלה עם הקלט.

הערה חשובה: מכאן לא נובע ש-$\mathrm{CLIQUE}\notin P$. נובע רק שהאלגוריתם הספציפי הזה אינו פולינומי. השאלה אם CLIQUE ב-$P$ פתוחה, ושקולה (כפי שיתברר) לשאלת $P$ מול $\mathrm{NP}$.

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

בשלב 1 של האלגוריתם במשפט 1 כתבנו "בחר באופן אי-דטרמיניסטי קבוצה $U$ בגודל $K$". איך זה נראה בפועל?

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

1. כתוב באופן אי-דטרמיניסטי $K$ מספרים, כל אחד בין $1$ ל-$|V|$, על הסרט השני.
2. התייחס אליהם כאל קדקודים ב-$G$.
3. אם קיים קדקוד שנבחר יותר מפעם אחת — דחה (הבחירה לא ייצרה קבוצה בגודל $K$).
4. אם קיימים שני קדקודים מבין הנבחרים שאין ביניהם קשת ב-$E$ — דחה.
5. אחרת — קבל.

ניתוח. שלב 1: כתיבת $K$ מספרים בין $1$ ל-$|V|$ עולה $O(K\cdot|V|)\subseteq O(|V|^2)$, שוב תוך שימוש ב-$K\le|V|$ — וכאן זה קריטי, כי אחרת מספר הצעדים היה מעריכי באורך הקידוד הבינארי של $K$. שלב 3: לכל אחד מ-$K$ המספרים סורקים את השאר, $O(K^2)\subseteq O(|V|^2)$. שלב 4: עוברים על כל זוג נבחרים ולכל זוג סורקים את רשימת הקשתות, $O(K^2\cdot|E|)$. סך הכול חסום ב-$O(|\langle G,K\rangle|^3)$ — לא הפולינום הטוב ביותר, אבל פולינום, וזה כל מה שנדרש.

בהמשך הקורס לא נרד לרמת פירוט זו; נכתוב "ננחש קבוצת קדקודים" ונמשיך. אבל כדאי שהמימוש יישאר ברקע כדי לדעת שהוא באמת אפשרי ויעיל.

תרגיל 5: ניתוח זמן ריצה חלופי לרדוקציה

בסיכום נכתב שבניית הגרף המשלים עולה $O(|V|^2)$; במסירה השנייה נאמר $O(|V|^2\cdot|E|)\subseteq O(|G|^3)$. מי צודק?

פתרון: שניהם, וההבדל הוא בייצוג. אם הגרף נתון במטריצת שכנויות, בדיקת "האם $xy\in E$" עולה $O(1)$, ולכן מעבר על כל $\binom{|V|}{2}$ הזוגות עולה $O(|V|^2)$. אם הגרף נתון ברשימת קשתות ואנחנו סורקים אותה עבור כל זוג, נשלם $O(|V|^2\cdot|E|)$. שניהם פולינומיים, ולכן לצורך הטענה $\mathrm{IS}\le_p \mathrm{CLIQUE}$ אין הבדל — וזו בדיוק הסיבה שמותר לנו להתרשל בפרטי המימוש. זהו יישום ישיר של "המסננת גסה מאוד".

תרגיל 6 (מהסיכום): הוכיחו את טענת הסגירות ואת הטרנזיטיביות

התרגיל מופיע בסיכום כשורה אחת; הפתרונות המלאים כתובים למעלה — משפט 5 (טרנזיטיביות) ומשפט 6 (סגירות). בשני המקרים הרעיון הסמנטי מועתק מהוכחות החישוביות המקבילות (שרשור מכונות / הרכבת פונקציות), והחלק החדש היחיד הוא ניתוח זמן הריצה, שנשען על שתי עובדות: (א) מכונה שרצה $t$ צעדים כותבת פלט באורך $O(t)$ לכל היותר, ולכן אורך הביניים חסום פולינומית; (ב) הרכבה של פולינומים היא פולינום. מומלץ לחזור על הוכחות אלו מקורס החישוביות לפני השיעור הבא.

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

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

• [00:16:00] הקידוד נעלם מהתמונה — בכוונה. מכאן ואילך נכתוב "קלט: זוג $\langle G,K\rangle$" בלי לפרט את הקידוד. עדיין מדובר בקידוד, ועדיין הוא חייב להיות סביר, אבל הוא לא מעניין אותנו יותר.

• [00:28:49] המלכודת של $K$. נשאלה שאלה מצוינת מהכיתה: הקלט מכיל גם את $K$, וכדי לקודד את $K$ צריך רק $\log_2 K$ ביטים — אז איך $O(K^2)$ נחשב פולינומי? התשובה: $K$ עצמו גדול מאוד ביחס לגודל הקידוד שלו, אבל בגלל שהגרף נמצא לידו בקלט, הגרף "משלם את המחיר". יחד עם ההנחה $K\le|V|$, הכול חוזר להיות פולינומי בגודל הקלט. אם $K$ היה מגיע לבדו — הניתוח היה קורס. שווה לזכור: כשמספר מופיע כפרמטר בקלט, תמיד לשאול אם החסם מבוטא ביחידות הנכונות.

• [00:31:27] → [00:46:25] חזרה מהצהרה. נשאל אם צריך להוכיח בנפרד שהאלגוריתם עוצר בכל ריצה. תחילה נאמר "אתה צודק ב-100%", ולאחר מכן המרצה חזר בו: "ברגע שזמן הריצה הוא פולינומי בכל ריצה, אני לא צריך את זה בנפרד." שתי התשובות אינן שגויות — הראשונה זהירה מדי. במבחן: אם ניתחתם זמן ריצה לכל ריצה אפשרית, אין צורך בטיעון עצירה נפרד.

• [00:33:34] "זה לא בדיוק ההפך מקליקה." אזהרה מפורשת נגד הטעות הנפוצה ביותר בהגדרות: השלילה של "לכל שניים יש קשת" היא "קיימים שניים שאין ביניהם קשת", ולא "לכל שניים אין קשת". שלילת כמת "לכל" אינה משאירה "לכל".

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

• [00:58:20] → [01:00:25] הדרך אל הגרף המשלים. ההצעות "נמחק את כל הקשתות" ו"נוסיף את כל הקשתות" נדחו לא כי הן טיפשות, אלא כי כל אחת מהן שוברת בדיוק כיוון אחד של ה"אם ורק אם". זו הדגמה מדויקת של מה שרדוקציה צריכה: לא פונקציה שמייצרת פלט "טוב", אלא פונקציה שמשמרת מבנה. שווה לחשוב על כך בכל פעם שנתקעים בבניית רדוקציה: איזה כיוון ההצעה שלי שוברת?

• [00:58:50] הקבלה לחישוביות. "כשעשינו רדוקציה מ-$\mathrm{HALT}$ ל-$\mathrm{HALT}_0$ לא יכולנו לבדוק אם הקלט ב-$\mathrm{HALT}$; היינו צריכים להעביר את התכונה בלי לדעת." אותה מחשבה בדיוק חלה כאן — הרדוקציה עיוורת לתשובה.

• [01:03:35] "פה הקבוצה לא נתונה לנו." בלבול שעלה בכיתה: בהוכחת הרדוקציה תלמידה חיפשה את הקבוצה $U$ כאילו היא חלק מהקלט, כמו ב-verifier של משפט 2. ההבהרה: בהוכחה מותר לומר "קיימת $U$" ולעבוד איתה — זו טענה מתמטית, לא שלב אלגוריתמי. ההבחנה בין "מה האלגוריתם עושה" ל"מה אני מוכיח" היא המקור השכיח ביותר לבלבול בשיעור הזה. במסירה השנייה [01:25:54] נאמר אותו דבר במפורש: "בזמן בניית הרדוקציה לא ידעתי אם זה שייך או לא שייך; בזמן ההוכחה אני מניח כיוון אחד ומראה את השני."

• [01:05:48] "תמיד לעבוד עם השלד של ההוכחה — זה המעקה ששומר עליכם." לפני שמפרקים הגדרות: מה הנחתי? מה בדיוק אני צריך להוכיח? רק אז לפתוח את ההגדרות. בהמשך אותה הוכחה נאמר לתלמידה שהתחילה מהפירוק: "זה כבר ה'איך אני מוכיח', לא 'מה אני רוצה להוכיח'."

• [01:07:24] כשיש שני גרפים — חובה לציין באיזה. לא "קליקה", אלא "קליקה ב-$\bar G$"; לא "קבוצת הקשתות", אלא "$\bar E$". בהוכחת רדוקציה בין בעיות גרפים זהו מקור קבוע לשגיאות.

• [01:22:29] ההבדל בין הקורסים. למי שלמד חישוביות במסלול שבו לא הוגדר "$\mathrm{RE}$-קשה": את התכונה למדתם, פשוט לא נתתם לה שם. אין הבדל מהותי.

• [01:26:48] למה בכלל צריך את משפט 7. להוכיח NP-קושי לפי ההגדרה מחייב לטפל בשפה שרירותית ב-NP — "אני לא יודע כלום על ה-$B$ הזאת" — ולכן זה מורכב. משפט 7 מאפשר לעשות את העבודה הקשה פעם אחת (Cook–Levin, שיעור הבא) ואז להתקדם ברדוקציות. "ברגע שיש לי עוד בעיה NP-קשה, אני יכול לעשות גם ממנה רדוקציה."

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

• מקור: עמוד 2 בסיכום. הפער: בהגדרת קבוצה בלתי תלויה נכתב ככל הנראה "לכל $x,y\in V$ שונים מתקיים $xy\notin E$", בעוד שההגדרה של קליקה בעמוד 1 משתמשת נכון ב-$x,y\in U$. הניסוח עם $V$ היה אומר שאין בגרף אף קשת כלל. ההכרעה: תוקן ל-$x,y\in U$ בהגדרה 3; זו ההגדרה שנאמרה בשתי ההקלטות. ייתכן גם שמדובר בשגיאת קריאה שלי בכתב היד — לכן נרשם ב-open_questions.

• מקור: הקלטה 13, [00:33:00]. הפער: התמלול האוטומטי מוריד את השלילה וכותב "$U$ תיקרא בלתי תלויה כאשר לכל $x,y\in U$ שונים הקשת $xy$ בגרף". ההכרעה: ארטיפקט תמלול. במשפט הבא המרצה עצמו אומר "פה אני דורש שלכל שניים אין קשת", והסיכום מסכים. נכתב $xy\notin E$.

• מקור: הסיכום מול הקלטה 13. הפער: הסיכום מציג את טענות הסגירות והטרנזיטיביות כ"טענה ללא הוכחה" ומוסיף "תרגיל: להוכיח"; בהקלטה נאמר שהן יוכחו בשיעור הבא, וניתן רק הרעיון המרכזי ("הרכבה של פולינומים היא פולינום"). ההכרעה: ההוכחות נכתבו כאן במלואן (משפטים 5 ו-6), עם סימון מפורש שבהרצאה הן נדחו.

• מקור: הקלטה 13, [01:15:16]. הפער: הכיוון $\mathrm{CLIQUE}\le_p \mathrm{IS}$ מוזכר במשפט אחד — "אותה רדוקציה למעשה היא רדוקציה גם בכיוון ההפוך" — ואינו מופיע כלל בסיכום. ההכרעה: נכתב כמשפט 4 עם הוכחה מלאה, כולל האינוולוציה $\overline{\bar H}=H$ שהמשפט נשען עליה; מסומן כשחזור.

• מקור: הסיכום (עמ' 4) מול הקלטה 14 ([01:19:52]). הפער: הסיכום מעריך את בניית הגרף המשלים ב-$O(|V|^2)$; המסירה השנייה מעריכה $O(|V|^2\cdot|E|)\subseteq O(|G|^3)$. ההכרעה: אין סתירה — ההבדל הוא בייצוג הגרף (מטריצת שכנויות מול רשימת קשתות). שני החסמים פולינומיים, ולכן שניהם מספיקים; שניהם מובאים, עם ההסבר, בתרגיל 5.

• מקור: הקלטה 14 בלבד ([00:44:46]–[00:49:07]). הפער: ניתוח החסם התחתון $\binom{|V|}{K}\ge(|V|/K)^K$ לאלגוריתם הנאיבי, וההסבר מדוע "משתנה בחזקת משתנה" אינו פולינום, אינם מופיעים בסיכום ולא במסירה השנייה. ההכרעה: נכללו כתרגיל 3, כולל האזהרה שמכאן לא נובע $\mathrm{CLIQUE}\notin P$.

• מקור: הקלטה 14 בלבד ([00:50:14]–[00:59:31]). הפער: המימוש המפורש של הבחירה האי-דטרמיניסטית (כתיבת $K$ מספרים ואז פסילת חזרות) והניתוח שלו אינם בסיכום. ההכרעה: נכללו כתרגיל 4.

• מקור: הקלטה 13 בלבד ([00:57:50]–[01:00:25], [00:28:49], [00:49:04]). הפער: הדיון בניסיונות הכושלים לבניית הרדוקציה, מלכודת הקידוד הבינארי של $K$, והדוגמה הנגדית של טבלת האמת כ-witness — כולם חסרים בסיכום ובמסירה השנייה. ההכרעה: נכללו, כי הם ההסבר למה עומד מאחורי ההגדרות, ולא רק להגדרות עצמן.

• מקור: הקלטה 14, [00:00:00]–[00:39:20]. הפער: כשליש מהקובץ עוסק בהגדרת SAT ובהוכחה ש-$\mathrm{SAT}\in \mathrm{NP}$ (בשתי הגרסאות), כולל דיון טכני באורך העדות ($n$ מול $p(|\varphi|)$). זהו חומר של שיעור 6. ההכרעה: לא נכלל כאן; רק ההערה הכללית על אורך העדות שימשה כדוגמה נגדית בהערה שאחרי משפט 2. סומן ב-coverage: partial.

• מקור: הגדרת הרדוקציה. הפער: הסיכום והקלטה 13 מגדירים רדוקציה כמכונה $M$; הקלטה 14 מגדירה אותה כפונקציה $f$ הניתנת לחישוב בזמן פולינומי. ההכרעה: ההגדרות שקולות (פונקציה חשיבה = קיימת מכונה שמחשבת אותה); הובאה גרסת הסיכום, עם ההסבר של המסירה השנייה מדוע לרוב נוח יותר להגדיר את הפונקציה ישירות דרך המכונה ולא בשני שלבים.

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

מה חייבים לדעת בעל פה

התוצאות

1. $\mathrm{CLIQUE}\in \mathrm{NP}$, $\mathrm{IS}\in \mathrm{NP}$.
2. $\mathrm{IS}\le_p \mathrm{CLIQUE}$ ו-$\mathrm{CLIQUE}\le_p \mathrm{IS}$, שתיהן על ידי $\langle G,K\rangle\mapsto\langle\bar G,K\rangle$.
3. $\le_p$ טרנזיטיבי.
4. $P$, $\mathrm{NP}$, $\mathrm{PSPACE}$ סגורות כלפי מטה תחת $\le_p$.
5. $A$ NP-קשה ו-$A\le_p B$ $\Rightarrow$ $B$ NP-קשה.

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

• הפיכת כיוון הרדוקציה. $A\le_p B$ אומר ש-$B$ קשה לפחות כמו $A$. הסגירות היא "$A\in P$ ו-$B\le_p A$ ⟹ $B\in P$" — הרדוקציה נכנסת אל הקלה. אם כתבתם את זה הפוך, קיבלתם $P=\mathrm{NP}$, וזה סימן אזהרה.
• NP-קשה ≠ NP-שלמה. שפה NP-קשה אינה חייבת להיות ב-NP, ואפילו לא כריעה. תמיד לבדוק את שני התנאים.
• "ההפך מקליקה". קבוצה בלתי תלויה אינה שלילת קליקה. הקשר הוא הגרף המשלים.
• רדוקציה שפותרת את הבעיה. אם בתיאור הרדוקציה שלכם מופיע "נמצא את הקליקה" או "נבדוק אם הקלט בשפה" — הרדוקציה לא חוקית. היא חייבת לפעול בלי לדעת את התשובה.
• הוכחת כיוון אחד בלבד. רדוקציה דורשת אם ורק אם. הוכחה שרק "כן ⟹ כן" חסרה חצי.
• חסמים בפרמטרים במקום בגודל הקלט. $O(K^2)$ אינו תשובה; צריך להסביר למה זה $O(|\langle G,K\rangle|^2)$, ולשם כך צריך את $K\le|V|$.
• witness ארוך מדי. אם העדות אינה חסומה פולינומית באורך הקלט, ההוכחה ש-$A\in \mathrm{NP}$ אינה תקפה.

צ'ק-ליסט: אחרי השיעור הזה סטודנט צריך לדעת

1. להוכיח שבעיית גרפים נתונה שייכת ל-NP, בשתי הדרכים (מכונה אי-דטרמיניסטית / verifier), כולל ניתוח זמן ריצה מלא כפונקציה של גודל הקלט.
2. לנסח רדוקציה בזמן פולינומי בשלושה חלקים: תיאור האלגוריתם, ניתוח זמן הריצה, והוכחת נכונות בשני הכיוונים.
3. להסביר מדוע הרדוקציה $\mathrm{IS}\le_p \mathrm{CLIQUE}$ עובדת, ומדוע ניסיונות נאיביים (מחיקת/הוספת כל הקשתות) נכשלים.
4. לקבוע נכון, בהינתן $A\le_p B$, מי הבעיה הקשה יותר ומה נובע ממה.
5. להבחין בין NP-קשה ל-NP-שלמה, ולהסביר את התפקיד של משפט 7 בהעשרת אוסף הבעיות ה-NP-קשות.
6. לעקוב אחרי גרף קונקרטי קטן דרך הרדוקציה, בשני הכיוונים, כולל קלט שלילי.

לקראת השיעור הבא. נוכיח את משפט Cook–Levin: $\mathrm{SAT}$ היא NP-קשה (ולמעשה NP-שלמה, שכן $\mathrm{SAT}\in \mathrm{NP}$ הוכח בשיעור 6). זו תהיה "הבעיה הראשונה", והיא נקודת המוצא לכל הרדוקציות שיבואו. מומלץ לחזור לפני כן על הוכחת משפט הרדוקציה ועל הוכחת הטרנזיטיביות מקורס החישוביות — ההוכחות כאן בנויות עליהן, בתוספת ניתוח הזמן.

הסיכום המקורי בכתב יד: גיא סופר.