Kachlíkování pořádně

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:

1. Jak tedy při převodu na kachlíkování zvolíme rozměry té čtvercové sítě?

2. Je jasné ( :wink: ), že na horním kraji je potřeba sekvenci (q₀,x₁), x₂, ..., x_n z obou stran doplnit dostatečeným počtem hvězdiček. Jak ale určíme, kam ve spodním řádku umístit q_F?

3. 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_F 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.)

4. 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"}

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...

a pokial mam spravne poznamky, tak q_F je na dolnom okraji hned na zaciatku (stroj po prechode do q_y 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...

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 q_F je na dolnom okraji hned na zaciatku (stroj po prechode do q_y 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:).

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.

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!

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).

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 2S(n)-n, nebo raději 2S(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.)

2. 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"}

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:).**

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.