11SUBSET SUM and its NP-completeness

בקצרה

• מוכיחים שהבעיה $\mathrm{SUBSET\text{-}SUM}$ — בהינתן מספרים טבעיים $a_1,\dots,a_n$ ומספר יעד $S$, האם קיימת תת-קבוצת אינדקסים שסכום איבריה בדיוק $S$ — היא NP-complete.
• החלק הקל: שייכות ל-NP, באמצעות certificate שהוא קבוצת האינדקסים עצמה.
• החלק המהותי: רדוקציה $\mathrm{VC} \le_p \mathrm{SUBSET\text{-}SUM}$, שבה כל קודקוד וכל קשת מקבלים מספר שנבנה ספרה-ספרה: עמודה אחת לכל קשת, ועוד עמודה מובילה שסופרת קודקודים.
• לב ההוכחה הוא טיעון אי-נשאות: בכל עמודת קשת סכום הספרות של כל המספרים הוא לכל היותר $3$, ולכן חיבור ארוך בבסיס $10$ אף פעם אינו נושא, וניתן להסיק מן הסכום מסקנה נפרדת על כל עמודה בנפרד. בלי הטיעון הזה כל ההוכחה קורסת.
• בנוסף מוכיחים בשיעור שתי תוצאות "מסביב": כל שפה ב-P ניתנת לרדוקציה לכל שפה לא-טריוויאלית (ולכן $\le_p$ הוא כלי גס מדי מכדי להבחין בין בעיות בתוך P), ו-$\mathrm{4COL}$ היא NP-complete באמצעות רדוקציה מ-$\mathrm{3COL}$.
• מבחינים בין ערך המספרים לבין אורך הייצוג שלהם: אלגוריתם התכנון הדינמי מקורס האלגוריתמים רץ בזמן $O(n\cdot S)$, וזה אינו זמן פולינומי בגודל הקלט. זו הסיבה ש-$\mathrm{SUBSET\text{-}SUM}$ היא NP-hard "חלשה" בלבד.
• מי שקורא רק את הסעיף הזה צריך לדעת: הרדוקציה עצמה קצרה, אבל היא נשענת על שתי נקודות עדינות (אי-נשאות, ו"בדיוק $K$" מול "לכל היותר $K$") שנבחנות בדיוק בגללן.

רקע ותלויות

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

מחלקות ו-verifiers (שיעורים 7–8). $P$ היא מחלקת השפות הניתנות להכרעה בזמן פולינומי במכונת טיורינג דטרמיניסטית; $\mathrm{NP}$ היא מחלקת השפות שעבורן קיים verifier פולינומי, כלומר קיימים פולינום $p$ ומכונה $V$ הרצה בזמן פולינומי כך ש-$x\in L$ אם ורק אם קיים $c$ באורך $|c|\le p(|x|)$ שעבורו $V(x,c)$ מקבלת. באופן שקול, $\mathrm{NP}$ היא מחלקת השפות הנכרעות בזמן פולינומי במכונה אי-דטרמיניסטית.

רדוקציות (שיעורים 8–9). $A \le_p B$ פירושו: קיימת פונקציה $f$ הניתנת לחישוב בזמן פולינומי כך שלכל $x$ מתקיים $x\in A \iff f(x)\in B$. שימו לב לכיוון: $A \le_p B$ אומר ש-$B$ היא הבעיה הקשה יותר — אפשר לפתור את $A$ אם יודעים לפתור את $B$. בהקלטה, כמו בכל דיבור חופשי, הכיוון מתהפך לעיתים קרובות; תמיד תרגמו חזרה לניסוח הפורמלי. שפה $B$ היא NP-hard אם לכל $A\in \mathrm{NP}$ מתקיים $A \le_p B$, והיא NP-complete אם בנוסף $B\in \mathrm{NP}$. הכלי המרכזי: אם $C$ היא NP-hard ו-$C \le_p B$, אז גם $B$ היא NP-hard, מפני שהיחס $\le_p$ טרנזיטיבי.

התוצאות שנשתמש בהן בפועל. משפט קוק–לוין (שיעור 9) נותן לנו את $\mathrm{SAT}$ כבעיה ה-NP-complete הראשונה, ומשיעור 10 יש בידינו ש-$\mathrm{3SAT}$, $\mathrm{3COL}$ ו-$\mathrm{VC}$ הן NP-complete. בשיעור הזה נשתמש ישירות רק בשתי עובדות: $\mathrm{3COL}$ היא NP-hard, ו-$\mathrm{VC}$ היא NP-hard.

נזכיר במלואן את שתי ההגדרות מהשיעור הקודם, כדי שלא תצטרכו לקפוץ:

• $\mathrm{VC}$ (Vertex Cover): הקלט הוא זוג $(G,K)$ כאשר $G=(V,E)$ גרף לא מכוון ו-$K\in\mathbb{N}$. כיסוי בקודקודים הוא קבוצה $U\subseteq V$ כך שלכל קשת $e\in E$ יש לפחות קצה אחד ב-$U$ (בהקלטה [00:53:37] סטודנט הציע "בדיוק אחד" והמרצה תיקן במפורש ל"לפחות אחד"; שימו לב שלפי זה $V$ עצמה היא תמיד כיסוי). מתקיים $(G,K)\in \mathrm{VC}$ אם ורק אם קיים כיסוי בקודקודים $U$ עם $|U|\le K$.
• $\mathrm{kCOL}$: הקלט הוא גרף $G=(V,E)$, והשאלה היא האם קיימת פונקציה $f:V\to\{1,\dots,k\}$ כך שאף קשת אינה מונוכרומטית, כלומר לכל $xy\in E$ מתקיים $f(x)\ne f(y)$. $k$ הוא חלק משם הבעיה, לא מהקלט. הפונקציה אינה חייבת להיות על: מותר שצבע לא ינוצל כלל ([00:15:50]).

הגדרות

הגדרה 1: שפה טריוויאלית

תהי $\Sigma$ אלפבית. שפה $B\subseteq \Sigma^*$ נקראת טריוויאלית אם $B=\emptyset$ או $B=\Sigma^*$. אחרת היא אינה טריוויאלית, כלומר קיימים $b_1\in B$ וגם $b_0\notin B$.

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

דוגמה. $\mathrm{SAT}$ אינה טריוויאלית: הנוסחה $x\lor \lnot x$ ספיקה, והנוסחה $x\land\lnot x$ אינה. אי-דוגמה. השפה $\{x : |x|\ge 0\}=\Sigma^*$ טריוויאלית.

הגדרה 2: הבעיה SUBSET SUM

הקלט הוא סדרה של $n$ מספרים טבעיים $a_1,a_2,\dots,a_n$ ומספר טבעי נוסף $S$, כולם נתונים בבסיס $10$. השאלה:

$(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 .$

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

דוגמה. $(3,7,11,2\;;\;S=13)\in \mathrm{SUBSET\text{-}SUM}$ שכן $11+2=13$. אי-דוגמה. $(4,6,10\;;\;S=13)\notin \mathrm{SUBSET\text{-}SUM}$: כל המספרים זוגיים ולכן כל סכום חלקי זוגי.

הערת בסיס. בסיס $10$ נבחר לנוחות בלבד — הוא מאפשר לכתוב על הלוח "חיבור ארוך" ולראות את העמודות ([00:56:15]). כל בסיס $\ge 2$ נותן את אותה בעיה בדיוק, מפני שההמרה בין בסיס $2$ לבסיס $10$ משנה את אורך הייצוג בגורם קבוע $\log_2 10$. הבסיס האונרי הוא היוצא מן הכלל היחיד — ראו הגדרה 3.

הגדרה 3: ערך מספר מול אורך הייצוג שלו

עבור $a\in\mathbb{N}$, הערך הוא $a$ עצמו, ואילו אורך הייצוג בבסיס $b\ge 2$ הוא $\lceil \log_b (a+1)\rceil$ ספרות. הקשר ביניהם מעריכי: כדי לייצג את $n$ נחוצים $\Theta(\log n)$ ביטים.

אינטואיציה. אלגוריתם נקרא פולינומי אם זמן ריצתו פולינומי באורך הקלט, לא בערכיו. כשהקלט הוא גרף גדול ומספר קטן, ההבחנה אינה מזיקה: בבעיות כמו $\mathrm{CLIQUE}$ ו-$\mathrm{IS}$ מקבלים $(G,K)$, ו-$K\le |V|$, כך שהגרף "בולע" את המספר ותרומתו לאורך הקלט זניחה ([00:48:18]). כשהקלט מורכב כולו ממספרים, כמו כאן, ההבחנה קריטית.

אי-דוגמה מאירה. אלגוריתם בדיקת ראשוניות הנאיבי עובר על כל המספרים עד $\sqrt{n}$ ובודק חלוקה. מספר האיטרציות $\sqrt n$ נראה פולינומי, אך אורך הקלט הוא $\Theta(\log n)$, ולכן $\sqrt n = 2^{\frac12\log n}$ הוא מעריכי באורך הקלט ([00:49:19]).

המקרה האונרי. אם מייצגים מספר בבסיס $1$ (אונרי), אורך הייצוג שווה לערך. אז — ורק אז — אלגוריתם שזמנו פולינומי בערך הופך לאלגוריתם פולינומי ([00:50:25]).

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

משפט 1: כל שפה ב-P ניתנת לרדוקציה לכל שפה לא-טריוויאלית

תהיינה $A,B\subseteq\Sigma^*$ שפות. אם $A\in P$ ו-$B$ אינה טריוויאלית, אז $A \le_p B$.

תזכורת מחישוביות ([00:00:32]). ראינו שם את הטענה המקבילה: אם $A\in R$ (כריעה) ו-$B$ אינה טריוויאלית, אז $A \le_m B$. ההוכחה כאן היא אותה הוכחה בדיוק; ההבדל היחיד הוא שכאן מתחייבים גם על זמן הריצה של הרדוקציה.

הוכחה. מכיוון ש-$A\in P$, קיימת מכונה $M_A$ המכריעה את $A$ בזמן פולינומי. מכיוון ש-$B$ אינה טריוויאלית, קיים $b_1\in B$ וקיים $b_0\notin B$. שני המחרוזות האלה קבועות ונבחרות לפני שהמכונה רואה קלט כלשהו.

נגדיר מכונה $M$ באופן הבא. על קלט $x$:

1. הרץ את $M_A$ על $x$.
2. אם $M_A$ קיבלה את $x$ — החזר $b_1$. אחרת — החזר $b_0$.

נכונות. יהי $x\in\Sigma^*$.

• נניח $x\in A$. אז $M_A$ מקבלת את $x$, ולכן $M(x)=b_1\in B$.
• נניח $x\notin A$. אז $M_A$ דוחה את $x$, ולכן $M(x)=b_0\notin B$.

בשני המקרים $x\in A \iff M(x)\in B$, כנדרש.

זמן ריצה. שלב 1 דורש זמן פולינומי ב-$|x|$, לפי הגדרת $M_A$. שלב 2 הוא כתיבת אחת משתי מחרוזות קבועות. כאן ישנה נקודה עדינה שסטודנטית העלתה בהקלטה ([00:09:43]): "אבל $b_0,b_1$ עלולים להיות ארוכים מאוד!" — נכון, אבל אורכם אינו תלוי ב-$x$. המכונה $M$ מחזיקה אותם "בבטן" כחלק מתיאורה, היא לא מקבלת אותם מבחוץ, והם נקבעו לפני שהוגדר $x$. לכן, כפונקציה של $|x|$, שלב 2 לוקח זמן קבוע. סך הכול $M$ רצה בזמן פולינומי בגודל הקלט, ולכן $A\le_p B$. $\blacksquare$

המשמעות ([00:02:37]–[00:04:12]). הטענה אומרת ש-$P$ היא המחלקה הקלה ביותר ביחס לרדוקציות זמן פולינומי: כל שפה לא-טריוויאלית "קשה לפחות כמו" כל שפה ב-$P$. אבל אנחנו יודעים שגם בתוך $P$ יש דרגות קושי — למשל, ממשפט ההיררכיה לזמן (מן הפרק הראשון של הקורס) יש שפה הניתנת להכרעה בזמן $n^3$ ולא בזמן ליניארי. המסקנה: רדוקציות זמן פולינומי הן כלי גס מדי מכדי להבחין בין בעיות בתוך $P$ — מבחינתן כל הבעיות ב-$P$ הן אותו דבר. זהו הכלי המתאים להוכחת קושי, לא לדירוג עדין.

הערה: בהרצאה זה נאמר בקיצור; הפירוט כאן. השימוש הישיר בטענה (בשיעורי הבית, [00:12:25]) הוא להראות שמחלקה כמו $\mathrm{DTime}(n^{10})$ אינה סגורה לרדוקציות זמן פולינומי. הנימוק: קחו $B\in \mathrm{DTime}(n^{10})$ לא-טריוויאלית כלשהי (למשל $B=\{x : x$ מתחיל ב-$0\}$, שהיא אפילו ליניארית). לפי משפט ההיררכיה לזמן קיימת $A\in \mathrm{DTime}(n^{11})\setminus \mathrm{DTime}(n^{10})$, ובפרט $A\in P$. לפי משפט 1, $A\le_p B$. אילו $\mathrm{DTime}(n^{10})$ הייתה סגורה כלפי מטה ל-$\le_p$, היה נובע $A\in \mathrm{DTime}(n^{10})$ — סתירה.

משפט 2: $\mathrm{4COL}$ היא NP-complete

שייכות ל-NP. ה-certificate הוא הצביעה עצמה, $g:V\to\{1,2,3,4\}$, שאורכה $2|V|$ ביטים — פולינומי בגודל הקלט. ה-verifier עובר על כל הקשתות ובודק לכל $xy\in E$ ש-$g(x)\ne g(y)$; זמן $O(|E|)$. הבדיקה מקבלת אם ורק אם קיימת צביעה חוקית, כנדרש.

NP-hardness: $\mathrm{3COL} \le_p \mathrm{4COL}$.

האלגוריתם. על קלט $G=(V,E)$:

1. בנה גרף $\hat G$ על ידי הוספת קודקוד חדש $\hat v$ לגרף, וחיבורו בקשת לכל הקודקודים ב-$V$.
2. החזר את $\hat G$.

זמן ריצה. הבנייה מוסיפה קודקוד אחד ו-$|V|$ קשתות, ולכן היא לינארית בגודל הקלט; בפרט פולינומית. הפלט קטן מפי שניים מן הקלט ועוד קבוע, כך שגודלו פולינומי בגודל הקלט ([00:26:10]).

נכונות. יהי $G=(V,E)$ גרף. נסמן ב-$\hat G=(\hat V,\hat E)$ את הגרף המוחזר על ידי האלגוריתם בהרצתו על $G$, וב-$\hat v$ את הקודקוד הנוסף.

כיוון ראשון: $G\in \mathrm{3COL} \Rightarrow \hat G\in \mathrm{4COL}$. קיימת צביעה חוקית $f:V\to\{1,2,3\}$, כלומר אין ב-$G$ קשת מונוכרומטית. נגדיר $g:\hat V\to\{1,2,3,4\}$ על ידי

$g(v)=\begin{cases} f(v) & v\in V\\ 4 & \text{otherwise}\end{cases}$

תהא $e=xy\in \hat E$.

• אם $e\in E$, אז $g(x)=f(x)$ ו-$g(y)=f(y)$, ומכיוון ש-$f$ צביעה חוקית של $G$ נובע $g(x)\ne g(y)$.
• אחרת $e$ היא קשת חדשה, ולכן $x=\hat v$ או $y=\hat v$. הקודקוד $\hat v$ צבוע ב-$4$ והשני צבוע בצבע מתוך $\{1,2,3\}$, ולכן שוב $g(x)\ne g(y)$.

כך או כך $g(x)\ne g(y)$, ולכן $g$ היא צביעה חוקית של $\hat G$ ב-$4$ צבעים, כלומר $\hat G\in \mathrm{4COL}$.

כיוון שני: $\hat G\in \mathrm{4COL} \Rightarrow G\in \mathrm{3COL}$. קיימת צביעה חוקית $g:\hat V\to\{1,2,3,4\}$ של $\hat G$. ללא הגבלת הכלליות $g(\hat v)=4$ — הצבעים סימטריים לחלוטין, ואם $\hat v$ קיבל צבע אחר נחליף את שמות שני הצבעים. נגדיר $f:V\to\{1,2,3,4\}$ על ידי $f(v)=g(v)$ לכל $v\in V$, ונראה שהטווח בפועל הוא $\{1,2,3\}$: יהי $x\in V$. מכיוון שחיברנו את $\hat v$ לכל קודקודי $V$, מתקיים $x\hat v\in \hat E$, ולכן $g(x)\ne g(\hat v)=4$. לכן לכל $x\in V$ מתקיים $f(x)\in\{1,2,3\}$.

כעת תהא $xy\in E$ קשת. לא הסרנו קשתות, ולכן גם $xy\in\hat E$, ומכיוון ש-$g$ חוקית ב-$\hat G$ נקבל $f(x)=g(x)\ne g(y)=f(y)$. לכן $f$ היא צביעה חוקית של $G$ ב-$3$ צבעים, כלומר $G\in \mathrm{3COL}$. $\blacksquare$

למה הבנייה נראית כך — שני ניסיונות שנשברו.

ניסיון ראשון: הזהות ([00:16:53]–[00:18:30]). סטודנט הציע להחזיר את $G$ עצמו: הרי אם $G$ הוא $3$-צביע אז בפרט הוא $4$-צביע. הכיוון הראשון עובד — וזו בדיוק הסיבה לחשוד. הכיוון השני קורס: הקליק $K_4$ הוא $4$-צביע (כל קודקוד בצבע משלו) ובוודאות אינו $3$-צביע, שכן בקליק בגודל $n$ כל שני קודקודים מחוברים ולכן דרושים $n$ צבעים. אז $K_4\in \mathrm{4COL}$ אבל $K_4\notin \mathrm{3COL}$, והזהות אינה רדוקציה.

ניסיון שני: להוסיף קודקוד בלי לחבר אותו ([00:31:29]–[00:34:41]). סטודנטית שאלה למה בכלל צריך את הקשתות החדשות. גם כאן הכיוון הראשון עובר בלי שינוי. הכיוון השני נשבר בדיוק בשורה אחת: הצעד שאומר "לכל $x\in V$ מתקיים $g(x)\ne 4$" נשען כולו על קיום הקשת $x\hat v$. בלי הקשתות אין שום מניעה שקודקוד ב-$V$ ייצבע ב-$4$, והצמצום של $g$ ל-$V$ לא יהיה צביעה בשלושה צבעים.

הערה: בהרצאה נאמר על כך רק ש"ההוכחה נשברת"; שימו לב שזה אינו מוכיח שהבנייה החלופית אינה רדוקציה — היא באמת אינה, אבל כדי לטעון זאת דרושה דוגמה נגדית, ולא רק כישלון של הוכחה מסוימת. דוגמה נגדית: $G=K_4$ ללא הקשתות החדשות נותן גרף שהוא $K_4$ בתוספת קודקוד מבודד; הגרף הזה $4$-צביע, ואילו $K_4$ אינו $3$-צביע.

ניסיון שלישי — ולמעשה הטעות החמורה מכולן ([00:21:39]–[00:23:45]). סטודנט ניסח את אותה בנייה נכונה במילים "נוסיף קודקוד חדש ונצבע אותו בצבע רביעי", והמרצה עצר את השיעור וכינה זאת "חטא כבד". שימו לב היכן בדיוק נמצאת הטעות: הבנייה זהה, אבל הניסוח מייחס לאלגוריתם גישה לצביעה. לאלגוריתם הרדוקציה אין ולא יכולה להיות גישה לפתרון. הוא מקבל גרף ומחזיר גרף; הוא אינו מחפש צביעה, אינו מקבל אחת ואינו יודע אם קיימת. הצביעות $f$ ו-$g$ מופיעות אך ורק בהוכחת הנכונות, ששם — ורק שם — מותר להניח "קיימת צביעה חוקית". זו הסיבה שבניסוח שלמעלה שלב 1 של האלגוריתם מדבר רק על קודקודים וקשתות, ואילו הפונקציה $g$ מוגדרת רק בתוך כיוון ההוכחה. המרצה השווה זאת לרדוקציה מ-$\mathrm{HALT}$: אסור לכתוב "אם המכונה עוצרת אז נחזיר כך", מפני שאי אפשר לבדוק זאת. אותו עיקרון בדיוק חוזר במשפט 4 להלן — הרדוקציה מ-$\mathrm{VC}$ ל-$\mathrm{SUBSET\text{-}SUM}$ בונה מספרים מהגרף ומ-$K$ בלבד, ואינה מחפשת כיסוי.

משפט 3: $\mathrm{SUBSET\text{-}SUM} \in \mathrm{NP}$

הוכחה. ה-certificate הוא קבוצת האינדקסים $I\subseteq\{1,\dots,n\}$, שאפשר לקודד ב-$n$ ביטים — פולינומי בגודל הקלט. ה-verifier מקבל $(a_1,\dots,a_n,S)$ ואת $I$, מסכם $\sum_{i\in I}a_i$ ומשווה ל-$S$. אם כל מספר תופס לכל היותר $\ell$ ספרות, חיבור של עד $n$ מספרים כאלה דורש $O(n\ell)$ פעולות, וההשוואה $O(\ell)$ — כלומר זמן פולינומי באורך הקלט. ה-verifier מקבל עבור $certificate$ כלשהו אם ורק אם קיימת $I$ עם הסכום הנכון, כלומר אם ורק אם הקלט בשפה. באופן שקול: בוחרים את $I$ באופן אי-דטרמיניסטי ומסכמים. $\blacksquare$

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

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

הרעיון. נבנה מספרים שאפשר לחשוב עליהם כשורות בטבלה: עמודה מיוחדת אחת בשם $d$, ועוד עמודה אחת לכל קשת. שורת קודקוד "מדווחת" באילו קשתות הוא נוגע; שורת קשת היא וקטור יחידה. סכום היעד דורש בדיוק $2$ בכל עמודת קשת ובדיוק $K$ בעמודה $d$. הקסם הוא שהדרישה "בדיוק $2$" ניתנת לסיפוק אם ורק אם לפחות אחד משני קצות הקשת נבחר.

האלגוריתם. על קלט $G=(V,E)$ ו-$K\in\mathbb{N}$, נסמן $m=|E|$ ו-$E=\{e_1,\dots,e_m\}$.

0. אם $K>|V|$, החלף את $K$ ב-$|V|$. (הצדקה למטה.)
1. לכל קודקוד $v\in V$ נייצר מספר $a_v$ בן $m+1$ ספרות, שבו הספרה השמאלית ביותר היא $1$, ולכל $1\le j\le m$ הספרה ה-$(j+1)$ משמאל היא $1$ אם $v\in e_j$ ו-$0$ אחרת.
2. לכל קשת $e\in E$ נייצר מספר $a_e$ בן $m+1$ ספרות, שבו הספרה השמאלית ביותר היא $0$, ולכל $1\le j\le m$ הספרה ה-$(j+1)$ משמאל היא $1$ אם ורק אם $e=e_j$, ואחרת $0$.
3. נגדיר מספר יעד $S$ בן $m+\lceil\log_{10}(K+1)\rceil$ ספרות: $\lceil\log_{10}(K+1)\rceil$ הספרות השמאליות ביותר מייצגות את $K$, וכל יתר הספרות שוות $2$.
4. החזר את רשימת המספרים $\{a_v\}_{v\in V}\cup\{a_e\}_{e\in E}$ ואת $S$.

באלגברה, במקום בציור, אלה בדיוק המספרים

$a_v \;=\; 10^{m} \;+\; \sum_{j=1}^{m} [\,v\in e_j\,]\cdot 10^{\,m-j}, \qquad a_{e_i} \;=\; 10^{\,m-i}, \qquad S \;=\; K\cdot 10^{m} \;+\; \sum_{j=1}^{m} 2\cdot 10^{\,m-j}.$

על צעד 0 והביטוי "בדיוק $K$". ההגדרה של $\mathrm{VC}$ מדברת על כיסוי בגודל לכל היותר $K$, ואילו הבנייה כופה בעמודה $d$ סכום של בדיוק $K$. הפער אינו מזיק, משתי סיבות: (א) הוספת קודקודים לכיסוי משאירה אותו כיסוי, ולכן אם קיים כיסוי בגודל $\le K$ ו-$K\le|V|$, אפשר להשלים אותו לכיסוי בגודל בדיוק $K$; (ב) אם $K>|V|$ אז $(G,K)\in \mathrm{VC}$ תמיד (הקבוצה $V$ עצמה מכסה), ולכן ההחלפה $K\leftarrow|V|$ אינה משנה את התשובה, שכן $(G,K)\in \mathrm{VC} \iff (G,\min(K,|V|))\in \mathrm{VC}$. צעד 0 מבוצע בזמן $O(\log K+\log|V|)$.

הערה: בהרצאה ובסיכום עוברים ישר ל"קיים $U$ כיסוי עם $|U|=K$" ([01:13:18]) בלי לומר מדוע מותר; הפירוט כאן.

למה 4.1 (אי-נשאות) — הצעד שבלעדיו כלום לא עובד

תהי $I$ תת-קבוצה כלשהי של המספרים שנבנו. נסמן $U=I\cap\{a_v\}_{v\in V}$ (ונזהה אותה עם קבוצת קודקודים), ולכל $1\le j\le m$ נסמן

$c_j \;=\; \bigl|\{v\in U : v\in e_j\}\bigr| \;+\; [\,a_{e_j}\in I\,].$

אזי:

1. $0\le c_j\le 3$ לכל $j$;
2. $\displaystyle \sum_{x\in I} x \;=\; |U|\cdot 10^{m} \;+\; \sum_{j=1}^{m} c_j\cdot 10^{\,m-j}$, וזהו בדיוק הייצוג העשרוני של הסכום בספרות $c_1,\dots,c_m$ — כלומר החיבור הארוך אינו נושא באף עמודת קשת;
3. $\displaystyle \sum_{j=1}^{m} c_j\cdot 10^{\,m-j} < 10^{m}$.

הוכחה. (1) לקשת $e_j$ יש בדיוק שני קצוות. לכן לכל היותר שני מספרי קודקוד נושאים $1$ בעמודה $j$, ובנוסף בדיוק מספר קשת אחד — $a_{e_j}$ — נושא שם $1$. סך כל האחדות בעמודה $j$ על פני כל המספרים שנבנו הוא לכל היותר $2+1=3$, ובפרט זה חסם על $c_j$.

(2) הזהות עצמה נובעת מפתיחת הסכום לפי ההצגה האלגברית שלמעלה וקיבוץ לפי חזקות $10$. הטענה שזהו הייצוג העשרוני נובעת מ-(1): כל מקדם $c_j$ מקיים $0\le c_j\le 3\le 9$, ולכן הוא ספרה חוקית בבסיס $10$ ואין העברה לעמודה שמשמאלה. זו כל המשמעות של "אין נשאות": בסיס $10$ נבחר גדול דיו מכדי שסכום עמודה כלשהי יגלוש. (למעשה כל בסיס $\ge 4$ היה מספיק; בסיס $10$ נבחר מטעמי נוחות כתיבה בלבד.)

(3) $\displaystyle\sum_{j=1}^m c_j 10^{m-j}\le \sum_{j=1}^m 3\cdot 10^{m-j} = 3\cdot\frac{10^m-1}{9}=\frac{10^m-1}{3}<10^m$. $\blacksquare$

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

מסקנה 4.2 (קריטריון הספרות)

בסימוני למה 4.1, מתקיים $\sum_{x\in I} x = S$ אם ורק אם $|U|=K$ וגם $c_j=2$ לכל $1\le j\le m$.

הוכחה. ($\Leftarrow$) הצבה ישירה בזהות של למה 4.1(2).

($\Rightarrow$) נסמן $L=\sum_{j} c_j 10^{m-j}$ ו-$L'=\sum_j 2\cdot 10^{m-j}$. לפי למה 4.1(3) מתקיים $0\le L<10^m$, ובאותו חשבון גם $0\le L'<10^m$. מן ההנחה, $|U|\cdot 10^m + L \;=\; K\cdot 10^m + L' \quad\Longrightarrow\quad \bigl(|U|-K\bigr)\cdot 10^m \;=\; L'-L .$ אגף ימין מקיים $|L'-L|<10^m$, ואגף שמאל הוא כפולה שלמה של $10^m$; לכן שני האגפים אפס. מכאן $|U|=K$ וגם $L=L'$. שני הסכומים כתובים במקדמים שכולם בין $0$ ל-$9$ (למה 4.1(1), ו-$2\le 9$), ולכן מיחידות ההצגה בבסיס $10$ נובע $c_j=2$ לכל $j$. $\blacksquare$

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

הוכחת המשפט

זמן ריצה. האלגוריתם עובר לולאה אחת על הקודקודים ולולאה אחת על הקשתות, וכותב לכל אחד מהם מספר בן $m+1$ ספרות; בנוסף הוא כותב את $S$. סך גודל הפלט הוא $O\bigl((|V|+m)\cdot m + \log K\bigr)$ ספרות — פולינומי בגודל הקלט. בדיקת "האם $v\in e_j$" היא $O(1)$ בייצוג רשימות שכנויות, ולכן זמן החישוב פרופורציוני לגודל הפלט. המרצה ציין שהאלגוריתם רץ למעשה בזמן ליניארי בגודל הפלט ([01:11:00]).

הערה חשובה שנאמרה רק ברמז: הערך של כל מספר שנבנה הוא בסדר גודל $10^{m}$ — מעריכי בגודל הקלט! זו אינה בעיה, מפני שהרדוקציה נדרשת לרוץ בזמן פולינומי, וכתיבת מספר כזה עולה רק $m+1$ ספרות. זו בדיוק ההבחנה של הגדרה 3, מן הצד השני שלה: הרדוקציה חוקית רק מפני שמותר לה לייצר מספרים בעלי ערך אדיר באורך ייצוג צנוע.

נכונות, כיוון ראשון: $(G,K)\in \mathrm{VC} \Rightarrow$ הפלט ב-$\mathrm{SUBSET\text{-}SUM}$.

נניח $(G,K)\in \mathrm{VC}$ (לאחר צעד 0 מתקיים $K\le|V|$). לפי הדיון על צעד 0 קיים כיסוי בקודקודים $U\subseteq V$ עם $|U|=K$ בדיוק. נסמן $I_1=\{a_u \mid u\in U\}$.

נסכום את המספרים ב-$I_1$. בעמודה $d$ כל אחד מהם תורם $1$, ובחרנו בדיוק $K$ קודקודים, ולכן התרומה שם היא $K$ — בדיוק כמו ב-$S$.

כעת יהי $1\le j\le m$. מכיוון ש-$U$ כיסוי, לפחות אחד מקצות $e_j$ שייך ל-$U$; ומכיוון של-$e_j$ יש רק שני קצוות, לכל היותר שניים שייכים. לכן סכום הספרות בעמודה $j$ הוא $1$ או $2$.

נגדיר $I_2$ כך: לכל $j$ שעבורו סכום העמודה יצא $1$, נוסיף ל-$I_2$ את המספר $a_{e_j}$ המתאים לאותה קשת. המספר $a_{e_j}$ מוסיף $1$ בדיוק לעמודה $j$ ואפס לכל עמודה אחרת (כולל עמודת $d$), ולכן הוא "מתקן" מ-$1$ ל-$2$ בלי לגעת בשום מקום אחר. שימו לב שהוא אינו יכול לתקן מ-$0$ ל-$2$ — וזה מדויק: המצב $0$ לא ייתכן כאן דווקא מפני ש-$U$ כיסוי ([01:18:47]).

נקבל $c_j=2$ לכל $j$ ו-$|U|=K$, ולפי מסקנה 4.2 סכום המספרים ב-$I_1\cup I_2$ הוא בדיוק $S$.

נכונות, כיוון שני: הפלט ב-$\mathrm{SUBSET\text{-}SUM}$ $\Rightarrow (G,K)\in \mathrm{VC}$.

הערה: כיוון זה אינו כתוב בסיכום, ובהרצאה הוא נאמר בעל פה בלבד ([01:29:33]) עם המשפט "אתם רוצים באמת להרגיש שאתם מבינים את זה — תכתבו את זה". הנה הכתיבה.

נניח שקיימת תת-קבוצה $I$ של המספרים שנבנו שסכומה בדיוק $S$. נסמן, כמו בלמה 4.1, $U=I\cap\{a_v\}_{v\in V}$ (מזוהה עם קבוצת קודקודים). לפי מסקנה 4.2 מתקיים

$|U|=K, \qquad c_j = \bigl|\{v\in U: v\in e_j\}\bigr| + [\,a_{e_j}\in I\,] = 2 \quad \text{for every } 1\le j\le m .$

יהי $1\le j\le m$. המחובר $[\,a_{e_j}\in I\,]$ הוא לכל היותר $1$, שכן יש מספר אחד בלבד המתאים לקשת $e_j$ ולכן אפשר לבחור אותו לכל היותר פעם אחת. לכן

$\bigl|\{v\in U: v\in e_j\}\bigr| \;=\; 2 - [\,a_{e_j}\in I\,] \;\ge\; 1 .$

כלומר לכל קשת $e_j$ יש לפחות קצה אחד ב-$U$, ולכן $U$ הוא כיסוי בקודקודים של $G$. גודלו $|U|=K\le K$, ולכן $(G,K)\in \mathrm{VC}$. $\blacksquare$

מסקנה. $\mathrm{VC}$ היא NP-hard (שיעור 10), ולפי הטרנזיטיביות של $\le_p$ נובע ש-$\mathrm{SUBSET\text{-}SUM}$ היא NP-hard. יחד עם משפט 3 מתקבל ש-$\mathrm{SUBSET\text{-}SUM}$ היא NP-complete.

משפט 5: אלגוריתם התכנון הדינמי אינו אלגוריתם פולינומי

בקורס האלגוריתמים ראינו אלגוריתם תכנון דינמי המכריע את $\mathrm{SUBSET\text{-}SUM}$ בזמן $O(n\cdot S)$ (טבלה בגודל $n\times S$). האלגוריתם הזה אינו פולינומי בגודל הקלט.

הוכחה. נתבונן במשפחת קלטים שבה המספרים גדולים משמעותית מכמותם: לכל $1\le i\le n$ מתקיים $2^{n}\le a_i\le 2^{2n}$, וכן $2^{n}\le S\le 2^{2n}$.

גודל הקלט. יש $n+1$ מספרים, וכל אחד מהם דורש לכל היותר $2n$ ביטים. לכן אורך הקלט הוא לכל היותר $(n+1)\cdot 2n = O(n^2)$ ביטים.

זמן הריצה. $n\cdot S \ge n\cdot 2^{n}$, שכן $S\ge 2^n$.

ההשוואה. נסמן ב-$N$ את אורך הקלט; אז $N=\Theta(n^2)$, כלומר $n=\Theta(\sqrt N)$, וזמן הריצה הוא לפחות $2^{\Omega(\sqrt N)}$. הפונקציה $2^{\sqrt N}$ גדולה אסימפטוטית מכל פולינום ב-$N$, ולכן זמן הריצה אינו פולינומי בגודל הקלט. $\blacksquare$

מה זה בדיוק ([00:46:11], [00:47:13]). הביטוי $2^{\sqrt N}$ הוא לא בדיוק "מעריכי" — זה מעריכי בשורש של גודל הקלט — אבל הוא בוודאות אינו פולינומי. המרצה הקפיד על הניסוח הזה. אלגוריתם כזה נקרא pseudo-polynomial: פולינומי בערך המספרים ולא באורך ייצוגם.

המסקנה על הבעיה. מכאן ש-$\mathrm{SUBSET\text{-}SUM}$ היא NP-hard חלשה (weakly NP-hard): אם היו מייצגים את המספרים בבסיס אונרי, אורך הייצוג היה שווה לערך, אלגוריתם ה-$O(n\cdot S)$ היה נעשה פולינומי, והבעיה הייתה נופלת ל-$P$. שימו לב שזה אינו סותר את משפט 4: הרדוקציה שם מייצרת מספרים שערכם כ-$10^{m}$, וכתיבתם בבסיס אונרי הייתה דורשת מקום מעריכי — כלומר הרדוקציה אינה רדוקציה ל-$\mathrm{SUBSET\text{-}SUM}$ האונרית.

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

דוגמה 1: מעקב מלא אחרי הרדוקציה $\mathrm{VC} \le_p \mathrm{SUBSET\text{-}SUM}$

זהו בדיוק המופע שהמרצה הריץ על הלוח והופיע בעמוד 5 בסיכום.

הגרף. $V=\{1,2,3,4,5\}$, ריבוע $1\!-\!2\!-\!3\!-\!4\!-\!1$ ובתוכו קודקוד $5$ המחובר ל-$2$ ול-$4$. הקשתות ממוספרות:

$e_1=\{1,2\},\quad e_2=\{2,3\},\quad e_3=\{3,4\},\quad e_4=\{1,4\},\quad e_5=\{2,5\},\quad e_6=\{4,5\},\qquad K=3 .$

כאן $n=|V|=5$, $m=|E|=6$, וכל מספר הוא בן $7$ ספרות.

המספרים שהאלגוריתם מייצר.

בקריאה כמספרים: $a_3 = 1011000$, $a_{e_5}=0000010$, $S=3222222$. שורות הקשתות הן בדיוק מטריצת היחידה ([01:24:48]), ושורת קודקוד היא שורת מטריצת השכנויות קודקוד–קשת עם $1$ מוביל.

כיוון ראשון (מכיסוי לסכום). ניקח את הכיסוי $U=\{2,4,5\}$, שגודלו $|U|=3=K$. ואכן הוא כיסוי: $e_1$ מכוסה על ידי $2$, $e_2$ על ידי $2$, $e_3$ על ידי $4$, $e_4$ על ידי $4$, $e_5$ על ידי $2$ ו-$5$, ו-$e_6$ על ידי $4$ ו-$5$.

$I_1=\{a_2,a_4,a_5\},\qquad a_2+a_4+a_5 \;=\; 3\,1\,1\,1\,1\,2\,2 .$

בדיקה עמודה-עמודה: $d$: $1+1+1=3$. $e_1$: $1+0+0=1$. $e_2$: $1+0+0=1$. $e_3$: $0+1+0=1$. $e_4$: $0+1+0=1$. $e_5$: $1+0+1=2$. $e_6$: $0+1+1=2$. אף עמודה לא עברה את $2$ — כמובטח בלמה 4.1.

העמודות $e_1,e_2,e_3,e_4$ יצאו $1$, ולכן

$I_2=\{a_{e_1},a_{e_2},a_{e_3},a_{e_4}\},$

ובחיבור:

$3111122+0100000+0010000+0001000+0000100 \;=\; 3222222 \;=\; S. \qquad\checkmark$

כיוון שני (מסכום לכיסוי). נניח שמישהו נותן לנו את הקבוצה $\{a_2,a_4,a_5,a_{e_1},a_{e_2},a_{e_3},a_{e_4}\}$ ואומר שסכומה $S$. לפי מסקנה 4.2 אנחנו קוראים מן הסכום: הבלוק השמאלי הוא $3$, ולכן נבחרו בדיוק $3$ מספרי קודקוד — הקודקודים $\{2,4,5\}$. בכל עמודת קשת הסכום הוא $2$; למשל בעמודה $e_3$ תרם $a_4$ אחת ו-$a_{e_3}$ אחת. מכיוון ש-$a_{e_3}$ יכול לתרום לכל היותר $1$, בהכרח לפחות אחד מקצות $e_3$ נמצא בקבוצה — וזה $4$. חוזרים על אותו שיקול לכל אחת משש העמודות ומקבלים ש-$\{2,4,5\}$ מכסה את כל הקשתות, כלומר כיסוי בקודקודים בגודל $3\le K$. $\checkmark$

מה היה קורה בלי אי-נשאות? נניח לרגע שהיינו עובדים בבסיס $2$ ובעמודה של $e_5$ היו שלושה מספרים עם $1$. אז $1+1+1=3$ היה נכתב כ-$11_2$, כלומר נשא $1$ לעמודה של $e_4$, וסכום סופי "נכון" היה יכול להתקבל מקבוצה שאינה כיסוי כלל. זו בדיוק הסיבה שאנחנו סופרים כמה אחדות יכולות להצטבר בעמודה (לכל היותר $3$) ובוחרים בסיס גדול מזה.

דוגמה 2: הדוגמה עם $7$ קשתות שנמחקה על הלוח

בעמוד 4 בסיכום מופיע אותו גרף עם $7$ קשתות, ו-$a_3=10110001$, $S=32222222$. בהקלטה ([01:22:44], [01:23:15]) המרצה אומר "מחקתי קשת אחת כדי שזה ייכנס לי ללוח" — כלומר עמוד 4 מתעד את המצב לפני המחיקה ועמוד 5 את המצב הסופי. שתי הגרסאות תקינות; הדוגמה המלאה והמאומתת היא זו שבדוגמה 1.

דוגמה 3: מעקב מלא אחרי הרדוקציה $\mathrm{3COL} \le_p \mathrm{4COL}$

מופע חיובי. ניקח $G=C_5$, המעגל באורך $5$: $V=\{1,2,3,4,5\}$ והקשתות $12,23,34,45,51$.

הבנייה. האלגוריתם מוסיף קודקוד $\hat v$ ומחבר אותו לכל חמשת הקודקודים. הגרף המתקבל $\hat G$ הוא הגלגל בעל $6$ קודקודים ו-$5+5=10$ קשתות.

מ-$\mathrm{3COL}$ ל-$\mathrm{4COL}$. מעגל אי-זוגי אינו $2$-צביע אבל כן $3$-צביע; ניקח

$f(1)=1,\; f(2)=2,\; f(3)=1,\; f(4)=2,\; f(5)=3 .$

בדיקה: $12: 1\ne2$, $23: 2\ne1$, $34: 1\ne2$, $45: 2\ne3$, $51: 3\ne1$ — צביעה חוקית. לפי הבנייה שבמשפט 2 נגדיר $g$ שמסכימה עם $f$ על $V$ ומקצה $g(\hat v)=4$. חמש הקשתות הישנות בסדר כי $f$ חוקית; חמש הקשתות החדשות בסדר כי $\hat v$ לבדו נושא את הצבע $4$. לכן $\hat G\in \mathrm{4COL}$. $\checkmark$

מ-$\mathrm{4COL}$ ל-$\mathrm{3COL}$. נניח שקיבלנו את הצביעה החוקית

$g(1)=2,\; g(2)=3,\; g(3)=2,\; g(4)=3,\; g(5)=4,\; g(\hat v)=1 .$

כאן $g(\hat v)\ne 4$, ולכן נפעיל את שלב "ללא הגבלת הכלליות": נחליף בין שמות הצבעים $1$ ו-$4$ ונקבל $g'(\hat v)=4$, $g'(5)=1$, ושאר הערכים ללא שינוי. החלפת שמות צבעים שומרת על חוקיות, שכן היא פרמוטציה חח"ע של הטווח. כעת $f=g'|_V$ נותנת

$f(1)=2,\; f(2)=3,\; f(3)=2,\; f(4)=3,\; f(5)=1 ,$

וכל הערכים אכן ב-$\{1,2,3\}$ — בדיוק מפני שכל קודקוד ב-$V$ שכן של $\hat v$ ולכן אסור לו לקבל $4$. הצביעה חוקית על כל חמש הקשתות של $C_5$, ולכן $G\in \mathrm{3COL}$. $\checkmark$

מופע שלילי. ניקח $G=K_4$. אז $\hat G=K_5$. אכן $K_4\notin \mathrm{3COL}$ (בקליק בגודל $n$ דרושים $n$ צבעים) וגם $K_5\notin \mathrm{4COL}$ מאותו נימוק — הרדוקציה שולחת "לא" ל"לא", כנדרש. $\checkmark$

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

תרגיל 1 (נפתר בכיתה): מדוע הזהות אינה רדוקציה מ-$\mathrm{3COL}$ ל-$\mathrm{4COL}$?

פתרון. צריך למצוא גרף שהוא $4$-צביע ואינו $3$-צביע. הקליק $K_4$ הוא כזה: הוא $4$-צביע כי אפשר לתת לכל קודקוד צבע משלו, והוא אינו $3$-צביע כי בקליק כל שני קודקודים מחוברים ולכן דרושים לפחות $4$ צבעים. לכן $\mathrm{id}(K_4)=K_4\in \mathrm{4COL}$ אך $K_4\notin \mathrm{3COL}$, בסתירה לתנאי הרדוקציה.

תרגיל 2 (נפתר בכיתה): האם היה אפשר לעשות רדוקציה מ-$\mathrm{IS}$ או מ-$\mathrm{CLIQUE}$ במקום מ-$\mathrm{VC}$?

פתרון ([00:54:41]). כן. יש רדוקציה מיידית $\mathrm{IS} \le_p \mathrm{VC}$: הקבוצה $U$ היא כיסוי בקודקודים אם ורק אם $V\setminus U$ היא קבוצה בלתי תלויה, ולכן מספיק להעביר $(G,K)\mapsto (G,|V|-K)$. אפשר לשלב אותה בחזית הרדוקציה שלנו ולקבל $\mathrm{IS} \le_p \mathrm{SUBSET\text{-}SUM}$ ישירות. מ-$\mathrm{CLIQUE}$ עוברים תחילה לגרף המשלים ואז ל-$|V|-K$. המרצה הדגיש שהבחירה ב-$\mathrm{VC}$ שרירותית לחלוטין ונובעת מכך שזו הרדוקציה הקלאסית בספרות ([00:55:43]) — לא מפני שהאחרות שגויות, אלא מפני שהן מוסיפות רעש להוכחה.

תרגיל 3 (שיעורי בית): $\mathrm{DTime}(n^{10})$ אינה סגורה לרדוקציות זמן פולינומי

פתרון. ראו ההערה בסוף משפט 1: בוחרים $B\in \mathrm{DTime}(n^{10})$ לא-טריוויאלית, לוקחים ממשפט ההיררכיה $A\in P\setminus \mathrm{DTime}(n^{10})$, ומקבלים ממשפט 1 ש-$A\le_p B$ בעוד $A\notin \mathrm{DTime}(n^{10})$.