Koukám na svoje zápisky z (d)úkazu, že Kachlíkování (dále KACHL) je NP-úplné a mám problém s jednou podstatnou věcí. Mám tušení, že se to řešilo i na přednášce (snad se na to ptal Martin Černý), a tehdy jsem to si myslel, že to chápu, nebo mě Čepek prostě nějak uchlácholil, takže jsem si z toho nic nezapsal. Mrkněte na to, a napište mi, co si o tom myslíte, resp. co si pamatujete z té přednášky:
Nástin problému: Výpočet NTS, který řešení KACHLu kóduje, přece může zabrat libovolný čas a prostor: nás to zajímá pro polynomiální čas a prostor, ale když nám nepřítel hodí nějaký konkrétní vstup, tak my houby víme, jakým konkrétním polynomem můžeme délku pásky/výpočtu omezit.
Konkrétní otázky a některé návrhy, jak problém řešit:
Jak tedy při převodu na kachlíkování zvolíme rozměry té čtvercové sítě?
Je jasné ( :wink: ), že na horním kraji je potřeba sekvenci (q<sub>0</sub>,x<sub>1</sub>), x<sub>2</sub>, ..., x<sub>n</sub> z obou stran doplnit dostatečeným počtem hvězdiček. Jak ale určíme, kam ve spodním řádku umístit q<sub>F</sub>?
Kdybychom se rozhodli problém vyřešit změnou definice problému KACHL a povolit nafukování čtverce (okraje by se doplňovaly hvězdičkami) a šoupání s q<sub>F</sub> na spodním okraji, říkejme tomu KACHL'. Algoritmus na řešení **KACHL'**u by to dělal nedeterministicky, takže KACHL' je pořád v NP. Není v úvaze chyba? (Ponechme stranou, že řešíme problém tím, že jsme změnili zadání: KACHL, jak ho má Čepek ve slajdech, má mít přece pevně zadaný okraj.)
Každý vidí ( :wink: ), že by se to dalo celé ošidit, kdybychom znali certifikát k řešení problému, který chceme převést na KACHL. Dá se to ale nějak rigorózně zformulovat, když certifikáty v definici převoditelnosti vůbec nevystupují?{: style="list-style-type:decimal"}