VC ≤p SUBSET-SUM | Complexity Atlas

הבנייה

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

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

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

באלגברה: $a_v=10^{m}+\sum_{j=1}^{m}[\,v\in e_j\,]\cdot10^{\,m-j},\qquad a_{e_i}=10^{\,m-i},\qquad S=K\cdot10^{m}+\sum_{j=1}^{m}2\cdot10^{\,m-j}.$

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

המחשה

G = P₅: |V| = 5, m = |E| = 4K = 3

מספר קודקוד a_v

שורה לכל מספר שנבנה; עמודה אחת ל־d ועמודה לכל קשת; השורות האחרונות הן סכומי העמודות וסכום היעד.
מספר	d	e₁	e₂	e₃	e₄	ערך

צעד 0 — "לכל היותר K" הופך ל"בדיוק K"אם K > |V| מחליפים את K ב־|V|. כיסוי בגודל ≤ K תמיד אפשר להשלים לגודל K בדיוק, ולכן כפיית K בעמודה d אינה מזיקה.

קלט

גרף, מספור קשתות ו־K

ניקח את המסלול על חמישה קודקודים, עם m = |E| = 4 קשתות ממוספרות e₁ = (v₁,v₂), e₂ = (v₂,v₃), e₃ = (v₃,v₄), e₄ = (v₄,v₅), ונשאל אם יש כיסוי קודקודים בגודל לכל היותר K = 3.

צעד 0 של האלגוריתם: אם K > |V|, מחליפים את K ב־|V|. לאחר מכן מותר לבנייה לכפות בדיוק K במקום לכל היותר K — הוספת קודקודים לכיסוי משאירה אותו כיסוי, ולכן כיסוי קטן יותר מושלם לגודל K בדיוק; ואם K > |V| התשובה חיובית ממילא.

הרדוקציה בונה את המספרים מהגרף ומ־K בלבד. היא אינה מחפשת כיסוי — ניסוח הבנייה במונחי הפתרון הוא אותו "חטא כבד" שנפסל ב־3COL ≤p 4COL.

נכונות — שני הכיוונים

VC ∈ ⟹ SUBSET-SUM ∈

למה 4.1 (אי-נשאות) — הצעד שבלעדיו כלום לא עובד. תהי $I$ תת-קבוצה כלשהי של המספרים שנבנו, ונסמן $U=I\cap\{a_v\}$ (מזוהה עם קבוצת קודקודים) ולכל $j$ $c_j=\bigl|\{v\in U:v\in e_j\}\bigr|+[\,a_{e_j}\in I\,].$ אזי (1) $0\le c_j\le3$ ; (2) $\sum_{x\in I}x=|U|\cdot10^m+\sum_j c_j 10^{m-j}$ , וזהו בדיוק הייצוג העשרוני — החיבור אינו נושא באף עמודת קשת; (3) $\sum_j c_j10^{m-j}<10^m$ .

הוכחה. (1) לקשת $e_j$ יש בדיוק שני קצוות, ולכן לכל היותר שני מספרי קודקוד נושאים $1$ בעמודה $j$ , ובנוסף בדיוק מספר קשת אחד; סך האחדות $\le3$ . (2) פתיחת הסכום וקיבוץ לפי חזקות $10$ ; היות $c_j\le3\le9$ ספרה חוקית מבטיח שאין העברה שמאלה. (3) $\sum_j 3\cdot10^{m-j}=\frac{10^m-1}{3}<10^m$ . $\square$

מסקנה 4.2 (קריטריון הספרות). $\sum_{x\in I}x=S$ אם ורק אם $|U|=K$ וגם $c_j=2$ לכל $j$ . הוכחה של $\Rightarrow$ : נסמן $L=\sum_j c_j10^{m-j}$ ו- $L'=\sum_j2\cdot10^{m-j}$ ; שניהם ב- $[0,10^m)$ . מההנחה $(|U|-K)\cdot10^m=L'-L$ , כאשר אגף ימין קטן בערך מוחלט מ- $10^m$ ואגף שמאל כפולה שלמה של $10^m$ — לכן שניהם אפס. $\square$

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

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

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

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

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

SUBSET-SUM ∈ ⟹ VC ∈

נניח שקיימת תת-קבוצה $I$ של המספרים שנבנו שסכומה בדיוק $S$ . נסמן, כמו בלמה 4.1, $U=I\cap\{a_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{לכל }1\le j\le m .$

יהי $j$ . המחובר $[\,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}$ .

סיבוכיות הרדוקציה

זמןO(|x|²)

מקוםO((|V| + m)·m)

גודל הפלטO((|V| + m)·m + log K) digits

לולאה אחת על הקודקודים ואחת על הקשתות, כשלכל אחד נכתב מספר בן $m+1$ ספרות; בנוסף נכתב $S$ . בדיקת "האם $v\in e_j$ " היא $O(1)$ ברשימות שכנויות, ולכן זמן החישוב פרופורציוני לגודל הפלט.

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

מה זה קונה

$\mathrm{SUBSET\text{-}SUM}$ היא NP-שלמה. מכאן ממשיכה השרשרת המספרית: $\mathrm{SUBSET\text{-}SUM}\le_p\mathrm{PARTITION}\le_p\mathrm{BIN\text{-}PACKING}$ .

מלכודות

בלי אי-הנשאות אין הוכחה. אילו סכום עמודה כלשהי היה מגיע ל- $10$ או יותר, הוא היה מעביר $1$ שמאלה, וסכום כולל שנראה נכון היה יכול להתקבל מצירוף עמודות שגוי לגמרי — למשל $10$ אחדות בעמודה אחת "מתחזות" לספרה $1$ בעמודה שכנה. כל הטיעון נשען על כך ששוויון סכומים גורר שוויון בכל ספרה בנפרד. (למעשה כל בסיס $\ge4$ היה מספיק; בסיס $10$ נבחר מטעמי נוחות בלבד.)
$K$ נכתב כבלוק של ספרות ולא כספרה בודדת. מספר הקודקודים הנבחרים $|U|$ עשוי להיות $10$ או יותר, ואז "הספרה" השמאלית איננה ספרה. הטיעון של מסקנה 4.2 אינו מניח דבר על $|U|$ — הוא רק מנצל שכל מה שמתחת ל- $10^m$ אינו מגיע ל- $10^m$ .
הרדוקציה בונה מספרים מהגרף ומ- $K$ בלבד ואינה מחפשת כיסוי. אותו "חטא כבד" שנפסל ב- $\mathrm{3COL}\le_p\mathrm{4COL}$ חוזר כאן: אסור לנסח את הבנייה במונחים של הפתרון.

השרשרת

נשענת על

IS ≤p VC

משמשת בהמשך ל

SUBSET-SUM ≤p PARTITION

מאיפה זה נקרא

שיעור 11משפט 4 (לב השיעור): $\mathrm{VC} \le_p \mathrm{SUBSET\text{-}SUM}$
תרגיל מודרךsubset-sum-encoding

כיוון $\Leftarrow$ אינו כתוב בסיכום הכתוב, ובהרצאה הוא נאמר בעל פה בלבד עם ההערה "אתם רוצים באמת להרגיש שאתם מבינים את זה — תכתבו את זה". הכתיבה כאן היא ההשלמה.