בעיית הסכומים החלקיים

במדעי המחשב, בעיית הסכום החלקי (Subset Sum Problem) היא בעיה חשובה בתורת הסיבוכיות ובקריפטוגרפיה. הבעיה היא כזו: בהינתן קבוצה של מספרים שלמים, האם קיימת תת-קבוצה לא ריקה שלה שסכום איבריה הוא אפס? לדוגמה, בהינתן הקבוצה {7-,3-,2-,8,5} כקלט לבעיה, התשובה תהיה חיובית, והקבוצה שסכומה אפס תהיה {2-,3-,5}. בעיה זו היא NP-שלמה.

בעיה שקולה לבעיה זו היא כדלקמן: בהינתן קבוצת מספרים שלמים I, ומספר נוסף s, האם קיימת תת-קבוצה לא ריקה של I שסכום איבריה הוא s?

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

אלגוריתמים לפתרון הבעיה

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

אלגוריתם לפתרון בזמן אקספוננציאלי

יש מספר דרכים לפתור את בעיית הסכום החלקי בזמן אקספוננציאלי בגודל הקבוצה. האלגוריתם הנאיבי ביותר יבדוק את כל תתי הקבוצות האפשריות, ויבדוק האם סכומן מתאים להגדרת הבעיה. זמן הריצה של אלגוריתם כזה יהיה $O(2^{n}n)$, שכן ישנן $2^{n}$ תתי קבוצות שהאלגוריתם יבדוק, ובכל קבוצה כזו יש לכל היותר $n$ איברים שהאלגוריתם יסכום.

קיים גם אלגוריתם טוב יותר שרץ בזמן $O(2^{\frac {n}{2}})$ שהוצג לראשונה על ידי הורוביץ וסהני בשנת 1972. האלגוריתם פועל באופן הבא:

1. נחלק את הקלט לקבוצות T ו-U בגודל ${\frac {n}{2}}$ כל אחת.
2. נחשב את הקבוצות A ו-B כאשר A היא קבוצת כל הזוגות הסדורים $(a_{i},p_{i})$ כך ש-$p_{i}$ הוא קידוד של בחירת איברים ב-T שסכומם הוא $a_{i}$ ובאותו אופן B היא קבוצת הזוגות $(b_{i},q_{i})$ עבור U.
3. נמיין את A ו-B בסדר עולה.
4. נחפש זוג $(a_{i},p_{i})$ ו-$(b_{j},q_{j})$ כך שמתקיים $a_{i}+b_{j}=s$.

אלגוריתם זה דורש מקום $O(2^{\frac {n}{2}})$ מאחר ש-A ו-B הן בגודל כזה כל אחת (הן מייצגות את קבוצות החזקה של קבוצות בגודל ${\frac {n}{2}}$). כדי להראות את הטענה לגבי זמן הריצה, צריך להראות שניתן לבנות את הקבוצות באופן ממוין בזמן $O(2^{\frac {n}{2}})$ ולחפש זוג מתאים בזמן דומה. הזמן של המיון נובע מהדרך בה בונים את A ו-B. את החיפוש ניתן לבצע בזמן הדרוש באופן הבא:

1. נסמן $i=1,j=|B|$
2. אם $a_{i}+b_{j}>s$, נסמן $j=j-1$
3. אחרת, אם $a_{i}+b_{j}<s$, נסמן $i=i+1$
4. אחרת, נחזיר את איחוד הקבוצות המקודדות על ידי $p_{i}$ ו-$q_{j}$

אלגוריתם לפתרון בזמן פסאודו פולינומי

פתרון בזמן פסאודו פולינומי אומר שעבור בעיה זהה בה הקלט הוא בבסיס אונרי קיים פתרון הרץ בזמן פולינומי.

הפתרון לבעיה הזו משתמש בתכנון דינמי. נניח שהקלט הוא מהצורה $X_{1},...,X_{n}$, ועלינו לבדוק האם קיימת תת-קבוצה שסכום איבריה הוא אפס. יהא $A$ הסכום של כל האיברים השליליים בקבוצה, ויהא $B$ הסכום של כל האיברים החיוביים בה.

נגדיר את הפעולה הבוליאנית $Q(i,s)$ להיות התשובה לשאלה: "האם קיימת תת-קבוצה של $X_{1},...,X_{i}$ שסכום איבריה הוא $s$ ?". ברור כעת כי פתרון הבעיה הוא $Q(n,0)$.

נבחין כי עבור $A>s,s>B$ מתקיים $\forall i:Q(i,s)=false$. כעת, ניצור טבלה בגודל $n*(B-A)$, כאשר הערך בנקודה $(i,j)$ יהיה $Q(i,A+j)$, ונמלא את הטבלה מלמטה למעלה ומשמאל לימין באמצעות הרקורסיה הבאה:

• מקרה הבסיס: $Q(1,s):=(x_{1}==s)$
• עבור $i=2,...,n$: $Q(i,s):=Q(i-1,s)or(x_{i}==s)orQ(i-1,s-x_{i})$

מילוי כל תא לוקח זמן $O(1)$ כי ערכי הטבלה שהוא משתמש בהן בפסוק הלוגי ידועים כבר מחישובים קודמים, ולכן זמן מילוי הטבלה יהיה $O(n*(B-A))$.

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

אלגוריתם קירוב בזמן פולינומי

אלגוריתם קירוב לבעיית הסכום החלקי הוא כדלהלן: בהינתן קבוצת מספרים $X_{1},...,X_{n}$, מספר s, ומספר c>0 כלשהו, נרצה שהפלט יהיה:

• "לא", אם לא קיימת תת-קבוצה שמסתכמת למספר בין $(1-c)s$ ל$s$.
• "כן", אם לא קיימת תת-קבוצה שמסתכמת ל$s$.
• "כן" \ "לא", אחרת.

אם כל המספרים הם לא שליליים, ניתן לפתור זאת בזמן פולינומי ב-$n$ וב-${\frac {1}{c}}$.

נשים לב שבבעיה המקורית, אם כל סכום אפשרי של מספרים יכול להיכתב באמצעות P ביטים, אם נפתור את הבעיה המקורית באלגוריתם הקירוב עם $c=2^{-P}$, נפתור את הבעיה בדיוק. לכן אלגוריתם זה הוא פתרון מדויק של הבעיה כשהוא רץ בזמן פולינומי ב-$n$ וב-$2^{P}$ (כלומר, אקספוננציאלי ב-$P$).

האלגוריתם המקורב לבעיה הוא:

initialize a list S to contain one element 0.
 for each i from 1 to n do
 let T be a list consisting of xi + y, for all y in S
 let U be the union of T and S
 sort U
 make S empty
 let y be the smallest element of U
 add y to S
 for each element z of U in increasing order do
 //trim the list by eliminating numbers close to one another
 //and throw out elements greater than s
 if y + cs/n < z ≤ s, set y = z and add z to S
 if S contains a number between (1 − c)s and s, output yes, otherwise no

האלגוריתם רץ בזמן פולינומי כיוון שהרשימות S, T, U תמיד בגודל פולינומי ב-n וב-${\frac {1}{c}}$, ולכן גם כל הפעולות שנעשות עליהן מתבצעות בזמן פולינומי. גודל הרשימות אכן נשאר פולינומי היות שאנו מוסיפים עצמים ל-S אם הם גדולים מהעצם הקודם ב-${\frac {cs}{n}}$ וקטנים מ-$S$. הצעד שמוודא שההפרש בין כל שני עצמים שמתווספים הוא לפחות ${\frac {cs}{n}}$ מוודא שברשימה יש לכל היותר ${\frac {n}{c}}$ עצמים.

האלגוריתם נכון כיוון שבכל צעד מתווספת שגיאה של לכל היותר ${\frac {cs}{n}}$, ובמהלך $n$ שלבים מתווספת שגיאה של לכל היותר $cs$.

ראו גם

• בעיית תרמיל הגב

לקריאה נוספת

• גדי אלכסנדרוביץ', על P=NP מעל חבורות אבליות – מבוא שלם, באתר "לא מדויק", 15 ביוני 2013

קישורים חיצוניים

• בעיית הסכומים החלקיים, באתר MathWorld (באנגלית)