מפת הסיבוכיות
EN
איבר ריפוד יחיד, $|2S-T|$

SUBSET-SUM ≤p PARTITION

SUBSET-SUM≤pPARTITION\mathrm{SUBSET\text{-}SUM}\le_p\mathrm{PARTITION}, ולכן PARTITION\mathrm{PARTITION} היא NP-קשה.

הבנייה

הגזירה — החלק שאסור לדלג עליו. ב-SUBSET-SUM\mathrm{SUBSET\text{-}SUM} יש סכום יעד חיצוני SS, וב-PARTITION\mathrm{PARTITION} אין — היעד מוכתב מבפנים והוא בהכרח חצי מהסכום הכולל. הרדוקציה חייבת "להטמיע את ה-SS פנימה".

נסמן T=∑iaiT=\sum_i a_i. נניח לרגע — רק לצורך החשיבה, לא כחלק מהאלגוריתם — שקיימת II עם ∑i∈Iai=S\sum_{i\in I}a_i=S. הצד השני סוכם ל-T−ST-S. נוסיף איבר bb לצד ה"קטן". במקרה S>T/2S>T/2 נדרוש ∑i∈Iai=S\sum_{i\in I}a_i=S ו-∑i∉Iai+b=S\sum_{i\notin I}a_i+b=S, ומכאן b=S−(∑iai⏟=T−∑i∈Iai⏟=S)=2S−T.b=S-\Bigl(\underbrace{\textstyle\sum_i a_i}_{=T}-\underbrace{\textstyle\sum_{i\in I}a_i}_{=S}\Bigr)=2S-T .

וכאן היופי. הביטוי האמצעי S−∑i∉IaiS-\sum_{i\notin I}a_i אינו ניתן לחישוב על ידי הרדוקציה: הוא תלוי ב-II, שהוא בדיוק האובייקט שאין לנו. אבל הביטוי הסופי 2S−T2S-T תלוי אך ורק בקלט — SS ניתן, ו-TT מחושב בזמן לינארי. שאלת הביניים עברה מ"תלוי בפתרון" ל"תלוי בקלט", ובזה הרדוקציה הפכה לחוקית. סימטרית, אם S<T/2S<T/2 נקבל b=T−2Sb=T-2S.

אלגוריתם RR. על קלט (a1,…,an,S)(a_1,\dots,a_n,S):

  1. חשב T←∑iaiT\leftarrow\sum_i a_i.
  2. אם 2S=T2S=T: החזר (a1,…,an)(a_1,\dots,a_n) ללא שינוי.
  3. אם 2S>T2S>T: החזר (a1,…,an, 2S−T)(a_1,\dots,a_n,\,2S-T).
  4. אם 2S<T2S<T: החזר (a1,…,an, T−2S)(a_1,\dots,a_n,\,T-2S).

ההשוואה נכתבת כ-2S2S מול TT ולא כ-SS מול 12T\tfrac12T כדי להישאר בשלמים גם כאשר TT אי-זוגי; זו אותה השוואה. כאשר TT אי-זוגי מקרה 2 פשוט אינו יכול להתרחש. בשני המקרים האחרים b>0b>0 ממש, בדיוק בגלל תנאי המקרה.

המחשה

בנייה מודרכת

סכום תת־קבוצה → חלוקה

שלב 1 מתוך 6
A = {3, 5, 6, 11}T = 14
מסכום תת־קבוצה לחלוקה באמצעות שני סמנים שנוספיםעמודות פרופורציוניות ל־3, 5, 6, 11 ולסמנים 39 ו־36 ממלאות שתי כפות שסכום כל אחת מהן 50.המספרים משורטטים לפי גודלם35611
מספר מקורי

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

SUBSET-SUM ∈ ⟹ PARTITION ∈

נניח (a1,…,an,S)∈SUBSET-SUM(a_1,\dots,a_n,S)\in\mathrm{SUBSET\text{-}SUM}; קיימת II עם ∑i∈Iai=S\sum_{i\in I}a_i=S. נפצל לפי המקרה שבו פעל האלגוריתם.

מקרה 2S=T2S=T. הפלט הוא (a1,…,an)(a_1,\dots,a_n). הקבוצה II מקיימת ∑i∈Iai=S=T/2\sum_{i\in I}a_i=S=T/2, ולכן ∑i∉Iai=T−T/2=T/2\sum_{i\notin I}a_i=T-T/2=T/2 — שני הצדדים שווים, והפלט ב-PARTITION\mathrm{PARTITION}.

מקרה 2S>T2S>T. הפלט הוא (a1,…,an,b)(a_1,\dots,a_n,b) עם b=2S−T>0b=2S-T>0, וסכומו הכולל T+b=T+2S−T=2ST+b=T+2S-T=2S. נבחר את הצד II עצמו: ∑i∈Iai=S=12(2S)\sum_{i\in I}a_i=S=\tfrac12(2S) — כלומר בדיוק חצי מהסכום החדש. לכן הפלט ב-PARTITION\mathrm{PARTITION}. (הצד השני מורכב מ-{ai}i∉I\{a_i\}_{i\notin I} יחד עם bb, וסכומו (T−S)+(2S−T)=S(T-S)+(2S-T)=S.)

מקרה 2S<T2S<T. הפלט הוא (a1,…,an,b)(a_1,\dots,a_n,b) עם b=T−2S>0b=T-2S>0, וסכומו הכולל T+b=2T−2ST+b=2T-2S. נבחר את הצד I∪{b}I\cup\{b\}: סכומו S+(T−2S)=T−S=12(2T−2S)S+(T-2S)=T-S=\tfrac12(2T-2S) — בדיוק חצי. לכן הפלט ב-PARTITION\mathrm{PARTITION}.

PARTITION ∈ ⟹ SUBSET-SUM ∈

נניח שהפלט ב-PARTITION\mathrm{PARTITION}; קיימת חלוקה של הפלט לשני צדדים שווי סכום. נפצל שוב לפי המקרה.

מקרה 2S=T2S=T. הפלט הוא הקלט המקורי, וחלוקה שווה פירושה שקיים II עם ∑i∈Iai=T/2=S\sum_{i\in I}a_i=T/2=S. מכאן (a1,…,an,S)∈SUBSET-SUM(a_1,\dots,a_n,S)\in\mathrm{SUBSET\text{-}SUM}.

מקרה 2S>T2S>T. הסכום הכולל של הפלט הוא 2S2S, ולכן כל צד סוכם ל-SS. נתבונן בצד שאינו מכיל את איבר הריפוד bb (בדיוק אחד משני הצדדים מכיל אותו). צד זה מורכב אך ורק מאיברים מקוריים, ונסמן ב-II את קבוצת האינדקסים שלהם. אז ∑i∈Iai=S\sum_{i\in I}a_i=S, ולכן (a1,…,an,S)∈SUBSET-SUM(a_1,\dots,a_n,S)\in\mathrm{SUBSET\text{-}SUM}.

מקרה 2S<T2S<T. הסכום הכולל הוא 2T−2S2T-2S, ולכן כל צד סוכם ל-T−ST-S. נתבונן בצד שכן מכיל את b=T−2Sb=T-2S, ונסמן ב-JJ את קבוצת האינדקסים של האיברים המקוריים שבו. אז ∑i∈Jai+(T−2S)=T−S⟹∑i∈Jai=S.\sum_{i\in J}a_i+(T-2S)=T-S\quad\Longrightarrow\quad\sum_{i\in J}a_i=S . לכן (a1,…,an,S)∈SUBSET-SUM(a_1,\dots,a_n,S)\in\mathrm{SUBSET\text{-}SUM}.

בכל שלושת המקרים קיבלנו תת-קבוצה של האיברים המקוריים שסכומה SS, כנדרש.

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

זמןO(|x|²)
מקוםO(|x|)
גודל הפלטO(|x|)

נסמן ב-mm את אורך הייצוג הארוך ביותר מבין a1,…,an,Sa_1,\dots,a_n,S, ובגודל הקלט ∣x∣≥n+m|x|\ge n+m. שלב 1 מבצע n−1n-1 חיבורים; הסכום החלקי אינו עולה על n⋅10mn\cdot10^m ולכן אורכו ≤m+⌈log⁡10n⌉+1\le m+\lceil\log_{10}n\rceil+1, וחיבור אחד לינארי באורכים — סך הכול O(n(m+log⁡n))=O(∣x∣2)O(n(m+\log n))=O(|x|^2). שלבים 2–4 הם השוואה וחיסור בודדים.

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

מה זה קונה

PARTITION\mathrm{PARTITION} היא NP-קשה, וגם ב-NP\mathrm{NP}, ולכן NP-שלמה. משם ממשיכים ל-BIN-PACKING\mathrm{BIN\text{-}PACKING}.

מלכודות

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

  • האלגוריתם מחשב TT ומשווה — וזה מותר. מה שהוא אינו עושה הוא לבדוק אם קיימת תת-קבוצה שסכומה SS, ואינו יכול. האיבר an+1a_{n+1} אינו מסייע להכריע דבר; הוא מבטיח רק ש"אם היה פתרון קודם, יש פתרון עכשיו, ולהפך".

  • הפלט הוא רשימה של n+1n+1 מספרים, לא זוג (מספרים, סכום יעד). כזה בדיוק הוא קלט של PARTITION\mathrm{PARTITION}; איש לא הבטיח ש-nn יישאר קבוע.

השרשרת

נשענת על

משמשת בהמשך ל

מאיפה זה נקרא

  • שיעור 12משפט 2 (לב השיעור): SUBSET-SUM≤pPARTITION\mathrm{SUBSET\text{-}SUM} \le_p \mathrm{PARTITION}
  • תרגיל מודרךpartition-from-subset-sum
  • 2026 '1 מועד 2Subset-SumSubset\text{-}Sum ו-PartitionPartition זו מול זו, והרדוקציה ביניהן.
  • 2025 '2 מועד 1הגדרת PartitionPartition בייצוג עשרוני והוכחת קשיותה.