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é ( ), že na horním kraji je potřeba sekvenci (q0,x1), x2, ..., xn z obou stran doplnit dostatečeným počtem hvězdiček. Jak ale určíme, kam ve spodním řádku umístit qF?
- 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 qF 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í ( ), ž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í?