בעיות שלמות קנוניות

SAT, בעיות גרפים, Subset Sum ותבניות חוזרות ברדוקציות NP-שלמות.

מטרות

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

1. מפת הבעיות

Cook–Levin מתחיל את הרשת:

מ-3SAT עוברים באמצעות גאדג׳טי פסוקיות ועקביות ל-Independent Set ול-CLIQUE. משלים גרף ומשלים קבוצת קודקודים מחברים בין CLIQUE, IS ו-Vertex Cover. ענפים אחרים מובילים לצביעה, Max-Cut, משפחת המילטון, Subset Sum, Partition ו-Bin Packing. Hamiltonian Cycle מובילה באופן טבעי לגרסת ההכרעה של TSP.

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

2. SAT ו-3SAT

SAT שואלת אם לנוסחה בוליאנית יש השמה מספקת. 3SAT מגבילה ל-CNF עם שלושה ליטרלים בכל פסוקית, או לכל היותר שלושה לפי המוסכמה. השמה היא תעודת NP.

פתיחת סוגריים ישירה עלולה ליצור CNF מעריכי. הבנייה הפולינומיאלית מוסיפה משתנה לכל תת־נוסחה וכופה בפסוקיות את ערכה. פסוקית ארוכה מפצלים בעזרת משתני עזר. למשל

מוחלפת ב-

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

3. IS, CLIQUE ו-Vertex Cover

בגרף $G=(V,E)$:

• IS מבקשת לפחות $k$ קודקודים בלתי־שכנים בזוגות.
• CLIQUE מבקשת לפחות $k$ קודקודים שכנים בזוגות.
• VC מבקשת לכל היותר $k$ קודקודים הנוגעים בכל צלע.

כולן ב-NP באמצעות רשימת קודקודים ובדיקה ישירה.

משלים גרף

ממפים $(G,k)$ אל $(\overline G,k)$, כאשר לקודקודים שונים

לכן

בניית המשלים דורשת $O(|V|^2)$ זמן. אין מוסיפים לולאות עצמיות.

קבוצה בלתי־תלויה וכיסוי

מתקיימת הזהות

אם צלע הייתה כולה בתוך $S$, הקבוצה לא הייתה בלתי־תלויה. ולהפך, אם המשלים מכסה כל צלע, אין צלע ששני קצותיה ב-$S$. לכן

במסלול $1-2-3-4$, הקבוצה $\{1,3\}$ בלתי־תלויה, ולכן $\{2,4\}$ כיסוי. בגרף המשלים $\{1,3\}$ קליקה. הפרמטר משתנה ברדוקציה ל-VC אך לא ברדוקציה ל-CLIQUE.

4. צביעה

$k$-COLOR שואלת אם אפשר לצבוע קודקודים ב-$k$ צבעים כך ששכנים יקבלו צבעים שונים. וקטור צבעים הוא תעודה. עבור $k=2$ בודקים דו־צדדיות ב-BFS; לכל $k\ge3$ קבוע הבעיה NP-שלמה.

ברדוקציה מ-3SAT ל-3-COLOR מקובל ליצור משולש צבעי ייחוס True, False, Base. גאדג׳ט משתנה כופה בחירה בין True ל-False, וגאדג׳ט פסוקית ניתן לצביעה בדיוק כאשר לפחות ליטרל אחד אמיתי. ציור אינטואיטיבי אינו הוכחה: יש להראות שכל השמה מספקת מתרחבת לצביעה ושכל צביעה חוקית מפענחת השמה מספקת. יש להבדיל בין 3-COLOR לבין COLORING שבה $k$ חלק מן הקלט.

5. Max-Cut

גרסת ההכרעה מקבלת $(G,K)$ ושואלת אם קיימת חלוקה $(S,V\setminus S)$ שלפחות $K$ צלעות חוצות אותה. הגרסה האופטימלית מבקשת את המקסימום; טענת NP-שלמות מתייחסת לשפת ההכרעה.

החלוקה היא תעודה. במשולש כל חיתוך מכיל לכל היותר שתי צלעות, והחלוקה של קודקוד אחד מול שניים משיגה שתיים. לכן $(K_3,2)$ הוא כן ו-$(K_3,3)$ הוא לא.

גאדג׳טים משתמשים בצלע כחיזוק לכך ששני ערכים נמצאים בצדדים הפוכים. במשקלים בינריים יש לנתח את אורכם. החלפת צלע במשקל $W$ ב-$W$ עותקים היא פולינומיאלית רק אם $W$ חסום פולינומיאלית בגודל הקלט.

6. משפחת המילטון ו-TSP

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

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

ממעגל המילטוני ל-TSP

בהינתן $G=(V,E)$, בונים גרף מלא על $V$ עם

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

הבנייה בגודל $O(|V|^2)$ והמשקלים קטנים. שפת TSP כאן היא: ״האם קיים סיור במשקל לכל היותר $B$?״, ולא בעיית האופטימיזציה.

7. Subset Sum וקידוד מספרי

הקלט הוא מספרים בינריים אי־שליליים $a_1,\ldots,a_m,T$, והשאלה היא האם

וקטור בחירה הוא תעודה וחיבור בינרי פולינומיאלי באורך הקלט.

המופע $\{3,5,6,11\}$ עם יעד 14 הוא כן כי $3+5+6=14$.

קידוד ללא נשיאות

ברדוקציה מ-3SAT מקצים עמודות ספרות למשתנים ולפסוקיות. מספרי בחירת $x_i$ או $\neg x_i$ מסמנים עמודת משתנה ואת הפסוקיות שבהן הליטרל מופיע; מספרי השלמה ממלאים עמודות פסוקית. היעד כופה בחירה אחת לכל משתנה ותרומה מספקת לכל פסוקית.

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

ולכן פולינומיאלי.

זמן פסאודו־פולינומיאלי

טבלת תכנות דינמי בגודל $O(mT)$ אינה בהכרח פולינומיאלית בקלט בינרי: $T$ עשוי להיות מעריכי ב-$\log T$. היא פסאודו־פולינומיאלית. בקידוד אונרי או בערכים חסומים פולינומיאלית המסקנה שונה.

8. Partition ו-Bin Packing

PARTITION שואלת אם אפשר לחלק מספרים לשתי קבוצות בעלות סכום שווה. אם הסכום הכולל $S$ אי־זוגי התשובה לא; אחרת מחפשים תת־קבוצה בסכום $S/2$. זה מסביר את הקשר ל-Subset Sum, אך רדוקציית קושי ממופע Subset Sum כללי דורשת רכיב איזון; הקשר המבני לבדו אינו חץ קושי מלא.

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

יהי $a_1,\ldots,a_m,T$ מופע Subset Sum ונסמן $S=\sum_i a_i$. בקלט פגום או במקרה $T>S$ מחזירים מופע לא קבוע. אחרת מוסיפים שני מספרים:

הסכום הכולל החדש הוא

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

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

הערכים החדשים לכל היותר $3S$. אורכם הבינרי $O(\log S)$, ו-$\log S$ חסום באורך הכולל של הקלט ועוד $O(\log m)$. חישוב הסכום והדפסת שני המספרים פולינומיאליים.

BIN PACKING מקבלת גדלי פריטים, קיבולת $C$ ומספר תאים $b$, ושואלת אם ניתן לשבץ את כולם לכל היותר ב-$b$ תאים. התעודה משייכת פריט לתא. Partition היא מבנה מיוחד של שני תאים כאשר הסכום $2C$. תוצאות קושי חזקות משתמשות לעיתים ב-3-PARTITION, שבה חסמי הגדלים כופים בדיוק שלושה פריטים לתא.

לדוגמה, $6,4,5,5$ נכנסים לשני תאים בקיבולת 10 כ-$(6,4)$ ו-$(5,5)$. עבור $6,6,4,4,1$ הסכום 21 גדול מהקיבולת הכוללת 20, ולכן המופע לא.

עבור מופע Subset Sum $\{3,5,6\}$ עם $T=8$, מתקבל $S=14$, ולכן מוסיפים $x=20,y=22$. סכום מופע Partition הוא 56 וכל צד צריך 28. בצד אחד נמצאים $\{3,5,20\}$ ובשני $\{6,22\}$.

בינרי לעומת אונרי וקושי חזק

כאשר מספר $M$ כתוב בינרית, אורכו $\Theta(\log M)$; בקידוד אונרי אורכו $\Theta(M)$. לכן אלגוריתם $O(mT)$ הוא מעריכי אפשרי בקלט בינרי אך פולינומיאלי בקלט אונרי. בעיה מספרית נקראת NP-קשה בחוזקה כאשר הקושי נשאר גם כשהערכים חסומים פולינומיאלית, ולכן אלגוריתם פסאודו־פולינומיאלי לבעיה כזו היה גורר תוצאה חזקה יותר. 3-PARTITION משמשת מקור קנוני לקושי חזק של בעיות אריזה ותזמון.

גם תעודת Bin Packing חייבת להימדד בקידוד. די לרשום לכל אחד מ-$m$ הפריטים מספר תא בן $O(\log b)$ ביטים ולחבר גדלים בינריים. אין צורך לייצר מערך פיזי בגודל הקיבולת $C$.

9. גאדג׳טים קטנים לחיתוך ולצביעה

ב-Max-Cut, המסלול $u-a-v$ הוא מיקרו־גאדג׳ט שימושי. אם $u,v$ באותו צד, מציבים את $a$ בצד השני ושתי הצלעות נחתכות. אם $u,v$ בצדדים שונים, לכל היותר צלע אחת נחתכת. לכן המסלול מתגמל שוויון בין קצותיו בשתי צלעות לעומת אחת. צלע ישירה $uv$ מתגמלת דווקא אי־שוויון. שילוב משוקלל או שכפול פולינומיאלי של שני האפקטים יכול לבטא אילוץ בוליאני, בתנאי שסף החיתוך אינו משאיר מרווח להפרת גאדג׳ט.

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

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

10. רדוקציות הגרף כרשת אחת

לאחר 3SAT→IS, שתי העתקות קצרות נותנות בעיות נוספות:

מעבירה IS ל-CLIQUE, משום שאי־צלעות ב-$G$ הן צלעות במשלים. אחר כך

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

11. בחירת בעיית מקור

• בחירה בוליאנית ועקביות: 3SAT.
• תאימות או סתירה זוגית: CLIQUE/IS.
• בחירה עם סכום מדויק: Subset Sum.
• מסלול גלובלי מחזורי: Hamiltonian Cycle.
• חלוקה לפי אי־הסכמה: Max-Cut.
• קבוצות תחת קיבולת: 3-Partition או Bin Packing.

התאמה מבנית עוזרת לנסח אינווריאנט, אך אינה מחליפה הוכחה.

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

1. לעבור בשקט בין הכרעה לאופטימיזציה.
2. להשמיט פרמטר מן המופע.
3. למדוד זמן ב-$T$ במקום ב-$\log T$.
4. להניח שהמרת CNF נאיבית תמיד פולינומיאלית.
5. להוכיח רק כיוון אינטואיטיבי של גאדג׳ט.
6. לערבב גרף משלים עם קבוצת קודקודים משלימה.
7. להשתמש בגאדג׳ט מכוון ליעד לא־מכוון.

תרגילים

תרגיל 1 — פרמטר IS→VC

הוכיחו את השקילות: לגרף $G=(V,E)$ יש קבוצה בלתי־תלויה בגודל $\ge k$ אמ״ם יש כיסוי קודקודים בגודל $\le |V|-k$.

תרגיל 2 — תקציב TSP ממשקל יחידה

ברדוקציה ממעגל המילטוני ל-TSP עם משקלי $1$ על צלעות הגרף ומשקל גדול על הלא־צלעות, מדוע תקציב $|V|$ נכון?

תרגיל 3 — בסיס גדול ב-Subset Sum

הסבירו מדוע קידוד עם בסיס גדול (למשל $4$) נחוץ ברדוקציה מ-3SAT ל-Subset Sum.

תרגיל 4 — $O(mT)$ וקידוד בינרי

הוכיחו כי אלגוריתם זמן $O(mT)$ ל-Subset Sum אינו בהכרח פולינומיאלי כאשר $T$ מקודד בינרית.

תרגיל 5 — אחרי קושי: שייכות ל-NP

סטודנט מוכיח ש-$A$ NP-קשה אך שוכח שייכות ל-$\mathrm{NP}$. מה חסר לשלמות? תנו דוגמה מדוע 2-COLOR אינו יעד NP-שלם אלא אם $\mathrm P=\mathrm{NP}$.

סיכום

בעיות קנוניות מתחברות ברשת רדוקציות. פרמטרים, משקלים וקידודים מספריים הם מקום נפוץ לטעויות פורמליות.

תרגול מודרך

משימה 1 — CLIQUE↔IS

הוכיחו שקילות פולינומיאלית בין CLIQUE ב-$G$ ל-IS ב-$\overline G$ (או להפך) עם אותו $k$.

משימה 2 — בחירת בעיית מקור

מתי עדיף להתחיל רדוקציה מ-3SAT ומתי מ-Vertex Cover? תנו קריטריון קצר.

משימה 3 — מלכודת קידוד בצביעה

הסבירו מדוע רדוקציה ל-$k$-COLOR חייבת לטפל בגרפים לא־פשוטים או בפרמטר $k$ כחלק מהקלט לפי הגדרת השפה בקורס.

מקורות

עדויות הקורס

• תמליל 14 של סמסטר א׳ הנוכחי: גאדג׳טי גרפים והחומר על Hamiltonian/TSP המשמש כאן.
• תמליל 15: החומר על בעיות מספריות, ובכלל זה Subset Sum, Partition וזהירות בקידודים.
• הסיכום הממוזג, עמ׳ 55–57, 64–66 ו-72–75: משפחת בעיות הגרף והרדוקציות ביניהן בלבד, לרבות החומר הרלוונטי על קבוצה בלתי־תלויה, קליקה, כיסוי, צביעה וחיתוך.
• פרקי Hamiltonian/TSP ו-Subset-Sum/Partition/Bin-Packing הם סינתזה של תמלילים וספרי לימוד. הם אינם מיוחסים לסיכום הממוזג.

אימות מספרי לימוד

• Sipser, מהדורה שלישית, §7.5, עמ׳ 315–325.
• Papadimitriou, פרק 9.
• Garey–Johnson, פרק 3 וקטלוג הבעיות. המקורות מאמתים את הניסוחים והקידודים; הדוגמאות וסדר ההצגה עוקבים אחר הקורס.