Kachlíkování pořádně

Základní přednáška o teorii složitosti algoritmů. Zhruba první polovina přednášky je věnována studiu složitosti konkrétních algoritmů různých typů (grafové, rozděl a panuj, hladové na matroidech) pracujících v polynomiálním čase. Složitost je zkoumána jak "klasicky" (složitost v nejhorším případě), tak amortizovaně. Druhá polovina přednášky je pak věnována studiu třídy NP, polynomiální převoditelnosti problémů a důkazům NP-úplnosti problémů. Závěr přednášky je věnován tématům souvisejícím se studiem NP-úplnosti: pseudopolynomiálním algoritmům a silné NP-úplnosti, početním úlohám a třídě #P.
Uživatelský avatar
adam
Matfyz(ák|ačka) level I
Příspěvky: 31
Registrován: 10. 1. 2007 12:36
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Kachlíkování pořádně

Příspěvek od adam »

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 (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?
  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 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.)
  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í?
Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: Kachlíkování pořádně

Příspěvek od Osiris »

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...
Osiris
Uživatelský avatar
macbeth
Matfyz(ák|ačka) level III
Příspěvky: 201
Registrován: 11. 2. 2005 14:48
Typ studia: Informatika Mgr.
Bydliště: PPraha
Kontaktovat uživatele:

Re: Kachlíkování pořádně

Příspěvek od macbeth »

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...
Nieco, co by nejavilo ziadne znamky bytia, teda by sa nijak neprejavovalo ako sucno, by nebolo niecim, ale prave nicim...
Uživatelský avatar
adam
Matfyz(ák|ačka) level I
Příspěvky: 31
Registrován: 10. 1. 2007 12:36
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Kachlíkování pořádně

Příspěvek od adam »

Osiris píše: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 píše: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:).
Naposledy upravil(a) adam dne 31. 1. 2010 14:38, celkem upraveno 1 x.
Uživatelský avatar
adam
Matfyz(ák|ačka) level I
Příspěvky: 31
Registrován: 10. 1. 2007 12:36
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Kachlíkování pořádně

Příspěvek od adam »

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.
Uživatelský avatar
adam
Matfyz(ák|ačka) level I
Příspěvky: 31
Registrován: 10. 1. 2007 12:36
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Kachlíkování pořádně

Příspěvek od adam »

adam píše: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!
Uživatelský avatar
Fairfax
Matfyz(ák|ačka) level I
Příspěvky: 28
Registrován: 17. 1. 2006 19:05
Typ studia: Matematika Mgr.
Kontaktovat uživatele:

Re: Kachlíkování pořádně

Příspěvek od Fairfax »

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).
Naposledy upravil(a) Fairfax dne 4. 2. 2010 13:59, celkem upraveno 1 x.
Uživatelský avatar
adam
Matfyz(ák|ačka) level I
Příspěvky: 31
Registrován: 10. 1. 2007 12:36
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Kachlíkování pořádně

Příspěvek od adam »

Fairfax píše: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.)
  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é.)
Uživatelský avatar
adam
Matfyz(ák|ačka) level I
Příspěvky: 31
Registrován: 10. 1. 2007 12:36
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Kachlíkování pořádně

Příspěvek od adam »

Jo, omylem jsi asi několikrát napsal "NP-úplný" místo "z třídy NP":
Fairfax píše: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:).
Uživatelský avatar
Fairfax
Matfyz(ák|ačka) level I
Příspěvky: 28
Registrován: 17. 1. 2006 19:05
Typ studia: Matematika Mgr.
Kontaktovat uživatele:

Re: Kachlíkování pořádně

Příspěvek od Fairfax »

adam píše: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.
Odpovědět

Zpět na „TIN062 Složitost I“