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í
Převod NTS=>SAT
-
- Admin(ka) level I
- Příspěvky: 635
- Registrován: 9. 6. 2005 12:33
- Typ studia: Informatika Mgr.
- Login do SIS: BUREJ3BM
- Bydliště: Konečně Vinohrady:)
- Kontaktovat uživatele:
Převod NTS=>SAT
When life gives you crap, make crap golems.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 16
- Registrován: 4. 6. 2007 09:37
- Typ studia: Informatika Mgr.
- Login do SIS: cunav5am
Re: Převod NTS=>SAT
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é...
Spíš mi celkově ty stránky přijdou zajímavé...
- Necroman
- Supermatfyz(ák|ačka)
- Příspěvky: 459
- Registrován: 20. 1. 2005 19:46
- Typ studia: Informatika Mgr.
- Login do SIS: suchm4am
- Bydliště: Louny / kolej Jednota, Praha
- Kontaktovat uživatele:
Re: Převod NTS=>SAT
Kdyz jsme u toho, nemate nekdo prevod KACHL > SAT? Tento mi jako jediny chybi...
WANTED:
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
-
- Admin(ka) level I
- Příspěvky: 635
- Registrován: 9. 6. 2005 12:33
- Typ studia: Informatika Mgr.
- Login do SIS: BUREJ3BM
- Bydliště: Konečně Vinohrady:)
- Kontaktovat uživatele:
Re: Převod NTS=>SAT
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:)
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.
-
- Admin(ka) level I
- Příspěvky: 635
- Registrován: 9. 6. 2005 12:33
- Typ studia: Informatika Mgr.
- Login do SIS: BUREJ3BM
- Bydliště: Konečně Vinohrady:)
- Kontaktovat uživatele:
Re: Převod NTS=>SAT
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.