מפת הסיבוכיות
EN
משקל ענק $\alpha|V|+1$ לקשת חסרה

UHC ≤p TSP-OPT

לכל α≥1\alpha\ge1: אם קיים אלגוריתם קירוב ביחס α\alpha לגרסת האופטימיזציה של TSPTSP הכללי, אז P=NP\mathrm{P}=\mathrm{NP}. למעשה מתקיימת שקילות: קיום קירוב כלשהו   ⟺  P=NP\iff \mathrm{P}=\mathrm{NP}.

הבנייה

רקע לניסוח. אין באמת "קושי" מוכח בעולם ה-NP: לא הוכחנו שאי אפשר לפתור בעיה NP-קשה ביעילות, רק שהיא קשה ביחס לשאר בעיות NP\mathrm{NP}. לכן, ובפרט לבעיות אופטימיזציה שעבורן NP-קושי אינו מוגדר פורמלית (הוא מוגדר דרך רדוקציות בין שפות), התוצאות שאפשר לנסח הן תוצאות קושי מותנות: "אם אפשר לעשות X, אז P=NP\mathrm{P}=\mathrm{NP}".

האלגוריתם. יהי α≥1\alpha\ge1, ונניח בשלילה שקיים אלגוריתם קירוב AA ביחס α\alpha. נבנה אלגוריתם המקבל גרף לא מכוון G=(V,E)G=(V,E):

  1. בנה גרף שלם G^=(V,E^)\hat G=(V,\hat E) על אותה קבוצת קודקודים, ולכל e∈E^e\in\hat E הגדר w(e)={1e∈Eα∣V∣+1e∉Ew(e)=\begin{cases}1 & e\in E\\ \alpha|V|+1 & e\notin E\end{cases}
  2. הרץ את AA על (G^,w)(\hat G,w).
  3. אם ערך הפתרון שחזר ≤α∣V∣\le\alpha|V| — קבל; אחרת — דחה.

זו כמעט אותה בנייה כמו UHC≤pTSPUHC\le_p TSP, אבל שם המשקלים היו 11 ו-22 וכאן המשקל של "קשת שלא הייתה" הוא ענק. הענק הזה הוא מה שקונה את הפער מול α\alpha.

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

המחשה

בנייה מודרכת

ל-TSP הכללי אין קירוב קבוע

שלב 1 מתוך 7
n = |V| = 5 · α = 2 · α|V|+1 = 11 · סף αn = 10
שני גרפים בני חמישה קודקודים שהושלמו במשקלים ענקיים, והפער בין שני האופטימומים האפשרייםמשמאל גרף המילטוני שהמסלול האופטימלי בו עולה חמש; מימין עניבת פרפר שאינה המילטונית, שבה המסלול הזול ביותר נאלץ לקנות קשת במשקל אחת עשרה ולעלות חמש עשרה. ציר משותף מציג את קטע הכן מחמש עד עשר, את סף הקבלה בעשר, ואת קטע הלא מחמש עשרה ומעלה, עם רצועה ריקה ביניהם.G ∈ UHCעניבת פרפר + המיתר {2,4}12345G ∉ UHCעניבת פרפר: 3 הוא קודקוד חתך12345
קשת מקורית, w = 1
מדוע קיים מעגל המילטוניהמיתר {2,4} סוגר את המעגל 1→2→4→5→3→1, העובר בכל קודקוד בדיוק פעם אחת ומשתמש רק בקשתות של G.
מדוע אין מעגל כזה בעניבת הפרפרמחיקת קודקוד 3 מותירה את שני הרכיבים {1,2} ו־{4,5}. מעגל המילטוני היה נאלץ לעבור בקודקוד 3 פעמיים כדי לבקר בשניהם, ומעגל אינו יכול לעשות זאת.

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

UHC ∈ ⟹ TSP-OPT ∈

G∈UHCG\in UHC. אז קיים ב-GG מעגל המילטוני C0C_0. אותו מעגל קיים גם ב-G^\hat G (כי E⊆E^E\subseteq\hat E), וכל קשתותיו ב-EE ולכן במשקל 11 כל אחת. במעגל המילטוני יש בדיוק n=∣V∣n=|V| קשתות, ולכן w(C0)=nw(C_0)=n.

יתרה מזו, כל מעגל המילטוני מורכב מ-nn קשתות שמשקל כל אחת לפחות 11, ולכן OPT(G^,w)≥n\mathrm{OPT}(\hat G,w)\ge n; יחד עם הקודם, OPT(G^,w)=n\mathrm{OPT}(\hat G,w)=n בדיוק.

מכיוון ש-AA הוא אלגוריתם קירוב ביחס α\alpha לבעיית מינימיזציה, הפתרון שהוא מחזיר מקיים w(A(G^,w))  ≤  α⋅OPT(G^,w)  =  αn.w(A(\hat G,w))\;\le\;\alpha\cdot\mathrm{OPT}(\hat G,w)\;=\;\alpha n . לכן שלב 3 מקבל — כנדרש.

TSP-OPT ∈ ⟹ UHC ∈

G∉UHCG\notin UHC. אז אין ב-GG מעגל המילטוני. יהי CC מעגל המילטוני כלשהו ב-G^\hat G (קיים, כי G^\hat G שלם). מכיוון ש-CC אינו מעגל המילטוני של GG, בהכרח יש בו קשת e∗∉Ee^*\notin E, ולכן w(e∗)=αn+1w(e^*)=\alpha n+1. שאר n−1n-1 הקשתות תורמות לפחות 11 כל אחת, ולכן w(C)  ≥  (αn+1)+(n−1)  =  αn+n  >  αn.w(C)\;\ge\;(\alpha n+1)+(n-1)\;=\;\alpha n+n\;>\;\alpha n . זה נכון לכל מעגל המילטוני ב-G^\hat G, ובפרט למינימלי, ולכן OPT(G^,w)>αn\mathrm{OPT}(\hat G,w)>\alpha n.

אלגוריתם הקירוב מחזיר פתרון אפשרי, ופתרון אפשרי אינו יכול להיות זול מהאופטימום, ולכן גם w(A(G^,w))≥OPT(G^,w)>αnw(A(\hat G,w))\ge\mathrm{OPT}(\hat G,w)>\alpha n. לכן שלב 3 דוחה — כנדרש.

שימו לב ששני צדדיו של אי-השוויון נוצלו. בכיוון הראשון השתמשנו בצד ה"מעניין" (ALG≤α OPT\mathrm{ALG}\le\alpha\,\mathrm{OPT}), ובכיוון השני דווקא בצד הטריוויאלי (ALG≥OPT\mathrm{ALG}\ge\mathrm{OPT}), הנובע מכך שהפלט הוא פתרון אפשרי. בלי הדרישה שהפלט יהיה פיזבילי, הכיוון השני היה נופל.

סיום. האלגוריתם מכריע את UHCUHC בזמן פולינומי, ולכן UHC∈PUHC\in\mathrm{P}. אך UHCUHC היא NP-קשה, ולכן לכל L∈NPL\in\mathrm{NP} מתקיים L≤pUHC∈PL\le_p UHC\in\mathrm{P}, כלומר NP⊆P\mathrm{NP}\subseteq\mathrm{P}; יחד עם ההכלה הטריוויאלית, P=NP\mathrm{P}=\mathrm{NP}.

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

זמןO(|V|²) plus one call to A
מקוםO(|V|²)
גודל הפלטO(|V|²) for the constructed instance

שלב 1 דורש O(∣V∣2)O(|V|^2): יש (∣V∣2)\binom{|V|}{2} קשתות בגרף השלם, ולכל אחת בדיקה וכתיבת משקל. המשקל α∣V∣+1\alpha|V|+1 ניתן לכתיבה ב-O(log⁡(α∣V∣))O(\log(\alpha|V|)) ביטים — זה מספר גדול אבל קצר, וזה בדיוק ההבדל בין "מספר גדול" ל"מספר שאי אפשר לכתוב".

שלב 2 פולינומי כי אלגוריתם קירוב הוא מעצם ההגדרה אלגוריתם פולינומי, ומכיוון ש-∣(G^,w)∣≤O(∣G∣2)|(\hat G,w)|\le O(|G|^2) ופולינום בפולינום הוא פולינום. שלב 3 הוא השוואה בודדת.

מה זה קונה

ל-TSPTSP הכללי אין אלגוריתם קירוב בשום יחס קבוע, אלא אם P=NP\mathrm{P}=\mathrm{NP}. השקילות המלאה: קיום קירוב ביחס כלשהו   ⟺  P=NP\iff\mathrm{P}=\mathrm{NP} — הכיוון ההפוך מיידי, שכן אם P=NP\mathrm{P}=\mathrm{NP} אפשר לפתור את גרסת האופטימיזציה במדויק בחיפוש בינארי על ערך המטרה, כלומר לקרב בפקטור 11.

מלכודות

  • המשקלים מפרים בגסות את אי-שוויון המשולש — קשת "יקרה" בין שני קודקודים שיש ביניהם מסלול זול. לכן המשפט אומר דבר על TSPTSP הכללי בלבד, ואינו סותר את קיומו של אלגוריתם הקירוב ביחס 22 לגרסה המטרית. זו הנקודה המרכזית: היכן בדיוק נשבר החסם כשמוסיפים את אי-שוויון המשולש.

  • אם α\alpha אינו שלם, αn+1\alpha n+1 אינו שלם. אפשר לעבוד עם משקלים רציונליים (ואז α\alpha חייב להיות רציונלי כדי שנוכל לכתוב אותו בזמן פולינומי), או להשתמש ב-⌈αn⌉+1\lceil\alpha n\rceil+1; אז w(C)≥⌈αn⌉+1+(n−1)>αnw(C)\ge\lceil\alpha n\rceil+1+(n-1)>\alpha n וההוכחה עוברת מילה במילה.

השרשרת

נשענת על

מאיפה זה נקרא

  • שיעור 13משפט 4: לכל α≥1\alpha \ge 1 — אם ניתן לקרב את בעיית הסוכן הנוסע הכללית ביחס α\alpha, אז P=NP\mathrm{P}=\mathrm{NP}
  • תרגיל מודרךmetric-tsp-approximation

  • שתי ההערות הטכניות — הטיפול ב-α\alpha לא שלם, והציון המפורש שאי-שוויון המשולש מופר — אינן נאמרות בהרצאה; הן השלמות שנכתבו בקובץ השיעור.