TSP je silně NP-těžký (redukce z HC, váhy 1/2)
V [L3.3] Hamiltonovská kružnice a NP-úplnost jsme si připravili zdroj těžkosti (HC je NP-úplný) a v „předkrmu“ sis dokonce zkusil(a) vymyslet převod na TSP. V [L3.4] už TSP umíme formálně i jako ILP. Dnes ten převod proměníme v úplný důkaz — první hotovou redukci téhle kapitoly. Stejná konstrukce se zostřenými vahami pak v [L3.6] zabije i všechny r-aproximace (žebříčkový důkaz #3) — dnešek je její „tréninková verze“, na které pochopíš každý krok.
Co dokazujeme a jak na to půjdeme
TSP is strongly NP-hard.
Slide k tomu říká, jak na to (EN 1:1): „We show that the TSP is NP-hard even when restricted to instances where all distances are 1 or 2 using polynomial transformation from the HC problem.“
Slovo silně (strongly) si necháme na konec lekce — nejdřív poctivě provedeme samotnou redukci HC → TSP. Plán z [L3.3]: vezmeme libovolnou instanci HC (obecný neorientovaný graf $G$ s $n$ vrcholy) a v polynomiálním čase z ní vyrobíme instanci TSP tak, aby hodnota optima prozradila odpověď HC.
Zkus sám (opáčko předkrmu z [L3.3]): TSP potřebuje úplný graf $K_n$ s cenami hran [L3.4], ale $G$ úplný není. Jak ceny nastavíš?
Vrcholy necháme ($n$ měst = $n$ vrcholů $G$), graf zúplníme a každé hraně $K_n$ dáme cenu podle toho, jestli v $G$ byla:
$$c(\{i,j\}) = \begin{cases} 1 & \text{if } \{i,j\} \in E(G); \\ 2 & \text{if } \{i,j\} \notin E(G). \end{cases}$$
(EN 1:1 ze slidu 18.) Hrany původního grafu jsou „levné“, doplněné hrany „drahé“. Žádná magická čísla — uvidíš, že stačí, aby drahá hrana stála ostře víc než levná.
Konstrukci si prohlédni na konkrétním grafu, který Hamiltonovskou kružnici má:
Zkus sám: je tenhle převod polynomiální? (Bez toho by celá redukce nedávala smysl.)
Ano — převod nic nehledá ani nezkouší: jen projde všech $\binom{n}{2} = O(n^2)$ dvojic vrcholů a každé přiřadí cenu 1 nebo 2 podle členství v $E(G)$ (jeden test na dvojici). Čas $O(n^2)$, polynomiální ve velikosti $G$. Důležité: převod neřeší HC — kdyby k sestavení instance bylo potřeba vědět, jestli HC existuje, byl by důkaz kruhový.
Klíčové tvrzení: HC v $G$ ⟺ optimum TSP $= n$
Slide 18 (EN 1:1): „$G$ has a Hamiltonian circuit iff optimal TSP solution is equal to $n$.“ To je srdce důkazu — a „iff“ znamená, že musíme zvládnout oba směry. Rozložíme si je na tři malé krůčky.
Zkus sám (krok 1 — dolní mez): kolik nejméně stojí úplně každý Hamiltonovský okruh v naší instanci? Nezávisle na tom, jak vypadá $G$.
Každý Hamiltonovský okruh v $K_n$ má přesně $n$ hran ($n$ měst, z každého právě jednou vyjedeš [L3.4]) a každá hrana stojí aspoň 1. Takže každý okruh stojí aspoň $n$: $$\mathrm{OPT} \ge n.$$ Tahle lacino vypadající nerovnost je půlka celé ekvivalence — bez ní by „optimum $= n$“ nic neznamenalo.
Zkus sám (krok 2 — směr ⇒): nechť $G$ Hamiltonovskou kružnici má. Proč je pak optimum přesně $n$?
Hamiltonovská kružnice v $G$ používá jen hrany $E(G)$ — a ty mají v naší instanci cenu 1. Tentýž okruh tedy existuje i v $K_n$ a stojí $n \cdot 1 = n$. Máme okruh za $n$, takže $\mathrm{OPT} \le n$; spolu s krokem 1 ($\mathrm{OPT} \ge n$) dostáváme $\mathrm{OPT} = n$. ✓
Zkus sám (krok 3 — směr ⇐, ten se zapomíná!): nechť optimum TSP je $n$. Co všechno víš o optimálním okruhu — a proč z toho plyne HC v $G$?
Optimální okruh má $n$ hran a stojí dohromady $n$. Kdyby jediná z jeho hran měla cenu 2, stál by aspoň $(n-1) \cdot 1 + 2 = n + 1 > n$ — spor. Takže všechny jeho hrany mají cenu 1, tedy všechny leží v $E(G)$. Okruh z hran $G$ procházející všemi vrcholy právě jednou — to je přesně Hamiltonovská kružnice v $G$. ✓
Ekvivalence je hotová: $G$ má HC ⟺ $\mathrm{OPT} = n$. Všimni si kontrapozice směru ⇐: když $G$ HC nemá, musí každý okruh použít aspoň jednu dvojkovou hranu, takže $\mathrm{OPT} \ge n + 1$. Mezi ANO a NE instancemi vzniká mezera $n$ vs. $n+1$ — žádná hodnota mezi tím nenastane.
NE-případ si přehraj na motýlku z [L3.3] — grafu, o kterém jsme dokázali, že HC nemá (artikulace $c$):
Závěr redukce: kdybys uměl(a) TSP, umíš HC
Zkus sám: představ si, že má kamarádka polynomiální algoritmus na TSP. Sestav z něj polynomiální rozhodovač HC — krok za krokem.
Pro vstupní graf $G$ s $n$ vrcholy:
- Sestav TSP instanci $(K_n, c)$ s cenami 1/2 podle $E(G)$ — čas $O(n^2)$.
- Spusť kamarádčin algoritmus → dostaneš $\mathrm{OPT}$ — polynomiální čas.
- Odpověz: $\mathrm{OPT} = n$ → ANO, HC existuje; $\mathrm{OPT} \ge n+1$ → NE.
Korektnost dává ekvivalence z předchozí sekce, polynomialitu kroky 1–2. Jenže HC je NP-úplný [L3.3] — polynomiální rozhodovač HC by znamenal $P = NP$. Takže (pokud $P \ne NP$) žádný polynomiální algoritmus na TSP neexistuje: TSP je NP-těžký. $\blacksquare$
Tohle schéma — převod ze známého těžkého problému + ekvivalence hodnot + „kdybys uměl nový, umíš starý“ — je šablona všech redukcí. V [L3.6] do ní jen dosadíme jiné ceny.
A teď to „silně“: malá čísla, žádný pseudopolynomiální únik
NP-těžkost některých problémů stojí na velkých číslech v instanci. Ukázkový příklad je problém batohu (knapsack):
Zkus sám: knapsack je NP-těžký, a přitom ho dynamické programování řeší v čase $O(nC)$, kde $C$ je kapacita batohu (uvidíš v [L7.1]). Není to spor — polynomiální algoritmus na NP-těžký problém?
Není. „Polynomiální“ se měří vůči velikosti zápisu vstupu $size(I)$ — a číslo $C$ se zapisuje binárně na $\log_2 C$ bitů. Čas $O(nC)$ je tedy v počtu bitů exponenciální: $C = 2^{\log_2 C}$. Pro $C \approx 10^{15}$ (16 cifer zápisu!) je tabulka DP beznadějně velká. Algoritmům polynomiálním v $size(I)$ a zároveň v hodnotě největšího čísla $largest(I)$ se říká pseudopolynomiální (pseudopolynomial) — jsou polynomiální jen „když jsou čísla malá“.
Pro knapsack je to skvělá zpráva: NP-těžkost se dá obejít, dokud jsou čísla rozumná. Otázka dne: jde to stejně u TSP?
Let $L$ be an optimization problem.
For a polynomial $p$ let $L_p$ be the restriction of $L$ to such instances $I$ that consist of nonnegative integers with $\mathit{largest}(I) \le p(\mathit{size}(I))$.
$L$ is strongly NP-hard if there is a polynomial $p$ such that $L_p$ is NP-hard.
Slide dodává (EN 1:1): „i.e., $L$ is said to be strongly NP-hard, if it remains NP-hard even when all of its parameters are bounded by a polynomial in the size of the input.“ A důsledek: „If $L$ is strongly NP-hard, then $L$ cannot be solved by a pseudopolynomial time algorithm unless $P = NP$.“
(Značení: $size(I)$ = délka zápisu instance v bitech, $largest(I)$ = největší číslo v instanci — standardní pojmy, slide je užívá bez definice; dovysvětlení je vlastní doplněk.)
Zkus sám (pointa lekce): kde přesně v naší redukci je „silně“ schované? Najdi restrikci $L_p$ a polynom $p$.
Naše redukce vyrobila instance, kde všechny ceny jsou 1 nebo 2 — a dokázala, že už tahle restrikce TSP je NP-těžká. Slide 17 (EN 1:1): „$L$ … TSP, $L_p$ … TSP with restriction $c(e) \in \{1,2\}$, i.e. $\mathit{largest}(I) = 2 \le n = p(\mathit{size}(I))$.“ Největší číslo v instanci je 2, což je triviálně omezené polynomem velikosti vstupu (třeba $p = n$). Definice je splněna: TSP je silně NP-těžký.
Důsledek: TSP nemá ani pseudopolynomiální algoritmus (pokud $P \ne NP$). Těžkost TSP nestojí na velkých číslech — je zadrátovaná už v kombinatorice okruhů. „Knapsackový únik“ tady neexistuje.
Slide 17 (EN 1:1): „On the other hand: $L$ … Knapsack, $L_p$ … Knapsack with bounded integer costs for which the Dynamic prog. table has polynomial number ($n \ast p(\mathit{size}(I))$) of columns, i.e. Knapsack is not strongly NP-hard.“ Omezíš-li čísla polynomem, DP tabulka se polynomiálně zmenší a knapsack se řeší v polynomiálním čase — restrikce tedy NP-těžká není (pokud $P \ne NP$). DP tabulku propočítáš v [L7.1], 2-aproximaci knapsacku dokážeme v [L3.11].
Pozor: nebezpečné polopravdy kolem redukce- „Silně NP-těžký = nějak víc NP-těžký.“ NE — „silně“ je přesný výrok o číslech v instanci: problém zůstane NP-těžký, i když všechna čísla omezíš polynomem velikosti vstupu. Důsledkem padá pseudopolynomiální algoritmus, nic „těžšího“ v tom není.
- Směr redukce: převádíme HC → TSP („kdybys uměl TSP, umíš HC“). Převod opačným směrem o těžkosti TSP neříká nic — u zkoušky je obrácený směr klasická diskvalifikační chyba [L3.3].
- „Optimum $= n$, hotovo.“ Ekvivalence má DVA směry: $\mathrm{OPT} \le n$ z existence HC a $\mathrm{OPT} \ge n$ z „$n$ hran po aspoň 1“; pro ⇐ navíc argument „jediná dvojka přehoupne přes $n$“. Bez dolní meze důkaz nestojí.
- „Dokázali jsme to jen pro ceny 1/2.“ Ano — a to stačí: restrikce je speciální případ, takže těžkost restrikce dává těžkost celého TSP. (Obecná zásada: NP-těžkost speciálního případu se dědí nahoru, nikdy ne dolů.)
Key takeaways — L3.5- Konstrukce (slide 18): z grafu $G$ pro HC vyrob úplný graf $K_n$; $c(\{i,j\}) = 1$ pokud $\{i,j\} \in E(G)$, jinak $2$. Převod je $O(n^2)$, nic neřeší, jen přepisuje.
- Ekvivalence: HC v $G$ existuje ⟺ optimum TSP $= n$. (⇒: HC = okruh ze samých jedniček; ⇐: okruh má $n$ hran ceny $\ge 1$, jediná dvojka by dala $\ge n+1$.) Bez HC je $\mathrm{OPT} \ge n+1$ — mezi ANO a NE je mezera.
- Silně NP-těžký (slide 17): restrikce $L_p$ na instance s $largest(I) \le p(size(I))$ je NP-těžká. U TSP: ceny $\in \{1,2\}$, $largest(I) = 2 \le n$ → TSP je silně NP-těžký → žádný pseudopolynomiální algoritmus, pokud $P \ne NP$. Kontrast: knapsack silně NP-těžký není (DP $O(nC)$, [L7.1]).
- Stejná šablona, jiné ceny: nahradíš-li 2 hodnotou $2 + (r-1)n$, mezera se roztáhne tak, že ji rozezná i r-aproximace — to je důkaz neexistence r-aproximace v [L3.6].
Prove that the Traveling Salesman Problem (TSP) is strongly NP-hard. Define strong NP-hardness, describe a polynomial transformation from the Existence of Hamiltonian Circuit (HC) problem, prove the correspondence between the two instances, and explain why this implies that TSP cannot be solved by a pseudopolynomial time algorithm unless $P = NP$.
a) Co je v zadání?
Celý dnešní důkaz „na papír“: definice silné NP-těžkosti, konstrukce instance s vahami 1/2, ekvivalence „HC ⟺ $\mathrm{OPT} = n$“ (oba směry!) a závěr o pseudopolynomiálních algoritmech. Je to důkazová úloha Slotu 3 — body se dávají za strukturu: definice → konstrukce → ekvivalence → závěr.
b) Co k tomu budeme potřebovat?
- Tato lekce — konstrukce, ekvivalence, definice „strongly“.
- [L3.3] Hamiltonovská kružnice a NP-úplnost — HC je NP-úplný (na tom celý důkaz stojí), směr redukce.
- [L3.4] TSP jako ILP — definice TSP, okruh má $n$ hran.
c) Jak nad úlohou uvažovat?
Piš důkaz jako čtyři očíslované bloky a u každého si zkontroluj jeho „povinnou větu“: (1) definice — co je restrikce $L_p$ a kdy je $L$ silně NP-těžký; (2) konstrukce — vzorec pro $c(\{i,j\})$ + věta „převod je polynomiální ($O(n^2)$)“; (3) ekvivalence — oba směry, nezapomeň dolní mez „okruh má $n$ hran ceny $\ge 1$“; (4) závěr — proč ceny $\{1,2\}$ znamenají „silně“ ($largest(I) = 2 \le n$) a co z toho plyne pro pseudopolynomiální algoritmy.
d) Úplné řešení
(1) Definice (slide 17). For a polynomial $p$ let $L_p$ be the restriction of $L$ to such instances $I$ that consist of nonnegative integers with $\mathit{largest}(I) \le p(\mathit{size}(I))$. $L$ is strongly NP-hard if there is a polynomial $p$ such that $L_p$ is NP-hard. If $L$ is strongly NP-hard, then $L$ cannot be solved by a pseudopolynomial time algorithm unless $P = NP$.
(2) Konstrukce (slide 18). Ukážeme, že TSP je NP-těžký už při restrikci na instance se vzdálenostmi 1 a 2, polynomiální transformací z problému HC. Nechť $G$ je neorientovaný graf s $n$ vrcholy, v němž chceme rozhodnout existenci Hamiltonovské kružnice. Sestavíme instanci TSP: každý vrchol $G$ odpovídá jednomu vrcholu úplného grafu $K_n$ a cena hrany $\{i,j\}$ v $K_n$ je $$c(\{i,j\}) = \begin{cases} 1 & \text{if } \{i,j\} \in E(G); \\ 2 & \text{if } \{i,j\} \notin E(G). \end{cases}$$ Převod jen ohodnotí $\binom{n}{2}$ dvojic — čas $O(n^2)$, polynomiální.
(3) Ekvivalence. Tvrdíme: $G$ má Hamiltonovskou kružnici ⟺ optimum TSP $= n$.
- Dolní mez: každý Hamiltonovský okruh v $K_n$ má přesně $n$ hran a každá stojí $\ge 1$, takže $\mathrm{OPT} \ge n$.
- (⇒) Má-li $G$ Hamiltonovskou kružnici, tentýž okruh v $K_n$ používá jen hrany ceny 1 a stojí $n$. Tedy $\mathrm{OPT} \le n$, a s dolní mezí $\mathrm{OPT} = n$.
- (⇐) Je-li $\mathrm{OPT} = n$, optimální okruh nesmí obsahovat žádnou hranu ceny 2 (jinak by stál $\ge (n-1) + 2 = n+1$). Všechny jeho hrany tedy leží v $E(G)$ a tvoří Hamiltonovskou kružnici v $G$. (Kontrapozicí: nemá-li $G$ HC, je $\mathrm{OPT} \ge n+1$.)
(4) Závěr. Polynomiální algoritmus pro TSP by přes tuto transformaci rozhodl NP-úplný problém HC v polynomiálním čase (spočti $\mathrm{OPT}$ a porovnej s $n$), tedy by platilo $P = NP$ — TSP je NP-těžký. Naše instance navíc obsahují jen čísla 1 a 2: $\mathit{largest}(I) = 2 \le n = p(\mathit{size}(I))$, takže NP-těžká je už restrikce $L_p$ s $c(e) \in \{1,2\}$ — TSP je silně NP-těžký. Proto TSP nemůže být řešen pseudopolynomiálním algoritmem, pokud $P \ne NP$. $\blacksquare$