Neexistence r-aproximace pro obecný TSP [FOTO]
V [L3.5] TSP je silně NP-těžký jsi prošel(a) „tréninkovou verzi“ dnešního důkazu: redukce HC → TSP s vahami 1/2 a ekvivalence „HC ⟺ $\mathrm{OPT} = n$“. Dnes tutéž šablonu vystřelíme na mnohem silnější cíl — ukážeme, že pro obecný TSP nepomůže ani vzdát se optimality: žádný polynomiální r-aproximační algoritmus [L3.1] neexistuje (pokud $P \ne NP$), a to pro žádné $r \ge 1$. Je to žebříčkový důkaz #3 pro 15. 6. — na zkoušce 25. 5. 2026 padl doslova — a lekce končí FOTO checkpointem.
Co dokazujeme: věta a strategie sporu
„If we believe $P \ne NP$, then there is no polynomial r-approximation algorithm for TSP for $r \ge 1$.“
A strategie důkazu, slide 19 (EN 1:1): „Proof by contradiction: Assume there exists a polynomial r-approximation algorithm $\mathcal{A}$ for TSP. We further show that we can solve the HC problem while using such an "inaccurate" algorithm $\mathcal{A}$. Since HC is NP-complete, $P = NP$.“
Plán je tedy stejný jako v [L3.5] — „kdybys uměl TSP, umíš HC“ — jen s jedním zásadním rozdílem: tentokrát nemáme k dispozici přesný algoritmus, ale jen „nepřesnou“ černou skříňku $\mathcal{A}$, která smí vrátit okruh až $r$-krát dražší než optimum [L3.1]. Celé umění dneška je sestavit instanci tak, aby ani tahle nepřesnost odpověď nerozmazala.
Zkus sám (klíčová otázka lekce): proč konstrukce z [L3.5] s vahami 1/2 najednou NESTAČÍ? Vezmi $r = 2$ a rozmysli si, co ti $\mathcal{A}$ na ANO-instanci smí vrátit.
Váhy 1/2 dávají mezeru: ANO → $\mathrm{OPT} = n$, NE → $\mathrm{OPT} \ge n+1$. Přesný algoritmus ji rozliší. Jenže 2-aproximace na ANO-instanci garantuje jen $J^{\mathcal{A}} \le 2n$ — klidně vrátí okruh za $1{,}5n$. A na NE-instanci může být optimum třeba $n+1$ a $\mathcal{A}$ vrátí $n+1$. Hodnota $1{,}5n$ (ANO) je větší než $n+1$ (NE) — z odpovědi $\mathcal{A}$ nepoznáš, ve kterém případě jsi. Mezera šířky 1 se v „rozmazání faktorem $r$“ utopí.
Poučení: aby šel výstup r-aproximace číst jako ANO/NE, musí být mezera mezi případy širší než celé rozmazání — NE-případ musí začínat až nad $r \cdot (\text{ANO optimum})$.
Konstrukce: jak drahá musí být chybějící hrana?
Zkus sám: levné hrany nech za 1 (ANO-případ pak má $\mathrm{OPT} = n$ jako v [L3.5]). Jak velkou cenu $x$ musí dostat doplněné hrany, aby KAŽDÝ okruh používající aspoň jednu z nich stál ostře víc než $r \cdot n$?
Nejlevnější okruh s aspoň jednou drahou hranou má $n-1$ hran po 1 a jednu za $x$: stojí $(n-1) + x$. Chceme $(n-1) + x > rn$, tedy
$$x > rn - n + 1 = (r-1)n + 1.$$
Slidy volí nejmenší „hezkou“ hodnotu o jedničku výš: $x = 2 + (r-1)n$. Pak nejlevnější „špinavý“ okruh stojí přesně $(n-1) + 2 + (r-1)n = rn + 1$ — první celé číslo nad pásem $\langle n, rn\rangle$, kam smí padnout odpověď $\mathcal{A}$ na ANO-instanci. Všimni si, že cena drahé hrany roste s $n$ i s $r$ — mezeru roztahujeme přesně tak agresivně, jak agresivní je faktor, který chceme porazit.
„Every HC instance can be polynomially reduced to a TSP instance "inaccurately" solved by r-approximation algorithm $\mathcal{A}$:“
- „Let $G$ be an undirected graph in which we want to find the Hamiltonian circuit.“
- „Create a TSP instance such that every node from $G$ is associated to one node (city) in the complete undirected graph $K_n$. Weight (distance) of $\{i,j\}$ in $K_n$ equals:“
$$c(\{i,j\}) = \begin{cases} 1 & \text{if } \{i,j\} \in E(G); \\ 2 + (r-1) \ast n & \text{if } \{i,j\} \notin E(G). \end{cases}$$
Zkus sám: je převod pořád polynomiální? A nepotřebuje znát odpověď HC?
Ano, polynomiální zůstal: stejně jako v [L3.5] projdeme $\binom{n}{2} = O(n^2)$ dvojic a každé přiřadíme 1, nebo $2+(r-1)n$ podle členství v $E(G)$ — nic se nehledá, odpověď HC převod nezná. Jediná novinka: do vah vstupuje $r$ (konstanta zkoumaného algoritmu) a $n$ — číslo $2+(r-1)n$ má polynomiálně dlouhý zápis, takže i s ním je instance sestavitelná v polynomiálním čase. (Mimochodem proto dnešní instance už nejsou „malá čísla“ — silnou NP-těžkost jsme dokazovali jinou, jemnější konstrukcí v [L3.5].)
Konstrukci si prohlédni na obou typech instancí. Nejdřív ANO-případ — pětiúhelník z [L3.5], který HC má (konkrétně $n = 5$, $r = 2$, takže drahé hrany stojí $2 + (2-1)\cdot 5 = 7$):
Zkus sám (ANO-případ): $G$ má HC, takže $\mathrm{OPT} = n$ (proč?). Jaké hodnoty teď smí vrátit r-aproximační $\mathcal{A}$?
$\mathrm{OPT} = n$: stejné dva kroky jako v [L3.5] — HC v $G$ je okruh ze samých jedniček (cena $n$), a žádný okruh nestojí méně, protože má $n$ hran po aspoň 1.
Odpověď $\mathcal{A}$: definice r-aproximace pro minimalizaci [L3.1] dává horní mez $J^{\mathcal{A}} \le r \cdot \mathrm{OPT} = rn$; a pod optimum se žádný algoritmus nedostane, takže $J^{\mathcal{A}} \ge n$. Odpověď je uvězněná v pásu $$n \;\le\; J^{\mathcal{A}} \;\le\; rn.$$ V našem příkladu: mezi 5 a 10.
A teď NE-případ — motýlek z [L3.3], který HC nemá (vrchol $c$ je artikulace):
Zkus sám (NE-případ): $G$ HC nemá. Dokaž, že KAŽDÝ Hamiltonovský okruh v $K_n$ teď stojí aspoň $rn + 1$ — a všimni si, že tady aproximační záruku vůbec nepotřebuješ.
Kdyby nějaký okruh používal jen hrany ceny 1, byly by to samé hrany $E(G)$ — a takový okruh je Hamiltonovská kružnice v $G$, která neexistuje. Každý okruh tedy obsahuje aspoň jednu drahou hranu a stojí aspoň
$$(n-1) \cdot 1 + 2 + (r-1)n = rn + 1.$$
A teď pointa: $\mathcal{A}$ vrací skutečný přípustný okruh — jeho hodnota je cena nějakého existujícího okruhu, tedy $J^{\mathcal{A}} \ge rn + 1$ automaticky, bez jakékoliv záruky. (Záruku $J^{\mathcal{A}} \le r\,\mathrm{OPT}$ jsme potřebovali jen v ANO-případu, aby odpověď nevylétla nad $rn$.)
Čtení odpovědi: dva disjunktní intervaly
Shrň si oba případy na číselné ose hodnot kritéria (přesně tohle kreslí slide 21):
Slide 20 z toho čte rozhodovací pravidlo (EN 1:1): „We use $\mathcal{A}$ to solve the instance: if the result is in interval $\langle n, r \ast n\rangle$, then the Hamiltonian circuit exists, otherwise the result is greater or equal to $(n-1) + 2 + (r-1) \ast n = r \ast n + 1$ and $G$ has no Hamiltonian circuit.“
Zkus sám: proč se intervaly $\langle n, rn\rangle$ a $\langle rn+1, \infty)$ nemůžou překrýt — a kde přesně by se důkaz rozbil, kdybychom za cenu drahé hrany dali jen $1 + (r-1)n$?
Nepřekrývají se, protože $rn < rn + 1$ — mezi pásem ANO-odpovědí a dnem NE-hodnot je ostrá hranice. Každá hodnota, kterou $\mathcal{A}$ může vrátit, padne právě do jednoho intervalu, takže odpověď čteme jednoznačně.
S cenou $1 + (r-1)n$ by nejlevnější „špinavý“ okruh stál $(n-1) + 1 + (r-1)n = rn$ — přesně horní okraj ANO-pásu. Odpověď $J^{\mathcal{A}} = rn$ by pak mohla znamenat obojí (ANO s nejhorší povolenou nepřesností, i NE s optimem $rn$) a rozhodnutí by se rozpadlo. Proto ta „+2“: posune NE-případ ostře nad pás.
Zkus sám (závěr sporu): poskládej z kousků celý polynomiální rozhodovač HC a řekni, kde přesně vznikne spor.
Pro vstupní graf $G$ s $n$ vrcholy:
- Sestav TSP instanci $(K_n, c)$ s cenami $1$ / $2+(r-1)n$ — čas $O(n^2)$.
- Spusť $\mathcal{A}$ → hodnota $J^{\mathcal{A}}$ — polynomiální čas (to je předpoklad sporu).
- Odpověz: $J^{\mathcal{A}} \le rn$ → ANO, HC existuje; $J^{\mathcal{A}} \ge rn+1$ → NE.
Korektnost dává analýza obou případů, polynomialitu kroky 1–2. Jenže HC je NP-úplný [L3.3] — sestrojili jsme polynomiální algoritmus pro NP-úplný problém, tedy $P = NP$. To odporuje předpokladu $P \ne NP$, takže výchozí domněnka (existence polynomiálního r-aproximačního $\mathcal{A}$) je nepravdivá. A protože $r \ge 1$ bylo libovolné, neexistuje r-aproximace pro žádný faktor — ani $r = 10^6$. $\blacksquare$
Zkus sám (kontrola konzistence): v [L3.9] a [L3.10] přitom dokážeme 2- a 3/2-aproximaci TSP. Jak to jde dohromady s dnešní větou?
Ty algoritmy jsou pro metrický TSP [L3.8a] — instance splňující trojúhelníkovou nerovnost $c(\{i,j\}) + c(\{j,k\}) \ge c(\{k,i\})$. Naše dnešní instance ji porušují: dvě levné hrany dají $1 + 1 = 2$, zatímco drahá hrana stojí $2 + (r-1)n > 2$ pro každé $r > 1$. Dnešní důkaz tedy o metrických instancích neříká nic — zabíjí jen aproximace slibující záruku pro všechny (i nemetrické) instance. Proto věta zní „for General TSP“. (Srovnej s [L3.5]: váhy 1/2 trojúhelníkovou nerovnost splňují, takže i metrický TSP je silně NP-těžký — těžkost zůstává, jen aproximovat už jde.)
Vzorové řešení v bance úloh (#31) vede tentýž důkaz s cenami $c(i,j) = 1$ / $\infty$ a prahem $J^{\mathcal{A}} \le rn \iff$ HC existuje; formální poznámka banky pak ∞ nahrazuje konečnou konstantou, např. $M = \lceil rn \rceil + 1$ (EN 1:1: „In a strictly formal reduction one usually avoids $\infty$ and replaces it by a sufficiently large finite constant, for example $M = \lceil rn\rceil + 1$. […] The proof idea is the same as with $\infty$.“). Slidová volba $2+(r-1)n$ je přesně takové konečné $M$ — u zkoušky piš slidovou verzi, je nejkonkrétnější.
Pozor: nebezpečné polopravdy kolem důkazu- „Stačí váhy 1/2 jako u silné NP-těžkosti.“ NE — mezera $n$ vs. $n+1$ je užší než rozmazání faktorem $r$; ANO-odpověď až $rn$ se s NE-hodnotami překryje. Drahá hrana musí stát $2+(r-1)n$, aby NE-případ začínal nad $rn$.
- „V NE-případu použiju záruku $J^{\mathcal{A}} \le r\,\mathrm{OPT}$.“ Nepotřebuješ ji (a argument by byl zbytečně křehký): $\mathcal{A}$ vrací přípustný okruh a každý okruh tam stojí $\ge rn+1$. Záruka pracuje jen v ANO-případu.
- „Věta zakazuje aproximovat každý TSP.“ NE — jen obecný (nemetrický). Konstruované instance porušují trojúhelníkovou nerovnost; metrický TSP má double-tree 2-aproximaci [L3.9] i Christofidesovu 3/2 [L3.10].
- Směr redukce: pořád HC → TSP („kdybys měl r-aproximaci TSP, rozhodneš HC“). Obrácený převod nedokazuje nic [L3.3].
- „$r$ je nějaká konkrétní konstanta.“ Důkaz běží pro libovolné $r \ge 1$ — konstrukce si faktor přečte a roztáhne mezeru na míru. Proto padají všechny faktory najednou.
Key takeaways — L3.6- Konstrukce (slide 20): z grafu $G$ pro HC vyrob $K_n$ s cenami $c(\{i,j\}) = 1$ pokud $\{i,j\} \in E(G)$, jinak $2 + (r-1) \cdot n$. Převod je $O(n^2)$, polynomiální.
- Dva disjunktní intervaly: HC existuje → $\mathrm{OPT} = n$ a r-aproximace vrátí $J^{\mathcal{A}} \in \langle n, rn\rangle$; HC neexistuje → každý okruh (tedy i výstup $\mathcal{A}$, bez záruky) stojí $\ge (n-1) + 2 + (r-1)n = rn + 1 > rn$.
- Spor: porovnáním $J^{\mathcal{A}}$ s prahem $rn$ by polynomiální r-aproximace rozhodla NP-úplný HC v polynomiálním čase → $P = NP$. Pokud $P \ne NP$, žádná polynomiální r-aproximace obecného TSP neexistuje, pro žádné $r \ge 1$.
- „Obecný“ je podstatné: konstruované instance porušují trojúhelníkovou nerovnost ($1+1 < 2+(r-1)n$) — metrickému TSP věta neškodí, tam fungují double-tree [L3.9] a Christofides [L3.10].
FOTO checkpoint
zdroj: zkouška KO 25.5.2026, slot 3 (EN 1:1, oba dochované přepisy znění shodné; = banka #31); řešení dle 06_TSP slidů 19–21, banka řeší variantou ∞/$M$ (zmíněna v závěru)
Prove the following statement: assuming that $P \neq NP$ there is no polynomial r-approximation algorithm for Traveling Salesman Problem (TSP). Explain polynomial reduction from Existence of Hamiltonian Circuit to prove the statement.
a) Co je v zadání?
Celý dnešní důkaz „na papír“: důkaz sporem, že polynomiální r-aproximace obecného TSP neexistuje (za předpokladu $P \ne NP$), s výslovně vyžádaným vysvětlením polynomiální redukce z HC. Žádná čísla, žádný konkrétní graf — odevzdává se text důkazu. Zadavatel recykluje: tahle úloha padla 25. 5. 2026 doslova v tomto znění.
b) Co k tomu budeme potřebovat?
- Tato lekce — konstrukce $1$ / $2+(r-1)n$, analýza obou případů, rozhodovací pravidlo, spor.
- [L3.1] Co je aproximační algoritmus a faktor r — definice $J^{\mathcal{A}}(I) \le r \cdot J^*(I)$ pro minimalizaci (v ANO-případu ji cituješ).
- [L3.5] TSP je silně NP-těžký — šablona redukce a argument „okruh má $n$ hran po $\ge 1$“.
- [L3.3] Hamiltonovská kružnice a NP-úplnost — HC je NP-úplný (na tom spor stojí) a směr redukce.
c) Jak nad úlohou uvažovat?
Piš jako pět očíslovaných bloků a u každého si zkontroluj „povinnou větu“: (1) strategie — sporem, předpokládej polynomiální r-aproximaci $\mathcal{A}$; (2) konstrukce — vzorec pro $c(\{i,j\})$ + věta „převod je polynomiální“; (3) ANO-případ — $\mathrm{OPT} = n$ (obě nerovnosti!) a ze záruky $J^{\mathcal{A}} \le rn$; (4) NE-případ — každý okruh má drahou hranu → $\ge rn+1$ (zdůrazni, že tady záruku nepotřebuješ); (5) závěr — pravidlo „$J^{\mathcal{A}} \le rn$ ⟺ HC“, polynomiální rozhodovač NP-úplného problému → $P = NP$, spor. Nejčastější ztráta bodů: chybějící zdůvodnění, proč je drahá hrana zrovna $2+(r-1)n$ — ukaž výpočet $(n-1)+2+(r-1)n = rn+1$.
d) Úplné řešení (dle slidů 19–21)
(1) Strategie (slide 19). Důkaz sporem. Předpokládejme, že existuje polynomiální r-aproximační algoritmus $\mathcal{A}$ pro TSP, $r \ge 1$, tj. pro každou instanci vrátí přípustný okruh s cenou $J^{\mathcal{A}} \le r \cdot \mathrm{OPT}$. Ukážeme, že pomocí takto „nepřesného“ $\mathcal{A}$ umíme polynomiálně rozhodnout NP-úplný problém HC, takže $P = NP$ — spor s předpokladem.
(2) Konstrukce (slide 20). 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 (městu) ú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 + (r-1) \ast n & \text{if } \{i,j\} \notin E(G). \end{cases}$$ Převod jen ohodnotí $\binom{n}{2}$ dvojic — čas $O(n^2)$, polynomiální; odpověď HC k němu nepotřebuje.
(3) ANO-případ. Má-li $G$ Hamiltonovskou kružnici, tentýž okruh v $K_n$ používá jen hrany ceny 1 a stojí $n$; a každý okruh má $n$ hran po aspoň 1, takže $\mathrm{OPT} = n$. Algoritmus $\mathcal{A}$ pak vrátí hodnotu v intervalu $$n \;\le\; J^{\mathcal{A}} \;\le\; r \cdot \mathrm{OPT} = r \ast n.$$
(4) NE-případ. Nemá-li $G$ Hamiltonovskou kružnici, žádný okruh v $K_n$ nemůže používat jen hrany ceny 1 (byl by to HC v $G$). Každý okruh tedy obsahuje aspoň jednu hranu ceny $2+(r-1)n$ a stojí aspoň $$(n-1) + 2 + (r-1) \ast n = r \ast n + 1.$$ Výstup $\mathcal{A}$ je cena skutečného okruhu, takže $J^{\mathcal{A}} \ge rn + 1 > rn$ — zde aproximační záruka není potřeba.
(5) Závěr (slidy 20–21). Intervaly $\langle n, rn\rangle$ a $\langle rn+1, \infty)$ jsou disjunktní, takže rozhodneme: je-li výsledek $\mathcal{A}$ v intervalu $\langle n, r \ast n\rangle$, Hamiltonovská kružnice existuje; jinak je výsledek $\ge rn+1$ a $G$ Hamiltonovskou kružnici nemá. Sestavení instance i běh $\mathcal{A}$ jsou polynomiální — rozhodli jsme NP-úplný problém HC v polynomiálním čase, tedy $P = NP$. To odporuje předpokladu $P \ne NP$; polynomiální r-aproximační algoritmus pro obecný TSP tedy neexistuje pro žádné $r \ge 1$. $\blacksquare$
Poznámka (vzorové řešení banky #31): ekvivalentně lze chybějícím hranám dát cenu $\infty$, resp. formálně konečné $M = \lceil rn\rceil + 1$; práh zůstává „$J^{\mathcal{A}} \le rn \iff$ HC existuje“ a myšlenka důkazu se nemění.
Krátká zkoušková odpověď (kostra, kterou rozepíšeš): ① sporem: nechť polynomiální r-aproximace $\mathcal{A}$ existuje; ② redukce HC → TSP: $K_n$, $c = 1$ pro hrany $G$, jinak $2+(r-1)n$, převod $O(n^2)$; ③ HC ano → $\mathrm{OPT} = n$ → $J^{\mathcal{A}} \le rn$; ④ HC ne → každý okruh $\ge (n-1)+2+(r-1)n = rn+1$; ⑤ porovnání $J^{\mathcal{A}}$ s $rn$ rozhodne HC polynomiálně → $P = NP$, spor. Výpočet $rn+1$ v kroku ④ výslovně ukaž.
FOTO checkpointTenhle důkaz napiš celý NA PAPÍR (bez koukání do řešení i do lekce — u zkoušky ho píšeš zpaměti, 25. 5. 2026 padl doslova) a pošli mi fotku. Zkontroluju strukturu (sporem → konstrukce → ANO/NE případy → práh → $P = NP$), vzorec $2+(r-1)n$ s výpočtem $rn+1$ a to, jestli máš v ANO-případu citovanou aproximační záruku a v NE-případu argument „každý okruh má drahou hranu“.