# Kachlíkování pořádně
<{ForumPost(poster="adam", timestamp=2010-01-31 11:48:26)}>
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í **KACHL**u 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:**
1. Jak tedy při převodu na kachlíkování zvolíme rozměry té čtvercové sítě?
1. Je jasné ( :wink: ), ž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*?
1. 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.)
1. 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"}
<{/ForumPost}>
<{ForumPost(poster="Osiris", timestamp=2010-01-31 13:16:09)}>
No, každý problém ve třídě NP je řešitelný v polynomiálním čase na NTS. Tak si vezmeš ten polynom a čtvercová síť bude mít délku/šířku nastavenou podle toho polynomu. Já myslím ,že stačí EXISTENCE toho polynomu...
<{/ForumPost}>
<{ForumPost(poster="macbeth", timestamp=2010-01-31 13:41:35)}>
a pokial mam spravne poznamky, tak qF je na dolnom okraji hned na zaciatku (stroj po prechode do qy neskonci, ale vsetko na paske prepise prazdnym symbolom, hlavu zaparkuje na zaciatku pasky a prejde do 'noveho' koncoveho stavu)... aspon tak sa to pise v poznamkach z fora, ktore mam...
<{/ForumPost}>
<{ForumPost(poster="adam", timestamp=2010-01-31 14:16:13)}>
> Osiris wrote:No, každý problém ve třídě NP je řešitelný v polynomiálním čase na NTS. Tak si vezmeš ten polynom a čtvercová síť bude mít délku/šířku nastavenou podle toho polynomu. Já myslím ,že stačí EXISTENCE toho polynomu...
(Poznámka: Celý následující argument je naprosto nesmyslný, což si nyní plně uvědomuji, viz níže. Ale nechám to tady pro poučení příštích generací, a taky abych se měl za co stydět:).) To je totéž, co jsem psal v bodu (4), certifikát existuje, polynom existuje, ani jeden ale neznáme. Narážel jsem na to, že z definice převoditelnosti musíš umět udělat převod *f*, který v polynomiálním čase DETERMINISTICKY převede zadání převáděného problému na cílový (aniž by dostal ten polynom, resp. konkrétní prostorovou/časovou složitost, nebo certifikát). Ten převod na **KACHL** se dělá pro nějaký pevně zvolený problém, pro který máme NTS M (který mimo jiné nějakou přechodovou fci delta), ze kterého mi ten převod *f* zkonstruujeme, chceš-li, můžeš při tom využít informaci, že takovýc polynom p EXISTUJE, ale ta je ti IMHO k ničemu. Kdybys chtěl uvnitř *f* ten polynom zjistit, tak bys musel spustit NEDETERMINISTICKÝ polynomiální výpočet, pak ale nezaručíš, že ten převod *f* je deterministicky polynomiální. Z informace o existenci polynomu *p* prostě deterministicky nezkonstruuješ okraj sítě, jehož délka je rovná jeho hodnotě *p*(*n*) (pro dané *n*). (Poznámka: konec nesmyslného argumentu.)
> macbeth wrote:a pokial mam spravne poznamky, tak qF je na dolnom okraji hned na zaciatku (stroj po prechode do qy neskonci, ale vsetko na paske prepise prazdnym symbolom, hlavu zaparkuje na zaciatku pasky a prejde do 'noveho' koncoveho stavu)... aspon tak sa to pise v poznamkach z fora, ktore mam...
To je fakt, takhle otázka je asi zbytečná. Dá se to vyřešit obdobně, jako když se tam žádné "místo na pásce" (resp. hvězdičky na horní okraj) nepřidává. Není v tom žádný velký zádrhel. Takže to bychom měli, a zpátky k tomu, jak vyřešit ten hlavní problém:).
<{/ForumPost}>
<{ForumPost(poster="adam", timestamp=2010-01-31 14:31:13)}>
Teď začínám být nějaký nejistý. Možná, že doopravdy řeším blbost. Asi bych mohl chtít, aby mi nepřítel, co mi předhazuje nějaký problém z NP a stroj M, který ho řeší mi dal i polynom, který shora odhaduje prostor použitý při přijímacím výpočtu.
<{/ForumPost}>
<{ForumPost(poster="adam", timestamp=2010-01-31 14:35:31)}>
> adam wrote:Teď začínám být nějaký nejistý. Možná, že doopravdy řeším blbost. Asi bych mohl chtít, aby mi nepřítel, co mi předhazuje nějaký problém z NP a stroj M, který ho řeší mi dal i polynom, který shora odhaduje prostor použitý při přijímacím výpočtu.
A ještě jednou si odpovím:): Ano, skutečně v tom není problém. Řeším přece existenci polynomiálního převodu *f*, ne otázku, zda a z jakých informací ho umím (efektivně) zkonstruovat. Tímto se omlouvám za hloupou otázku (učím se současně na vyčíslitelnost, tak asi chápete, proč mě takovéhle blbosti napadají;)), a děkuji Osirisovi za nakopnutí správným směrem!
<{/ForumPost}>
<{ForumPost(poster="Fairfax", timestamp=2010-02-04 10:43:22)}>
Na kachlíkování je právě nejlepší, že si tam člověk může krásně představit prostorovou a časovou složitost.
**prostorová** - šířka čtvercové sítě
**časová** - výška čtvercové sítě
V důkazu existence NP-úplného problému (Cook-Levin) se především ukazuje, že jsme schopni převést libovolný problém ze třídy NP na KACHL. Někdo nám tedy dá problém $Q \in NP$ (výpočet příslušného NTS lze tedy omezit nějakým polynomem **T(n)** časově a **S(n)** prostorově). Pro libovolnou instanci **Q** (jejíž délku **n** známe v momentě kdy nám ji nepřítel zadá) můžeme zkonstruovat zadání KACHL. Velikost čtvercové sítě spočítáme z **n** a polynomů **T(n)** a **S(n)**, které nám nepřítel musí dodat (protože to je ON, kdo tvrdí, že **Q** patří do NP - ukázat existenci nějakých dvou polynomů by tedy pro něj neměl být problém).
<{/ForumPost}>
<{ForumPost(poster="adam", timestamp=2010-02-04 11:02:21)}>
> Fairfax wrote:Na kachlíkování je právě nejlepší, že si tam člověk může krásně představit prostorovou a časovou složitost.
Přesně tak. Prima, že to tady někdo pro příští myslitele shrnul:).
Jen k tomu pro úplnost dodám pár *technických* drobností, doufám, že správných:
1. Pracujeme-li s modelem TS, který má jednu oboustraně nekonečnou pásku, je třeba zvolit šířku 2*S(*n*)-*n*, nebo raději 2*S(*n*)+*n* (podle toho, jak máme definovanou prostorovou složitost na jedné pásce), a vstup dát doprostřed (nevíme, ze které strany to bude těch S\[/i](*n*) polí potřebovat). (Jednostrannou pásku, kde bychom to řešit nemuseli, jsme na přednášce určitě nikdy nezaváděli, i když to samozřejmě jde.)
1. Pracujeme-li s definicí **KACHL**, která má čtvercovou síť, můžeme oba rozměry sítě zvolit 2*T(*n*)+*n*, jistě totiž pro jednopáskový stroj platí platí S(*n*) ≤ T(*n*). (Myslím, že jsme pracovali právě se čtvercovou definicí, i když to samozřejmě taky není nutné.){: style="list-style-type:decimal"}
<{/ForumPost}>
<{ForumPost(poster="adam", timestamp=2010-02-04 11:06:43)}>
Jo, omylem jsi asi několikrát napsal "NP-úplný" místo "z třídy NP":
> Fairfax wrote:jsme schopni převést libovolný NP-úplný problém na KACHL.
Má být "libovolný problém *z třídy NP*".
> Někdo nám tedy dá NP-úplný problém **Q**
Má být "dá problém **Q** *z třídy NP*".
> tvrdí, že **Q** je NP-úplný
Má být "tvrdí, že **Q\[/Q] je *z třídy NP*".
Ale to asi každému dojde:).**
<{/ForumPost}>
<{ForumPost(poster="Fairfax", timestamp=2010-02-04 14:09:39)}>
> adam wrote:Jo, omylem jsi asi několikrát napsal "NP-úplný" místo "z třídy NP"
Opraveno.
Jak je člověk zvyklej převádět pořád něco NP-úplnýho na něco jinýho aby dokázal NP-těžkost, tak to snadno poplete.
Cook & Levin dokazujou NP-těžkost přímo z definice, takže stačí "z třídy NP" jak jsi správně poznamenal. Thx.
<{/ForumPost}>