12PARTITION ו-BIN PACKING, הבעיות ההמילטוניות ו-TSP

בקצרה

• מרחיבים את "שק" הבעיות ה-NP-hard בשתי בעיות שעוסקות במספרים ולכן הן "קרובות משפחה" של $\mathrm{SUBSET\text{-}SUM}$: $\mathrm{PARTITION}$ (האם אפשר לפצל רב-קבוצה של מספרים לשני חלקים שווי-סכום) ו-$\mathrm{BIN\text{-}PACKING}$ (האם אפשר לארוז $n$ פריטים ב-$k$ תאים בעלי קיבולת $1$).
• לב השיעור הוא שרשרת הרדוקציות $\mathrm{SUBSET\text{-}SUM} \le_p \mathrm{PARTITION} \le_p \mathrm{BIN\text{-}PACKING}$. שני הצעדים משתמשים באותו טריק: מחשבים את הסכום הכולל ומכניסים אותו לתוך הקלט החדש — פעם אחת כאיבר ריפוד נוסף, ופעם אחת כמכנה של נרמול.
• הליבה החישובית של הצעד הראשון היא איבר ריפוד יחיד $a_{n+1}=2S-\sum a_i$ (או $\sum a_i - 2S$), שערכו נגזר אלגברית מהדרישה "מה עוד חסר לצד השני כדי להגיע ל-$S$". הגזירה הזאת היא כל ההוכחה, ולכן היא נעשית כאן מלכתחילה ולא מוצגת כעובדה.
• הרדוקציה השנייה מוכיחה יותר ממה שביקשנו: היא מראה ש-$\mathrm{BIN\text{-}PACKING}$ נשארת NP-hard גם כאשר מספר התאים קבוע מראש ושווה $2$ — בניגוד ל-$\mathrm{CLIQUE}$ ול-$\mathrm{IS}$, שבהן קיבוע $k$ מפיל את הבעיה ל-P, ובדומה ל-$\mathrm{3COL}$.
• חוזרים לעולם הגרפים ומגדירים ארבע וריאציות המילטוניות ($DHP$, $DHC$, $UHP$, $UHC$). מציינים בלי הוכחה ש-$\mathrm{3SAT} \le_p DHP$, ומראים שכל ארבעתן שקולות פולינומית — ולכן די בארבע רדוקציות ולא ב-12.
• הרדוקציה האחרונה בקורס לזמן הקרוב היא $UHC \le_p TSP$: משלימים את הגרף לגרף מלא, נותנים משקל $1$ לקשתות המקוריות ו-$2$ לחדשות, ושואלים על מעגל במשקל $\le|V|$. הבחירה ב-$\{1,2\}$ ולא ב-$\{0,1\}$ אינה מקרית והמרצה הסביר למה.
• לאורך כל השיעור חוזרת ההבחנה שהתחילה בשיעור 11 — ערך מספר מול אורך הייצוג שלו. זו הסיבה ש"טבלת תכנון דינמי בגודל $k$" אינה אלגוריתם פולינומי, וזו הסיבה שהבעיות האלה קשות למרות שהן נראות כמו חשבון פשוט.

רקע ותלויות

השיעור הזה הוא הרביעי ברצף של "אוסף בעיות NP-hard", והוא מניח שלושה דברים משיעורים קודמים.

1. רדוקציית זמן פולינומי וכיוון החץ (שיעורים 7–9). נזכיר את ההגדרה במלואה. שפה $A$ ניתנת לרדוקציה בזמן פולינומי לשפה $B$, ומסמנים $A \le_p B$, אם קיימת פונקציה $f$ הניתנת לחישוב בזמן פולינומי כך שלכל $x$

$x \in A \iff f(x) \in B .$

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

2. $\mathrm{SUBSET\text{-}SUM}$ ושלמותה ב-NP (שיעור 11). נשתמש בתוצאה במלואה, ולכן נחזור עליה:

$(a_1,\dots,a_n,S)\in \mathrm{SUBSET\text{-}SUM} \iff \exists\, I\subseteq\{1,\dots,n\}\ \text{ s.t. }\ \sum_{i\in I} a_i = S .$

המספרים $a_1,\dots,a_n,S$ הם מספרים טבעיים הנתונים בייצוג מיקומי (המרצה אומר "בבסיס 10"), והוכח בשיעור 11 ש-$\mathrm{VC} \le_p \mathrm{SUBSET\text{-}SUM}$ ולכן $\mathrm{SUBSET\text{-}SUM}$ היא NP-complete.

3. ההבחנה בין ערך לבין אורך ייצוג (שיעור 11). מספר $a$ הכתוב בבסיס $10$ תופס $\Theta(\log a)$ תווים. לכן אלגוריתם שרץ בזמן $O(n\cdot S)$ הוא פולינומי בערך $S$ אך מעריכי באורך הייצוג של $S$, ואינו אלגוריתם פולינומי. ההבחנה הזאת חוזרת כאן פעמיים: פעם בדיון של המרצה על טבלת תכנון דינמי בגודל $k$ ([01:05:32]), ופעם בשאלה מה בכלל מותר לוריפייר לעשות.

4. תפקיד ה-$k$ בקלט (שיעור 10). בשיעור 10 ראינו ש-$\mathrm{3COL}$ נשארת NP-hard גם כאשר מספר הצבעים קבוע ואינו חלק מהקלט, בעוד שב-$\mathrm{CLIQUE}$ ו-$\mathrm{IS}$ קיבוע $k$ מראש מעביר את הבעיה ל-P (אפשר לעבור על כל $\binom{n}{k}=O(n^k)$ תת-הקבוצות). ההבחנה הזאת תחזור כאן במלוא עוצמתה כשנשאל מה קורה ל-$\mathrm{BIN\text{-}PACKING}$ עם $k=2$ קבוע.

הגדרות

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

קלט: $n$ מספרים טבעיים $a_1,\dots,a_n$, בייצוג מיקומי (בסיס $10$).

שאלה: האם קיימת קבוצת אינדקסים $I \subseteq \{1,2,\dots,n\}$ כך ש

$\sum_{i\in I} a_i \;=\; \sum_{i\notin I} a_i \;?$

ניסוח שקול, שהוא זה שבו נשתמש בפועל: האם קיימת $I\subseteq\{1,\dots,n\}$ כך ש

$\sum_{i\in I} a_i \;=\; \frac{1}{2}\sum_{i=1}^{n} a_i \;?$

השקילות מיידית: אם נסמן $T=\sum_{i=1}^n a_i$ אז $\sum_{i\notin I}a_i = T - \sum_{i\in I}a_i$, והשוויון בין שני הצדדים שקול ל-$\sum_{i\in I}a_i = T/2$.

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

למה קבוצת אינדקסים ולא תת-קבוצה של המספרים ([00:03:08]). המרצה הדגיש את הנקודה הזאת במפורש ואמר במכוון "עֲנִיָּה של מספרים" ולא "קבוצה של מספרים": איש לא הבטיח שהמספרים שונים זה מזה, ובקלט יכולות להיות חזרות. אילו היינו מדברים על תת-קבוצה של המספרים עצמם, הקלט $(5,5)$ היה מתמוטט לקבוצה $\{5\}$ ומאבד את המידע. לכן החלוקה נעשית תמיד על מרחב האינדקסים $\{1,\dots,n\}$: האינדקסים כולם שונים גם כשהמספרים אינם.

דוגמה. $(3,4,5,6)\in \mathrm{PARTITION}$: $T=18$, $T/2=9$, ו-$I=\{1,4\}$ נותנת $3+6=9$ והמשלים $4+5=9$.

אי-דוגמה מסוג ראשון (סכום אי-זוגי). $(1,2,4)\notin \mathrm{PARTITION}$: $T=7$ אי-זוגי, ולכן $T/2$ אינו שלם ואף סכום חלקי של שלמים לא יוכל להשתוות לו. זהו תנאי הכרחי שקל לבדוק ולכן הוא אינו מקל על הבעיה.

אי-דוגמה מסוג שני (איבר דומיננטי). $(1,1,10)\notin \mathrm{PARTITION}$: $T=12$, $T/2=6$, אבל $a_3=10>6$ — כל צד שמכיל את $10$ עובר את החצי. הדוגמה הזאת אינה שולית: בדיוק המקרה הזה יהפוך למקרה הראשון בטיפול של הרדוקציה הבאה.

הגדרה 2: הבעיה $\mathrm{BIN\text{-}PACKING}$ (אריזה בתאים)

קלט: מספרים $a_1,\dots,a_n \in (0,1]$ ומספר טבעי $k\in\mathbb{N}$.

שאלה: האם ניתן לחלק את המספרים ל-$k$ תאים כך שסכום המספרים בכל תא הוא לכל היותר $1$?

ניסוח פורמלי (המידול המתמטי שנעשה בכיתה ב-[00:35:59]–[00:37:33]). בהגדרות הקודמות ה"קיים" היה בולט — קיימת קבוצת קודקודים, קיימת השמה, קיימת תת-קבוצת אינדקסים. כאן הוא מוסתר במילים "ניתן לחלק", וצריך לחלץ אותו. חלוקה של $n$ פריטים ל-$k$ תאים מיוצגת בנוחות המרבית כפונקציה מהאינדקסים לתאים, ולכן:

$(a_1,\dots,a_n,k)\in \mathrm{BIN\text{-}PACKING} \iff \exists\, f:\{1,\dots,n\}\to\{1,\dots,k\}\ \ \text{ s.t. }\ \ \forall\, 1\le \ell\le k:\ \sum_{i\,:\,f(i)=\ell} a_i \le 1 .$

הביטוי $\{i : f(i)=\ell\}$ הוא בדיוק אוסף האינדקסים ש-$f$ מכניסה לתא ה-$\ell$, ולכן הסכום שמעליו הוא משקלו הכולל של התא ה-$\ell$.

אינטואיציה. יש לי מכולות בקיבולת $1$ ופריטים בגדלים שברִיים; האם $k$ מכולות מספיקות. זו בעיה שממדלת מספר עצום של בעיות עולם אמיתי — הקצאת קבצים לדיסקים, משימות למעבדים, פרסומות לבלוקי שידור.

למה $a_i > 0$ ולא $a_i \ge 0$ ([00:33:41]). אפסים הם מיותרים: אפשר להוציא אותם מהקלט מבלי לשנות את התשובה, שהרי אפשר לדחוס את כולם לתא כלשהו בלי להעלות שום סכום. לכן ההגדרה מוציאה אותם מראש והקטע הוא חצי-פתוח $(0,1]$. הקצה הימני סגור: פריט בגודל $1$ בדיוק הוא קלט חוקי (הוא ממלא תא שלם לבדו).

"לכל היותר $k$" מול "בדיוק $k$" ([00:34:11]). שאלה טובה שעלתה בכיתה. ההבדל אינו מהותי: אם הצלחנו לארוז ב-$j<k$ תאים, ויש לנו לפחות $k$ פריטים, אפשר תמיד "לפתוח עוד תא" ולהעביר אליו פריט בודד — הוא בגודל $\le 1$ ולכן התא החדש חוקי. הניסוח עם הפונקציה $f$ שלמעלה תופס ממילא את "לכל היותר", שכן $f$ אינה נדרשת להיות על.

דוגמה. $\left(\tfrac13,\tfrac13,\tfrac13,\tfrac12,\tfrac12\,;\,k=2\right)\in \mathrm{BIN\text{-}PACKING}$: תא אחד מקבל את שלושת השלישים (סכום $1$) והשני את שני החצאים (סכום $1$).

אי-דוגמה. $\left(\tfrac34,\tfrac34,\tfrac34\,;\,k=2\right)\notin \mathrm{BIN\text{-}PACKING}$: לפי שובך היונים תא אחד יקבל לפחות שני פריטים, וסכומם $\tfrac32>1$. שימו לב לאי-דוגמה הזאת — היא בדיוק ה"קלט השלילי המומצא" שהרדוקציה במשפט 4 תשתמש בו.

הגדרה 3: ארבע הבעיות ההמילטוניות

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

$DHP$. קלט: גרף מכוון $G=(V,E)$. שאלה: האם קיים ב-$G$ מסלול המילטוני?

$DHC$. קלט: גרף מכוון $G=(V,E)$. שאלה: האם קיים ב-$G$ מעגל המילטוני?

ובאופן מקביל $UHP$ ו-$UHC$ עבור גרפים לא מכוונים (ה-$D$ הוא directed וה-$U$ הוא undirected).

וריאציה עם קצוות נתונים ([01:10:55]). אפשר לנסח גם גרסה שבה הקלט כולל שני קודקודים $s,t$ ושואלים אם קיים מסלול המילטוני מ-$s$ ל-$t$. כל הגרסאות שקולות; לא נטפל בהן בנפרד.

דוגמה. הגרף המעגלי $C_4$ (קודקודים $1,2,3,4$ וקשתות $12,23,34,41$) שייך ל-$UHC$ — הוא בעצמו מעגל המילטוני.

אי-דוגמה. המסלול $P_4$ (קשתות $12,23,34$) שייך ל-$UHP$ אך לא ל-$UHC$: לקודקודים $1$ ו-$4$ יש דרגה $1$ כל אחד, ובמעגל כל קודקוד חייב דרגה לפחות $2$.

הגדרה 4: הבעיה $TSP$ (בעיית הסוכן הנוסע)

קלט: גרף מלא $G=(V,E)$, פונקציית משקלים על הקשתות $w:E\to[0,\infty)$, ומספר $K\in\mathbb{N}$.

שאלה: האם קיים ב-$G$ מעגל המילטוני שמשקלו לכל היותר $K$? משקלו של מעגל הוא סכום משקלי קשתותיו.

למה הגרף מלא ולמה צריך את המשקל ([01:19:56]). אם לא היינו מוסיפים משקלים, השאלה הייתה טריוויאלית: בגרף מלא על יותר משלושה קודקודים תמיד קיים מעגל המילטוני, שכן כל הקשתות קיימות ואפשר לעבור על הקודקודים בכל סדר. הקושי כולו טמון במשקל: קל למצוא מעגל, קשה למצוא מעגל זול.

האינטואיציה שנתנה לבעיה את שמה ([01:21:07]). יש $n$ ערים; סוכן נוסע יוצא מהמפעל, רוצה לעבור בכל אחת מהערים בדיוק פעם אחת ולחזור הביתה, במחיר נסיעה כולל של לכל היותר $K$.

דוגמה. $V=\{1,2,3,4\}$, כל הקשתות במשקל $1$, $K=4$. המעגל $1\!-\!2\!-\!3\!-\!4\!-\!1$ הוא המילטוני ומשקלו $4\le 4$, ולכן הקלט שייך ל-$TSP$.

אי-דוגמה. אותו גרף עם $K=3$: כל מעגל המילטוני על $4$ קודקודים מכיל בדיוק $4$ קשתות, ולכן משקלו לפחות $4>3$.

הערה מקדימה על אופטימיזציה ([01:22:12]). $TSP$ היא הגשר לנושא הבא בקורס: גרסת האופטימיזציה שלה אינה מקבלת $K$ אלא מבקשת את המעגל הזול ביותר. ההגדרה שלמעלה היא גרסת ההכרעה, וזו הגרסה היחידה שעליה NP-hardness מוגדרת פורמלית, מפני שהיא מוגדרת באמצעות רדוקציות בין שפות.

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

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

טענה. $\mathrm{PARTITION} \in \mathrm{NP}$.

הוכחה (שתי הדרכים שנאמרו בכיתה, [00:03:40]–[00:04:45]).

דרך א — מכונה אי-דטרמיניסטית. על קלט $(a_1,\dots,a_n)$ המכונה בוחרת באופן אי-דטרמיניסטי תת-קבוצה $I\subseteq\{1,\dots,n\}$ (כלומר, $n$ צעדים אי-דטרמיניסטיים, בכל אחד "בפנים/בחוץ"), מחשבת את שני הסכומים ומקבלת אם ורק אם הם שווים. חישוב שני הסכומים הוא $O(n)$ חיבורים של מספרים באורך לכל היותר אורך הקלט, ולכן זמן פולינומי. לפי ההגדרה של $\mathrm{NP}$ כמחלקת השפות המוכרעות בזמן פולינומי אי-דטרמיניסטי, $\mathrm{PARTITION}\in \mathrm{NP}$.

דרך ב — verifier. ה-certificate הוא $I$ עצמה, מקודדת כמחרוזת $n$ ביטים — אורך $n$, בוודאי פולינומי באורך הקלט. הוריפייר קורא את $I$, מחשב את שני הסכומים ומשווה. זמן פולינומי. $\blacksquare$

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

משפט 2 (לב השיעור): $\mathrm{SUBSET\text{-}SUM} \le_p \mathrm{PARTITION}$, ולכן $\mathrm{PARTITION}$ היא NP-hard

כיוון הרדוקציה במילים. נראה שאם היה בידינו אלגוריתם פולינומי ל-$\mathrm{PARTITION}$, היינו יכולים לפתור בעזרתו את $\mathrm{SUBSET\text{-}SUM}$ בזמן פולינומי. כלומר $\mathrm{PARTITION}$ היא הבעיה הקשה יותר מבין השתיים, ומכיוון ש-$\mathrm{SUBSET\text{-}SUM}$ היא NP-hard (שיעור 11), גם $\mathrm{PARTITION}$ היא NP-hard.

למה דווקא מ-$\mathrm{SUBSET\text{-}SUM}$ ([00:05:16]–[00:05:47], [00:29:19]–[00:30:24])

בכיתה הוצע לעשות רדוקציה מ-$\mathrm{SAT}$. המרצה קיבל שזה אפשרי — כל בעיה NP-complete ניתנת לרדוקציה לכל בעיה NP-complete אחרת — אבל דחה את זה כבחירה: "לקודד נוסחה בעזרת קבוצה של מספרים" זו עבודה מיותרת. העיקרון שהוא ניסח: מעבירים בין בעיות מאותו עולם. כאן הקלט מספרים והפלט מספרים, ולכן אפשר לעבור מסכום בפלט לסכום בקלט ובחזרה בלי לתרגם עולמות. רדוקציות שעוברות בין עולמות (כמו $\mathrm{VC} \le_p \mathrm{SUBSET\text{-}SUM}$ משיעור 11) הן היפות יותר — אבל כשבונים רדוקציה בפועל, מעדיפים את הבעיה הקרובה ביותר.

הגזירה: מהיכן בא איבר הריפוד

זהו החלק שאסור לדלג עליו. הרעיון: ב-$\mathrm{SUBSET\text{-}SUM}$ יש סכום יעד חיצוני $S$, וב-$\mathrm{PARTITION}$ אין — הסכום היעד מוכתב מבפנים והוא בהכרח חצי מהסכום הכולל. הרדוקציה חייבת "להטמיע את ה-$S$ פנימה" ([00:06:51]).

נסמן $T=\sum_{i=1}^n a_i$. נניח לרגע — רק לצורך החשיבה, לא כחלק מהאלגוריתם — שקיימת $I$ עם $\sum_{i\in I}a_i=S$, ונשאל מה חסר. הצד השני של החלוקה סוכם ל-$T-S$. אנחנו רוצים ששני הצדדים יסתכמו לאותו דבר, ולכן נוסיף איבר $b$ לצד ה"קטן". במקרה $S>T/2$ הצד הקטן הוא המשלים, ולכן נדרוש:

$\sum_{i\in I} a_i = S, \qquad \sum_{i\notin I} a_i + b = S .$

מכאן

$b \;=\; S-\sum_{i\notin I} a_i \;=\; S-\Big(\underbrace{\sum_{i=1}^{n} a_i}_{=\,T}-\underbrace{\sum_{i\in I} a_i}_{=\,S}\Big) \;=\; S-T+S \;=\; 2S-T .$

וכאן נמצא כל היופי ([00:12:16]–[00:13:20]). הביטוי האמצעי $S-\sum_{i\notin I}a_i$ הוא בלתי ניתן לחישוב על ידי הרדוקציה: הוא תלוי ב-$I$, ו-$I$ הוא בדיוק האובייקט שאין לנו ושאותו אנחנו לא מחפשים. אבל הביטוי הסופי $2S-T$ תלוי אך ורק בקלט — $S$ ניתן לנו, ו-$T$ מחושב בזמן לינארי. שאלת הביניים "מה $b$?" עברה מ"תלוי בפתרון" ל"תלוי בקלט", ובזה הרדוקציה הפכה לחוקית.

באופן סימטרי, אם $S<T/2$ הצד הקטן הוא $I$ עצמה, ואז נדרוש $\sum_{i\in I}a_i + b = \sum_{i\notin I}a_i$, כלומר $S+b=T-S$ ומכאן

$b \;=\; T-2S .$

בשני המקרים $b>0$ ממש, בדיוק בגלל תנאי המקרה. וכאשר $S=T/2$ אין מה לרפד.

הערה: בהרצאה ההצדקה למה $b$ חייב להיות חיובי לא נאמרה במפורש; היא נחוצה כדי שהפלט יהיה קלט חוקי של $\mathrm{PARTITION}$ מעל המספרים הטבעיים, והיא נובעת ישירות מתנאי המקרה: $S>T/2 \Rightarrow 2S-T>0$, ו-$S<T/2 \Rightarrow T-2S>0$.

הרדוקציה

אלגוריתם $R$. על קלט $(a_1,\dots,a_n,S)$ — מספרים טבעיים בבסיס $10$:

1. חשב $T \leftarrow \sum_{i=1}^{n} a_i$.
2. אם $2S = T$ (כלומר $S=\tfrac12 T$): החזר $(a_1,\dots,a_n)$ ללא שינוי.
3. אם $2S > T$ (כלומר $S>\tfrac12 T$): החזר $(a_1,\dots,a_n,\,2S-T)$.
4. אם $2S < T$ (כלומר $S<\tfrac12 T$): החזר $(a_1,\dots,a_n,\,T-2S)$.

הערה: בסיכום ובהרצאה ההשוואה נכתבת כ-$S$ מול $\tfrac12\sum a_i$. כאן היא נכתבת כ-$2S$ מול $T$ כדי להישאר בשלמים גם כאשר $T$ אי-זוגי; זו אותה השוואה בדיוק. שימו לב שכאשר $T$ אי-זוגי מקרה 2 פשוט אינו יכול להתרחש, ובכל אחד משני המקרים האחרים האיבר המוסף עדיין שלם.

הערה קריטית על מה שהרדוקציה עושה ואיננה עושה ([00:08:29], [00:21:06]–[00:22:11]). האלגוריתם מחשב את $T$ ומשווה אותו ל-$2S$ — וזה בסדר גמור, זו פעולה חשבונית פשוטה. הוא אינו בודק אם קיימת תת-קבוצה שסכומה $S$, ואינו יכול. ההבחנה הזאת עלתה כשאלה מהכיתה: "אז החזרנו מספר שעוזר לנו לפתור?" והתשובה הייתה נחרצת — לא. האיבר $a_{n+1}$ אינו מסייע במאום להכריע את השאלה; הוא מבטיח רק את המשפט "אם היה פתרון קודם, יש פתרון עכשיו, ולהפך". רדוקציה לעולם אינה באה להכריע את הבעיה.

עוד אי-הבנה שתוקנה בכיתה ([00:14:53]): הרדוקציה אינה מחזירה זוג מהצורה (מספרים, סכום יעד). הפלט הוא רשימה של $n+1$ מספרים בלבד, כי כזה בדיוק הוא קלט של $\mathrm{PARTITION}$. איש לא הבטיח ש-$n$ יישאר קבוע.

ניתוח זמן ריצה

נסמן ב-$m$ את אורך הייצוג הארוך ביותר מבין $a_1,\dots,a_n,S$, ובגודל הקלט $|x|\ge n+m$.

• שלב 1 מבצע $n-1$ חיבורים. הסכום החלקי אינו עולה על $n\cdot 10^m$ ולכן אורכו לכל היותר $m+\lceil\log_{10}n\rceil+1$. חיבור אחד עולה זמן לינארי באורכים, ולכן שלב 1 עולה $O\!\left(n\,(m+\log n)\right) = O(|x|^2)$.
• שלב 2 הוא השוואה אחת ($2S$ הוא הזזה/הכפלה ב-$2$, זמן לינארי).
• שלבים 3–4 הם חיסור אחד, זמן לינארי.
• הכתיבה של הפלט: $n+1$ מספרים, כל אחד באורך $O(m+\log n)$.

סך הכול $O(|x|^2)$ — פולינומי בגודל הקלט. חשוב לשים לב שזמן הריצה נמדד באורך הייצוג ולא בערך המספרים: לו היינו צריכים לספור עד $T$ הרדוקציה לא הייתה פולינומית.

אורך הפלט הוא $O(|x|)$; זה חשוב לטרנזיטיביות של $\le_p$ (רדוקציה שמנפחת את הקלט מעריכית אינה שמישה בהרכבה).

נכונות, כיוון ראשון: $(a_1,\dots,a_n,S)\in \mathrm{SUBSET\text{-}SUM} \Rightarrow R(x)\in \mathrm{PARTITION}$

יהיו $a_1,\dots,a_n,S$ ונניח $(a_1,\dots,a_n,S)\in \mathrm{SUBSET\text{-}SUM}$. אז קיימת $I\subseteq\{1,\dots,n\}$ כך ש-$\sum_{i\in I}a_i=S$. נפצל לשלושה מקרים.

מקרה 2 (זה שהוצג בהרצאה, [00:19:23]–[00:21:06]): $2S>T$. נסמן $a_{n+1}=2S-T$. האלגוריתם מחזיר $(a_1,\dots,a_{n+1})$. הסכום הכולל של הפלט הוא

$\sum_{i=1}^{n+1} a_i \;=\; T + (2S-T) \;=\; 2S,$

ולכן חצי הסכום הוא בדיוק $S$. עבור אותה $I$ עצמה (שהיא תת-קבוצה של $\{1,\dots,n\}\subseteq\{1,\dots,n+1\}$) מתקיים

$\sum_{i\in I} a_i \;=\; S \;=\; \frac{1}{2}\sum_{i=1}^{n+1} a_i ,$

ולכן גם $\sum_{i\notin I}a_i = 2S-S = S$. מצאנו חלוקה שווה, ומכאן $(a_1,\dots,a_{n+1})\in \mathrm{PARTITION}$.

מקרה 1: $2S=T$. האלגוריתם מחזיר את הקלט כפי שהוא. חצי הסכום הוא $T/2=S$, ואותה $I$ מקיימת $\sum_{i\in I}a_i=S=\tfrac12\sum_{i=1}^n a_i$. מכאן $(a_1,\dots,a_n)\in \mathrm{PARTITION}$.

מקרה 3: $2S<T$. נסמן $a_{n+1}=T-2S>0$. הסכום הכולל של הפלט הוא $T+(T-2S)=2(T-S)$, וחציו $T-S$. הפעם ניקח את המשלים $J=\{1,\dots,n\}\setminus I$ כצד אחד:

$\sum_{i\in J} a_i \;=\; T-S \;=\; \frac{1}{2}\sum_{i=1}^{n+1}a_i .$

מכאן $(a_1,\dots,a_{n+1})\in \mathrm{PARTITION}$.

הערה: בהרצאה נאמר "מקרים 1 ו-3 לבית" ([00:28:47]); הם נכתבים כאן במלואם. שימו לב שמקרה 3 אינו העתקה מילולית של מקרה 2 — בו הצד ה"טוב" הוא המשלים של $I$ ולא $I$ עצמה, וזו בדיוק הנקודה שבה סטודנטים נופלים.

נכונות, כיוון שני: $R(x)\in \mathrm{PARTITION} \Rightarrow (a_1,\dots,a_n,S)\in \mathrm{SUBSET\text{-}SUM}$

הערה מתודית שנאמרה בכיתה ובצדק ([00:24:27]–[00:25:28]). כשמוכיחים את הכיוון הזה, יש בידינו שני דברים בו-זמנית: הקלט המקורי $(a_1,\dots,a_n,S)$, שממנו התחלנו, וגם הפלט של האלגוריתם. אין צורך "לשחזר" את הקלט מן הפלט. בפרט יש לנו גישה חופשית ל-$S$ ול-$a_i$ בתוך ההוכחה, למרות שלאלגוריתם עצמו לא הייתה גישה לשום פתרון. זה מקור בלבול קבוע.

מקרה 2: $2S>T$. הפלט הוא $(a_1,\dots,a_n,a_{n+1})$ עם $a_{n+1}=2S-T$, וסכומו הכולל $2S$. נניח שהפלט שייך ל-$\mathrm{PARTITION}$. אז קיימת $J\subseteq\{1,\dots,n+1\}$ כך ש

$\sum_{i\in J} a_i \;=\; \sum_{i\notin J} a_i \;=\; \frac{1}{2}\cdot 2S \;=\; S .$

עכשיו מגיע הצעד שהודגש בכיתה ([00:27:03]): איננו יכולים להחזיר את $J$ כפתרון של $\mathrm{SUBSET\text{-}SUM}$, כי ייתכן ש-$n+1\in J$ ואז $J$ אינה תת-קבוצה של $\{1,\dots,n\}$. הפתרון: בלי הגבלת הכלליות $n+1\notin J$, שכן אם $n+1\in J$ נחליף את $J$ במשלים שלה $\overline{J}=\{1,\dots,n+1\}\setminus J$. זה חוקי בדיוק מפני ש-$\mathrm{PARTITION}$ סימטרית: שני הצדדים מסתכמים לאותו מספר $S$, ולכן המשלים הוא פתרון תקף באותה מידה, והאיבר $n+1$ נמצא באחד משני הצדדים בלבד.

לאחר ההחלפה, $J\subseteq\{1,\dots,n\}$ ומתקיים $\sum_{i\in J}a_i=S$. לפי ההגדרה, $(a_1,\dots,a_n,S)\in \mathrm{SUBSET\text{-}SUM}$.

מקרה 1: $2S=T$. הפלט הוא הקלט עצמו וסכומו $T=2S$. אם קיימת $J\subseteq\{1,\dots,n\}$ עם $\sum_{i\in J}a_i=\tfrac12 T=S$, זו בדיוק עדות ל-$\mathrm{SUBSET\text{-}SUM}$. (כאן לא צריך טיעון משלים, שכן לא נוסף איבר.)

מקרה 3: $2S<T$. הפלט הוא $(a_1,\dots,a_n,T-2S)$ וסכומו $2(T-S)$, כך שכל צד מסתכם ל-$T-S$. תהי $J$ צד של חלוקה שווה; בלי הגבלת הכלליות $n+1\notin J$ (אחרת נעבור למשלים, כמו קודם), ולכן $J\subseteq\{1,\dots,n\}$ ומתקיים $\sum_{i\in J}a_i=T-S$. נגדיר $I=\{1,\dots,n\}\setminus J$; אז

$\sum_{i\in I} a_i \;=\; T-\sum_{i\in J} a_i \;=\; T-(T-S) \;=\; S ,$

ולכן $(a_1,\dots,a_n,S)\in \mathrm{SUBSET\text{-}SUM}$. $\blacksquare$

מסקנה. $R$ היא רדוקציה בזמן פולינומי מ-$\mathrm{SUBSET\text{-}SUM}$ ל-$\mathrm{PARTITION}$. מכיוון ש-$\mathrm{SUBSET\text{-}SUM}$ היא NP-hard (שיעור 11), גם $\mathrm{PARTITION}$ היא NP-hard, ויחד עם משפט 1 — $\mathrm{PARTITION}$ היא NP-complete.

משפט 3: $\mathrm{BIN\text{-}PACKING} \in \mathrm{NP}$

טענה. $\mathrm{BIN\text{-}PACKING} \in \mathrm{NP}$.

הוכחה. ה-certificate הוא הפונקציה $f$ עצמה, מקודדת כרשימה של $n$ ערכים $f(1),\dots,f(n)$, כל אחד באורך $O(\log k)$ ביטים — סך הכול $O(n\log k)$, פולינומי באורך הקלט. הוריפייר סורק את הרשימה, צובר עבור כל תא את סכום הפריטים שהוקצו אליו, ומוודא שכל סכום הוא $\le 1$. לחלופין, מכונה אי-דטרמיניסטית בוחרת את $f$ באופן אי-דטרמיניסטי ומוודאת. $\blacksquare$

הערה: בהרצאה ([00:37:33]–[00:39:04]) הווידוא תואר כמעבר על $\ell=1,\dots,k$. זה מדויק רק אם $k$ אינו גדול מדי — וזו בדיוק הנקודה שהמרצה עצמו הדגיש ב-[01:05:32]: $k$ נכתב בייצוג מיקומי ולכן ערכו יכול להיות מעריכי באורך הקלט, ולולאה באורך $k$ תהיה מעריכית. שני תיקונים אפשריים, ושניהם נכונים: (א) לסרוק רק את התאים שאליהם הוקצה לפחות פריט אחד — לכל היותר $n$ תאים; (ב) להבחין שאפשר להניח בלי הגבלת הכלליות $k\le n$, שכן אם $k\ge n$ ניתן להכניס כל פריט לתא נפרד וכל תא מסתכם ל-$a_i\le 1$, ולכן הקלט הוא בהכרח כן-קלט. בשני התיקונים הווידוא הוא פולינומי, וכך גם הקידוד של ה-certificate.

משפט 4: $\mathrm{PARTITION} \le_p \mathrm{BIN\text{-}PACKING}$, ולכן $\mathrm{BIN\text{-}PACKING}$ היא NP-hard

כיוון הרדוקציה במילים. אלגוריתם פולינומי ל-$\mathrm{BIN\text{-}PACKING}$ היה נותן לנו אלגוריתם פולינומי ל-$\mathrm{PARTITION}$; $\mathrm{BIN\text{-}PACKING}$ היא הקשה מבין השתיים.

למה מ-$\mathrm{PARTITION}$ ולא מ-$\mathrm{SUBSET\text{-}SUM}$ ([00:39:47]–[00:41:21])

השאלה נשאלה בכיתה. התשובה: $\mathrm{PARTITION}$ היא בדיוק "חלוקה לשני תאים". הבעיה הקטנה ביותר של אריזה בתאים היא $k=2$, וב-$\mathrm{PARTITION}$ סכום היעד קבוע מראש לחצי — כלומר, ה-$S$ כבר "נבלע" בתוך הבעיה. מ-$\mathrm{SUBSET\text{-}SUM}$ אפשר לעשות רדוקציה, אבל אז צריך לשלב את $S$ בעצמנו, ו-$k$ עלול לצאת תלוי בערכי המספרים; והרי מספר התאים מופיע בתיאור הפונקציה $f$, ולכן $k$ גדול מדי היה מנפח את הפלט. המרצה הדגיש: בחירת בעיה אחרת אינה שגויה, היא פשוט פחות פשוטה.

הרעיון: נרמול לפי חצי הסכום ([00:43:26])

אנחנו מקבלים מספרים טבעיים שיכולים להיות עצומים, וצריכים להוציא מספרים ב-$(0,1]$. הדבר המתבקש הוא לחלק בקבוע. באיזה קבוע? נסמן $T=\sum_{j=1}^n a_j$. אם נחלק ב-$T$ נקבל סכום כולל $1$ — אפשר לדחוס הכול לתא אחד, והבעיה נעשית טריוויאלית. אם נחלק ב-$T/2$ נקבל סכום כולל $2$ בדיוק, וכעת אריזה ב-$2$ תאים בעלי קיבולת $1$ אפשרית אם ורק אם מתחלקים בדיוק $1$ ו-$1$ — לא נשאר שום מרווח. הצמידות המוחלטת הזאת היא מנוע הרדוקציה.

המכשול והטיפול בו ([00:44:31]–[00:46:45])

הנרמול $b_i = \dfrac{a_i}{T/2} = \dfrac{2a_i}{T}$ מייצר קלט חוקי רק אם $b_i \le 1$ לכל $i$, כלומר רק אם $a_i \le T/2$ לכל $i$. אם קיים $i$ עם $a_i > T/2$, הנרמול נכשל — אבל במקרה הזה אנחנו יודעים בוודאות שהקלט אינו ב-$\mathrm{PARTITION}$, שכן כל צד שמכיל את $a_i$ עובר את החצי. זהו מקרה פרטי שקל לזהות בזמן פולינומי (השוואה אחת אחרי חישוב $T$), ולכן מותר לנו במקרה הזה להחזיר קלט שלילי מומצא כלשהו של $\mathrm{BIN\text{-}PACKING}$. הקלט שנבחר הוא $\left(\tfrac34,\tfrac34,\tfrac34,\,2\right)$, שאינו ב-$\mathrm{BIN\text{-}PACKING}$ מטעמי שובך יונים.

הרדוקציה

אלגוריתם $R'$. על קלט $(a_1,\dots,a_n)$, מספרים טבעיים (בלי הגבלת הכלליות $a_i>0$ לכל $i$; אפסים אפשר להשמיט מבלי לשנות את התשובה):

1. חשב $T \leftarrow \sum_{j=1}^{n} a_j$.
2. אם קיים $1\le i\le n$ כך ש-$2a_i > T$: החזר $\left(\tfrac34,\tfrac34,\tfrac34,\,2\right)$.
3. אחרת, לכל $1\le i\le n$ הגדר $b_i \leftarrow \dfrac{2a_i}{\sum_{j=1}^{n} a_j}$, והחזר $(b_1,\dots,b_n,\,2)$.

הערה: התנאי בשלב 2 נכתב בסיכום (עמוד 2) עם $\ge$ ובהקלטה נאמר "גדול מ" ([00:44:31]). האי-שוויון החד הוא הנכון: אם $a_i = T/2$ בדיוק, אז $\{i\}$ מול המשלים היא חלוקה חוקית, הקלט כן ב-$\mathrm{PARTITION}$, ואילו הפלט של שלב 2 אינו ב-$\mathrm{BIN\text{-}PACKING}$ — הרדוקציה הייתה נשברת. עם $>$ הכול תקין, ואף מתקיים $b_i\le 1$ במקרה הגבול $a_i=T/2$ שנותן $b_i=1$, שהוא ערך חוקי.

על הייצוג של הפלט. ה-$b_i$ הם רציונליים ומיוצגים כזוג שלמים — מונה $2a_i$ ומכנה $T$. אורך כל אחד מהם $O(m+\log n)$ ולכן כל הפלט פולינומי באורך הקלט. שאלה שעלתה בכיתה ([01:07:39]) הייתה בדיוק על כך: אין דרישה שהקלט של $\mathrm{BIN\text{-}PACKING}$ יהיה שלם — ההגדרה מדברת על מספרים בקטע $(0,1]$, וזה בדיוק הצורך שבגללו הגדרנו כך.

התכונה המרכזית של הפלט

בשלב 3 מתקיים

$\sum_{i=1}^{n} b_i \;=\; \sum_{i=1}^{n}\frac{2a_i}{\sum_{j=1}^n a_j} \;=\; \frac{2}{\sum_{j=1}^n a_j}\sum_{i=1}^{n} a_i \;=\; \frac{2}{T}\cdot T \;=\; 2 ,$

כאשר ההוצאה של $\frac{2}{T}$ מחוץ לסכום מותרת כי הוא קבוע ואינו תלוי ב-$i$. כמו כן $b_i>0$ (כי $a_i>0$) ו-$b_i\le 1$ (כי $2a_i\le T$ בשלב זה), ולכן $b_i\in(0,1]$ והפלט הוא קלט חוקי.

ניתוח זמן ריצה

חישוב $T$ הוא $O(n(m+\log n))$ כמו קודם. שלב 2 הוא $n$ השוואות. שלב 3 הוא $n$ פעולות של כתיבת זוג $(2a_i,T)$ — אין צורך בחילוק ממשי. סך הכול $O(|x|^2)$, פולינומי, ואורך הפלט $O(|x|)$.

נכונות, כיוון ראשון: $(a_1,\dots,a_n)\in \mathrm{PARTITION} \Rightarrow R'(x)\in \mathrm{BIN\text{-}PACKING}$

נניח $(a_1,\dots,a_n)\in \mathrm{PARTITION}$: קיימת $I\subseteq\{1,\dots,n\}$ עם

$\sum_{i\in I} a_i \;=\; \sum_{i\notin I} a_i \;=\; \frac{1}{2}\sum_{j=1}^n a_j \;=\; \frac{T}{2}.$

קודם כול נראה שהאלגוריתם לא נכנס לשלב 2. לכל $1\le i\le n$, האיבר $a_i$ שייך לאחד משני הצדדים, וסכום הצד כולו הוא $T/2$; מכיוון שכל האיברים אי-שליליים, $a_i \le T/2$, כלומר $2a_i\le T$. לכן התנאי בשלב 2 אינו מתקיים לאף $i$, והפלט הוא $(b_1,\dots,b_n,2)$.

עכשיו נבנה אריזה. נכניס לתא הראשון את כל האיברים שהאינדקס שלהם ב-$I$, ולתא השני את כל השאר. (מכיוון שיש רק שני תאים, אפשר לתאר חלוקה בעזרת תת-קבוצה של אינדקסים במקום בעזרת פונקציה $f$ — הן מייצגות אותו דבר, [00:57:27].) אז

$\sum_{i\in I} b_i \;=\; \sum_{i\in I}\frac{2a_i}{\sum_{j=1}^n a_j} \;=\; \frac{2}{T}\sum_{i\in I} a_i \;=\; \frac{2}{T}\cdot\frac{T}{2} \;=\; 1 \;\le\; 1,$

ובאופן זהה $\sum_{i\notin I} b_i = 1 \le 1$. שני התאים חוקיים, ולכן $(b_1,\dots,b_n,2)\in \mathrm{BIN\text{-}PACKING}$.

נכונות, כיוון שני: $R'(x)\in \mathrm{BIN\text{-}PACKING} \Rightarrow (a_1,\dots,a_n)\in \mathrm{PARTITION}$

נניח שהפלט שייך ל-$\mathrm{BIN\text{-}PACKING}$.

שלב א — זיהוי איזה ענף של האלגוריתם רץ ([01:00:12]–[01:01:17]). הפלט של שלב 2 הוא $\left(\tfrac34,\tfrac34,\tfrac34,2\right)$, והוא אינו ב-$\mathrm{BIN\text{-}PACKING}$: יש שלושה פריטים ושני תאים, ולכן לפי שובך היונים תא אחד מקבל לפחות שניים מהם, וסכומם $\tfrac32>1$. מכיוון שהפלט כן ב-$\mathrm{BIN\text{-}PACKING}$, האלגוריתם בהכרח לא עבר בשלב 2, ולכן הפלט הוא $(b_1,\dots,b_n,2)$ עם $b_i=\frac{2a_i}{T}$.

שלב ב — מסקנה על החלוקה. מכיוון ש-$k=2$, קיימת $I\subseteq\{1,\dots,n\}$ (התא הראשון) כך ש

$\sum_{i\in I} b_i \le 1$

וגם

$\sum_{i\notin I} b_i \le 1 .$

אבל ראינו ש-$\sum_{i=1}^n b_i = 2$ בדיוק. אילו אחד משני הסכומים היה קטן ממש מ-$1$, סכומם היה קטן ממש מ-$2$ — סתירה. לכן שני הסכומים שווים ל-$1$ בדיוק. זו הנקודה שבה "הצמידות" של הבנייה משתלמת.

שלב ג — חזרה לקלט. מהשוויון $\sum_{i\in I} b_i = 1$ נקבל

$1 \;=\; \sum_{i\in I}\frac{2a_i}{T} \;=\; \frac{2}{T}\sum_{i\in I} a_i \quad\Longrightarrow\quad \sum_{i\in I} a_i \;=\; \frac{T}{2} \;=\; \frac{1}{2}\sum_{j=1}^{n} a_j .$

זו בדיוק ההגדרה של $\mathrm{PARTITION}$, ולכן $(a_1,\dots,a_n)\in \mathrm{PARTITION}$. $\blacksquare$

מסקנה. $\mathrm{PARTITION} \le_p \mathrm{BIN\text{-}PACKING}$; לפי משפט 2 ולפי הטרנזיטיביות של $\le_p$ מתקבל $\mathrm{SUBSET\text{-}SUM} \le_p \mathrm{BIN\text{-}PACKING}$, ולכן $\mathrm{BIN\text{-}PACKING}$ היא NP-hard. יחד עם משפט 3 — היא NP-complete.

משפט 5 (בונוס של אותה הוכחה): $\mathrm{BIN\text{-}PACKING}$ נשארת NP-hard גם כאשר $k=2$ קבוע

טענה. תהי $\mathrm{BIN\text{-}PACKING}_2$ הבעיה שקלטה $a_1,\dots,a_n\in(0,1]$ בלבד והשאלה היא אם ניתן לארוז אותם בשני תאים בעלי קיבולת $1$. אז $\mathrm{BIN\text{-}PACKING}_2$ היא NP-hard.

הוכחה. אותו אלגוריתם $R'$ בדיוק, למעט שאינו מדפיס את ה-$2$ בסוף — כי $2$ אינו חלק מהקלט של הבעיה החדשה. כל שלבי ההוכחה של משפט 4 עוברים מילה במילה, שכן בשום שלב לא השתמשנו ב-$k$ אלא כמספר קבוע. $\blacksquare$

למה זה מעניין ([00:48:20]–[00:53:44]). הרדוקציה שבנינו שולחת את כל הקלטים לתת-קבוצה מאוד צרה של מרחב הקלטים של $\mathrm{BIN\text{-}PACKING}$ — רק כאלה שבהם $k=2$. המרצה נתן את התמונה הכללית: אם $A$ ניתנת לרדוקציה ל-$B$ אבל הרדוקציה שולחת את כל הקלטים לתוך תת-בעיה $C\subseteq B$ (וכל אי-הקלטים לתוך $\overline{C}$), אז אותה רדוקציה עצמה מוכיחה גם ש-$C$ קשה. זה בדיוק מה שהיה בחישוביות ברדוקציות מ-$\mathrm{HALT}$ ל-$\mathrm{HALT}_0$ ול-$\mathrm{HALT}_\varepsilon$ — פונקציית המקבע שלחה את כל הקלטים לקבוצה זעירה ולכן סגרה כמה בעיות במחיר אחד.

ההשוואה שכדאי לזכור. קיבוע $k$ מראש לא תמיד מוריד את הקושי:

משפט 6: מדוע "תכנון דינמי לפי מספר התאים" אינו אלגוריתם פולינומי

השאלה עלתה מהכיתה ([01:05:00]–[01:05:32]) והתשובה היא ההבחנה המרכזית של שני השיעורים האחרונים, ולכן היא נרשמת כאן כטענה.

טענה. אלגוריתם ל-$\mathrm{BIN\text{-}PACKING}$ שמחזיק טבלה שבה $k$ תאים (או $k$ שורות) אינו אלגוריתם פולינומי בגודל הקלט.

הוכחה. המספר $k$ נתון בייצוג מיקומי ולכן אורך הייצוג שלו הוא $\Theta(\log k)$ תווים. אם $|x|$ הוא גודל הקלט אז $\log k \le |x|$, כלומר $k$ יכול להיות עד $2^{\Theta(|x|)}$. טבלה בגודל $k$ היא אפוא בגודל מעריכי ב-$|x|$, ובוודאי גם הזמן הדרוש כדי למלא אותה. $\blacksquare$

הערה: ההרחבה הבאה לא נאמרה בהרצאה במפורש, אך היא ההמשך הישיר של אותו טיעון ומופיעה בשיעור 11 עבור $\mathrm{SUBSET\text{-}SUM}$. אותו הסבר עצמו מסביר מדוע אלגוריתם התכנון הדינמי הידוע ל-$\mathrm{SUBSET\text{-}SUM}$, הרץ בזמן $O(n\cdot S)$, ואלגוריתם דומה ל-$\mathrm{PARTITION}$ הרץ בזמן $O(n\cdot T)$, אינם אלגוריתמים פולינומיים: הם פולינומיים בערך המספרים ומעריכיים באורך הייצוג שלהם. אלגוריתמים כאלה נקראים פסאודו-פולינומיים, והבעיות $\mathrm{SUBSET\text{-}SUM}$, $\mathrm{PARTITION}$ ו-$\mathrm{BIN\text{-}PACKING}$ נקראות NP-hard חלשות: לו המספרים היו נתונים בייצוג אונרי, אורך הייצוג היה שווה לערך והבעיות היו נופלות ל-P. זו הסיבה שהמרצה טורח לומר בכל פעם "בבסיס 10" ([00:02:06], [00:41:54]) — זה אינו קישוט, זו ההנחה שכל הקושי תלוי בה.

משפט 7: ארבע הבעיות ההמילטוניות

טענה א (נאמרת בלי הוכחה). $\mathrm{3SAT} \le_p DHP$, ולכן $DHP$ היא NP-hard.

הערה על הוויתור. המרצה הצהיר במפורש ([01:14:51]–[01:15:25]) שהרדוקציה הזאת "חמודה אבל מאוד מאוד טרחנית" ולכן מוותרים עליה בקורס: את התוצאה צריך לדעת, את ההוכחה לא.

טענה ב. בין כל שתיים מארבע הבעיות $DHP$, $DHC$, $UHP$, $UHC$ קיימת רדוקציה בזמן פולינומי; כלומר כולן שקולות פולינומית, ולכן כולן NP-hard.

איך זה נעשה ביעילות ([01:16:34]–[01:18:11]). לכאורה צריך להראות רדוקציה בין כל זוג סדור, כלומר $4\cdot3=12$ רדוקציות. אבל $\le_p$ טרנזיטיבי, ולכן די במעגל של ארבע רדוקציות:

$DHP \le_p DHC \le_p UHC \le_p UHP \le_p DHP ,$

ומכל צומת אפשר להגיע לכל צומת אחר לאורך המעגל. עלינו מ-12 ל-4.

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

טענה ג. כל ארבע הבעיות שייכות ל-$\mathrm{NP}$.

הוכחה ([01:12:33]). ה-certificate הוא סדר של הקודקודים (תמורה של $V$), באורך $O(|V|\log|V|)$. הוריפייר בודק שכל שתי קודקודים עוקבים בסדר מחוברים בקשת (ובגרף מכוון — בקשת בכיוון הנכון), ובמקרה של מעגל בודק גם את הקשת הסוגרת מהאחרון לראשון. זמן פולינומי. $\blacksquare$

אזהרה שעלתה בכיתה ([01:13:05]). סטודנט הזכיר שבקורס האלגוריתמים ראינו אלגוריתם פולינומי בעזרת מיון טופולוגי. זה נכון — אבל רק עבור גרף מכוון חסר מעגלים (DAG), שהוא מקרה מאוד מאוד ספציפי. אין בכך סתירה לקושי של הבעיה הכללית.

משפט 8: $UHC \le_p TSP$, ולכן $TSP$ היא NP-hard

כיוון הרדוקציה במילים. אלגוריתם פולינומי ל-$TSP$ היה מכריע את $UHC$ בזמן פולינומי; $TSP$ היא הקשה יותר.

למה דווקא מ-$UHC$ ([01:24:53]). אפשר היה לצאת גם ממסלול המילטוני — יש רדוקציות בין כל הגרסאות — אבל $TSP$ שואלת על מעגל בגרף לא מכוון, ולכן $UHC$ היא הבעיה הקרובה ביותר. שוב אותו עיקרון: להתחיל מהבעיה הקרובה ביותר.

הרדוקציה

אלגוריתם $R''$. על קלט $G=(V,E)$ — גרף פשוט לא מכוון: