DHP/DHC/UHC/UHP ≤p each other

הטיעון החוסך. לכאורה צריך רדוקציה בין כל זוג סדור, כלומר $4\cdot3=12$ רדוקציות. אבל $\le_p$ טרנזיטיבי, ולכן די במעגל של ארבע:

$DHP\ \le_p\ DHC\ \le_p\ UHC\ \le_p\ UHP\ \le_p\ DHP .$

מכל צומת אפשר להגיע לכל צומת אחר בהליכה לאורך המעגל, ובכל הליכה כזו מרכיבים לכל היותר שלוש רדוקציות — והרכבה של פולינומים היא פולינום. עלינו מ-12 ל-4.

ההצדקה המלאה של ההרכבה. אם $f$ מחשבת $A\le_p B$ בזמן $p(n)$ ו-$g$ מחשבת $B\le_p C$ בזמן $q(n)$, אז $|f(x)|\le p(|x|)$ — בזמן $p(|x|)$ אי אפשר לכתוב יותר מ-$p(|x|)$ תווים — ולכן חישוב $g(f(x))$ עולה $p(|x|)+q(p(|x|))$, שהוא פולינום. וכן $x\in A\iff f(x)\in B\iff g(f(x))\in C$.

נקודת המוצא. נאמר בקורס ללא הוכחה כי $\mathrm{3SAT}\le_p DHP$, ולכן $DHP$ היא NP-קשה; המרצה הצהיר במפורש שהרדוקציה הזאת "חמודה אבל מאוד מאוד טרחנית" ולכן מוותרים עליה — את התוצאה צריך לדעת, את ההוכחה לא. מרגע ש-$DHP$ קשה, המעגל מעביר את הקושי לשלוש האחרות.

כולן ב-NP. ה-certificate הוא סדר של הקודקודים (תמורה של $V$), באורך $O(|V|\log|V|)$. המוודא בודק שכל שני קודקודים עוקבים מחוברים בקשת (ובגרף מכוון — בקשת בכיוון הנכון), ובמקרה של מעגל בודק גם את הקשת הסוגרת מהאחרון לראשון. זמן פולינומי. לכן כל הארבע NP-שלמות.

כל ארבע הבעיות ההמילטוניות NP-שלמות. אזהרה שעלתה בכיתה: בקורס האלגוריתמים ראינו אלגוריתם פולינומי בעזרת מיון טופולוגי — זה נכון, אבל רק עבור גרף מכוון חסר מעגלים (DAG), מקרה מאוד ספציפי, ואין בכך סתירה לקושי של הבעיה הכללית.