Převod NTS=>SAT

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.
gASK
Admin(ka) level I
Příspěvky: 635
Registrován: 9. 6. 2005 12:33
Typ studia: Informatika Mgr.
Bydliště: Konečně Vinohrady:)
Kontaktovat uživatele:

Převod NTS=>SAT

Příspěvek od gASK »

Pozdě, ale přece - odkaz na poměrně lidsky vysvětlený důkaz Cook-Levina (osobně se mi líbí víc než ten přes KACHL):

Převod NTS => SAT

V tom důkazu podle mne chybí zajištění, že hlava není na dvou místech najednou, což se dá udělat analogicky jako u stavů.

Taky to, že je stroj vždy alespoň v jednom stavu nám podle mně zajišťuje ta počáteční podmínka a přechodová fce, ale formule navíc ničemu nevadí :wink:
When life gives you crap, make crap golems.
cunav5am
Matfyz(ák|ačka) level I
Příspěvky: 16
Registrován: 4. 6. 2007 09:37
Typ studia: Informatika Mgr.

Re: Převod NTS=>SAT

Příspěvek od cunav5am »

No, záleží na názoru, co je jednodušší. Já osobně souhlasím s Čepkem v tom, že KACHL>=SAT je jednodušší než NTS>=SAT. Ale pokud jde jen o SAT, tak je lepší dělat ten převod rovnou.

Spíš mi celkově ty stránky přijdou zajímavé...
Uživatelský avatar
Necroman
Supermatfyz(ák|ačka)
Příspěvky: 459
Registrován: 20. 1. 2005 19:46
Typ studia: Informatika Mgr.
Bydliště: Louny / kolej Jednota, Praha
Kontaktovat uživatele:

Re: Převod NTS=>SAT

Příspěvek od Necroman »

Kdyz jsme u toho, nemate nekdo prevod KACHL > SAT? Tento mi jako jediny chybi...
WANTED:
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
gASK
Admin(ka) level I
Příspěvky: 635
Registrován: 9. 6. 2005 12:33
Typ studia: Informatika Mgr.
Bydliště: Konečně Vinohrady:)
Kontaktovat uživatele:

Re: Převod NTS=>SAT

Příspěvek od gASK »

KACHL na SAT jsme řešili na minulém sezení. Je to analogicky tomu důkazu:

v podstatě si uděláš podmínky Qijk, tedy že na pozici Q je kachl k, poté si uděláš sady podmínek:
=na každé pozici je alespoň jeden kachl
=na žádné pozici nejsou dva kachly
=každý kachl je kompatibilní se svým sousedem nahoře-vlevo-vpravo-dole
=každý krajní kachl je kompatibilní s okrajem

To je vše:)
When life gives you crap, make crap golems.
gASK
Admin(ka) level I
Příspěvky: 635
Registrován: 9. 6. 2005 12:33
Typ studia: Informatika Mgr.
Bydliště: Konečně Vinohrady:)
Kontaktovat uživatele:

Re: Převod NTS=>SAT

Příspěvek od gASK »

Apropos, mě zase chybí VP na SP a VP na HK, může mně někdo naťuknout?
When life gives you crap, make crap golems.
Odpovědět

Zpět na „TIN062 Složitost I“