רדוקציה מ־Subset Sum ל־Partition

איזון תת־קבוצה מול המשלימה בלי להניח שהיעד הוא מחצית הסכום.

שאלה

עבור שלמים חיוביים $a_1,\ldots,a_m$ ויעד $T$, בצעו רדוקציה מ-SUBSET-SUM ל-PARTITION. טפלו במקרה $T>\sum_i a_i$, והגדירו PARTITION כחלוקת הרב־קבוצה לשני חלקים שווי־סכום. הוכיחו נכונות וגודל קידוד פולינומי.

דרישות קדם

נדרשת שליטה בהגדרות היחידה ובניתוח אורכי קידוד. יש להבחין בין טענה מותנית, רדוקציה ואלגוריתם.

רמז 1

נסמן $S=\sum_i a_i$ ונוסיף מספרים היוצרים היסט מתאים.

רמז 2

הזוג $S+T,2S-T$ נותן סכום כולל $4S$.

רמז 3

שני המספרים החדשים אינם יכולים להיות באותו צד.

פתרון מלא

נסמן $S=\sum_i a_i$. אם $T>S$, נחזיר מופע לא קבוע, למשל $\{1,2\}$. אחרת, עבור $0<T\le S$, נחזיר

סכום כל המספרים הוא $4S$, ולכן בכל חלוקה שווה סכום כל צד $2S$.

אם תת־קבוצה מקורית סכומה $T$, נשים אותה יחד עם $2S-T$ ונקבל $2S$. שאר המספרים המקוריים יחד עם $S+T$ נותנים $(S-T)+(S+T)=2S$.

להפך, שני המספרים החדשים אינם יכולים להיות באותו צד, כי סכומם $3S>2S$. לכן הם מופרדים. בצד המכיל $2S-T$, סכום המספרים המקוריים חייב להיות בדיוק $T$, וזו תת־קבוצה פותרת.

את $S$ מחשבים בחיבורים בינאריים פולינומיים. המספרים החדשים לכל היותר $3S$, ו-$\log S$ פולינומי באורך הקלט, ולכן גם אורך הפלט פולינומי. יש לשמר ריבוי של ערכים שווים. במקרה $T=0$ התשובה המקורית כן בגלל הקבוצה הריקה, ולכן אפשר להחזיר מופע כן קבוע ולהימנע מהכנסת אפס כאשר ההגדרה דורשת חיוביות.

נקודות בדיקה

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

טעויות נפוצות

• הוספת $S-2T$ בלי טיפול בסימן.
• אי־הוכחת הפרדת המספרים החדשים.
• מדידת גודל לפי ערך ולא מספר ביטים.

מקורות ואימות

• 2026 transcript 15
• Garey-Johnson, SP12
• הערת כיסוי הקורפוס: אין כיסוי ישיר בסיכום הממוזג.
• מיפוי קטלוג: data/exercises.json; הניסוח והפתרון עצמאיים; הגשות אישיות אינן מקור סמכות.

הערת מקור וביטחון

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

פתיחה בגלריית ההמחשות: סכום תת־קבוצה → חלוקה