Fórum studentů MFF UK

Apropos, mě zase chybí VP na SP a VP na HK, může mně někdo naťuknout?

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

Kdyz jsme u toho, nemate nekdo prevod KACHL > SAT? Tento mi jako jediny chybi...

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

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

[url=http://www.algoritmy.net/article/8053/Turinguv-stroj--SAT]Převod NTS => SAT[/url]

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: