SAT jeNP-těžký
SAT = {(cp) I cp je splnitelná Booleovská formule}
SAT je NP-těžký, tj. A e NP ^ /l <p SAT:
Nechť A/" je nedeterministický TM rozhodující A v čase nk. Pro každé slovo w sestrojíme Booleovskou formuli O, která je splnitelná, právě když stroj J\f má akceptující výpočet nad w.
IB102 Automaty, gramatiky a složitost, 9.12.2013
1/29
S AT jeNP-těžký
Každý výpočet stroje J\í pracujícího v čase nk nad slovem w lze reprezentovat tablem:
Vytvoříme 0, aby platilo:
<t> je splnitelné <=^> existuje akceptující tablo reprezentující výpočet na
IB102 Automaty, gramatiky a složitost, 9.12.2013
<*> = ^cell A 4>start A CD
move A ^accept
d>ceN = "každé x/J?s platí <=^> v tablu na pozici i J je symbol s,
kde s g C = Quru{#}"
*cell=   A   í(Vx^>)A ( A n(%A%))
1</< flfr+l
1 <y<n/í+4
se C
s,reC
ocelil ^0(A72/C)
IB102 Automaty, gramatiky a složitost, 9.12.2013
<*> = ^cell A 4>start A CD
move A ^accept
d>start = "na prvním řádku je iniciální konfigurace pro w =    w2... wn"
0
start —
A X1)2)ťfc A
^1,3,^1 ^ x1,4,w/2 A . . . *1,n+3,u A Xi,n+4,u A
A ^i,n+2,^ A
• • • A X-| ?A?/c+3?u A X-| ^+4^
^startl e 0(77*)
IB102 Automaty, gramatiky a složitost, 9.12.2013
4/29
<*> = ^cell A 0start A 4> move A ^accept
^move = "každé dva po sobě jdoucí řádky tabla odpovídají kroku výpočtu" popíšeme pomocí "legálních oken" 2x3
příklady legálních oken pro S(q^, b) = {(g2, c, /.), (g2, a, /?)}:
IB102 Automaty, gramatiky a složitost, 9.12.2013
5/29
<*> = ^cell A 4>start A <D move A ^accept
^move = "každé okno tabla je legální" (okna se překrývají)
0
move
A
1 </< A^ + l
1 <j<nk+4
W       x/V-1,ai A
i    i - i ^/+1,y-1,a4 legální okno i—i—i—i
A */+1,y,a5 A X/+1j/-+1>a6
A
ai	a2	a3
a4	a5	a6
d>
move
e 0(n2/<)
IB102 Automaty, gramatiky a složitost, 9.12.2013
<*> = ^cell A 4>start A <D move A ^accept
^accept = "v tablu je stav gacc"
^accept —      f\ xiJ,qacc
1 </<n/í+1 1 <j<nk+4
l^acceptl e 0{ndk)
IB102 Automaty, gramatiky a složitost, 9.12.2013
7/29
<*> = ^cell A 4>start A <D move A ^accept
4>| = 0(n2k) + 0(nK) + 0(nZK) + 0(nZK) = 0(nZK)
2k
,2/c
,2/c
Počet proměnných x,^s závisí na a? = | w\ a není pevně omezen Proměnnou lze zakódovat O(\og rí) znaky. Tedy       = 0(n2k log n).
ct>) má polynomiální délku vzhledem k a? = | w\ a lze spočítat v polynomiálním čase. Tedy A <p SAT.
IB102 Automaty, gramatiky a složitost, 9.12.2013
8/29
Konjunktivní normální forma (cnf) formulí
literál = je proměnná nebo její negace
klauzule = disjunkce literálů
formule v cnf = konjunkce klauzulí
formule v 3cnf = formule v cnf, kde všechny klauzule obsahují 3 literály
IB102 Automaty, gramatiky a složitost, 9.12.2013 9/29
Problém 3SAT
Problém 3SAT je problém rozhodnout, zda je daná Booleovská formule 3cnf formě splnitelná.
3SAT = {(<p) \<p\e splnitelná formule v 3cnf}
Věta. 3S47"je NP-úplný. Důkaz. 3SAT e NP:
IB102 Automaty, gramatiky a složitost, 9.12.2013
1
3S/\7jeNP-těžký
3SAT = {(cp) I cp je splnitelná formule v 3cnf}
3SAT je NP-těžký, tj. A e NP       A <p 3SAT: □ zkonstruujeme 0 jako v důkazu NP-těžkosti SATu
q 0 převedeme na ekvivalentní <t>' v cnf pomocí ekvivalence
(<p A VO V p = ((f V p) A (ip V p)
IB102 Automaty, gramatiky a složitost, 9.12.2013
11/29
3SAT je NP-těžký
<t>' převedeme na ekvivalentní <t>" v 3cnf pomocí ekvivalencí
h v /2 v /3
/! V /2 V /3 V /4
/! V /2 V ... V /j
d>" je ekvivalentní * a |<t>"| e ^(n2*). Tedy ^ <p 3SAT
IB102 Automaty, gramatiky a složitost, 9.12.2013
Redukce a C-těžkost
Lemma. Nechť C je složitostní třída.
A je C-těžký a A <p B       B je C-těžký
Důkaz.
□
Důsledek. Je-li >í NP-úplný, 4<peaeeNP, pak B je také NP-úplný.
IB102 Automaty, gramatiky a složitost, 9.12.2013 13/29
Prostorová složitost algoritmu
■ paměť použitá při výpočtu
■ závisí na vstupu
■ jako základní model použijeme Turingův stroj
■ zkoumáme nejhorší případ, tedy maximální počet přečtených políček pásky v závislosti na délce vstupu
■ lze zkoumat i průměrný případ
IB102 Automaty, gramatiky a složitost, 9.12.2013
14/29
Prostorová složitost Turingova stroje
Definice. Nechť M je úplný deterministický (jednopáskový nebo vícepáskový) Turingův stroj se vstupní abecedou Z. Pro každé i^gF definujeme Sm(w) jako počet políček pásky, které stroj M čte při výpočtu na vstupu w. Prostorová složitost stroje M je pak funkce SM ■ N0 N definovaná vztahem
SM(n) = max{sM(w) | w e Tn}.
Definice. Definice prostorové složitosti úplného nedeterministického Turingova stroje se liší pouze tím, že Sm(w) označuje maximální počet políček pásky, které stroj M čte při nějakém výpočtu na vstupu w.
Používáme asymptotickou notaci, protože prostor lze komprimovat.
IB102 Automaty, gramatiky a složitost, 9.12.2013 15/29
Příklad
M = ({cfo, q^, c/acc, Orej}, {0,1}, {0,1, >, u}, >, u, 6, c/o, qacc, qKj)
S	>	0	1		u	
Qo				R)	(<7acc> 5	-)
<7i		(<hj,-,-)	(<h,1,	R)	(<7acc> 5	-)
IB102 Automaty, gramatiky a složitost, 9.12.2013
16/29
Komprese prostoru
Věta. Pro každý deterministický úplný TM M a pro každé m > 1 lze zkonstruovat deterministický úplný TM M' tak, že L(M) = L(Mf) a
SMn) = ^ + n + 2.
Důkaz.
IB102 Automaty, gramatiky a složitost, 9.12.2013
Prostorové složitostní třídy problémů
prostorová složitost problému = nejmenší prostorová složitost, s jakou lze daný problém rozhodnout
Definice. Každá funkce /: N -> N definuje prostorové složitostní třídy problémů:
SPACE(/r(/i)) = {/_ | L je rozhodovaný nějakým deterministickým TM M
s prostorovou složitostí SM(n) = 0(f(n))}
NSPACE(/(a?)) = {L\L\e rozhodovaný nějakým nedet. TM J\í
s prostorovou složitostí Sx(n) = 0(f(n))}
IB102 Automaty, gramatiky a složitost, 9.12.2013
18/29
SAT e SPACE(n)
SAT = {((p) | (p je splnitelná Booleovská formule}
SAT může být rozhodován deterministickým třípáskovým TM M:
■ na 2. pásku postupně zapisujeme všechna ohodnocení proměnných
■ na 3. pásce pro dané ohodnocení ověříme, zda splňuje vstupní formuli
■ akceptujeme, pokud narazíme na splňující ohodnocení
■ zamítneme, pokud žádné ohodnocení není splňující
Prostor lze použít opakovaně.
IB102 Automaty, gramatiky a složitost, 9.12.2013
19/29
Cas a prostor
Věta. Pro každou funkci / : N ->■ N platí:
□ TIME(/(A7)) c SPACE(/(n))
B NTIME(/(A7)) c NSPACE(f(n))
El SPACE(/(n)) c TIME(/c^")) pro vhodné k e N
□ NSPACE(f(n)) c NTIME(/c^n)) pro vhodné k e N
Důkaz.
IB102 Automaty, gramatiky a složitost, 9.12.2013
Savitchova věta
Savitchova věta. Pro každou funkci /: N -> N splňující f(rí) > n platí
NSPACE(/(a?)) c SPACE(/2(a?))
Standardní převod nedeterministického TM na deterministický nefunguje
IB102 Automaty, gramatiky a složitost, 9.12.2013
21/29
Savitchova věta
Důkaz. Nechť A/" je nedeterministický TM s prostorovou složitostí f(ri). Stroj upravíme tak, aby před akceptováním smazal pásku a posunul hlavu zcela vlevo. Má tedy jen jednu akceptující konfiguraci cacc- Výpočet stroje má maximálně kf^ kroků.
Ekvivalentní deterministický stroj M implementuje proceduru comp(ci, c2, ř), která akceptuje, pokud lze ve stroji J\f během t kroků přejít z konfigurace c-i do c2, jinak zamítá. Je-li cw iniciální konfigurace stroje M pro w, stačí tedy spustit comp(cw, caCc, kf^).
coA7?p(c1, c2, ř) lze implementovat rekursivně:
IB102 Automaty, gramatiky a složitost, 9.12.2013
22/29
Savitchova věta
Algoritmus pro comp{^, c2, t):
t = 1: Otestujeme, zda platí c-i = c2 nebo Ci h/vr °2-Pokud platí, akceptujeme, jinak zamítneme.
t > 1: Pro každou konfiguraci c7 stroje J\f využívající max. f (n) políček
spustíme coA7?p(c1, c', [|]) a comp(d, c2, [|]).
Pokud obojí akceptuje, akceptujeme. Pokud žádné ď nevedlo k akceptování, zamítneme.
Prostorová složitost:
■ comp potřebuje prostor na c-i, c2, d a ř (a něco konstantního):
■ hloubka rekurzivního volání:
■ celkem: □
IB102 Automaty, gramatiky a složitost, 9.12.2013 23/29
Polynomiální prostorové složitostní třídy
PSPACE = |J SPACE^)        NPSPACE = |J NSPACE^)
/ceN k€N
Věta. PSPACE = NPSPACE
Důkaz. Plyne přímo ze Savitchovy věty.
IB102 Automaty, gramatiky a složitost, 9.12.2013
Vztahy prostorových a časových tříd
P c NP c PSPACE = NPSPACE c EXPTIME c NEXPTIME
IB102 Automaty, gramatiky a složitost, 9.12.2013
25/29
Problém TQBF
QBF = kvantifikované Booleovské formule (proměnné v doméně {0,1})
3xVy((x V y) A (-.x V ->y))
Definice. Problém TQBF je problém rozhodnout, zda je daná QBF formule bez volných proměnných pravdivá.
TQBF = {(</?} | <f je pravdivá QBF formule bez volných proměnných} Věta. TQBF je PSPACE-úplný.
Důkaz. Ukážeme, že TQBF e PSPACE a že TQBF je PSPACE-těžký. □
IB102 Automaty, gramatiky a složitost, 9.12.2013
26/29
TQBF g PSPACE
TQBF lze rozhodovat pomocí rekurzivní procedury t(cp)\
□ Pokud (p neobsahuje kvantifikátory, snadno vyhodnotíme a akceptujeme, pokud je <p pravdivá. Jinak zamítneme.
H Je-li (p tvaru 3x(^), spustíme t((p'[x h> 0]) a t((p'[x h> 1]). Pokud alespoň jedno z volání akceptuje, akceptujeme. Jinak zamítneme.
B Je-li (p tvaru Vx(^'), spustíme r(<p'[x h> 0]) a r(<p'[x h> 1]). Pokud obě volání akceptují, akceptujeme. Jinak zamítneme.
Prostorová složitost:
■ v jednom zavolání t si stačí pamatovat pouze něco konstantního.
■ hloubka rekurzivního volání:
■ celkem:
IB102 Automaty, gramatiky a složitost, 9.12.2013
27/29
TQBF je PSPACE-těžký
Ukážeme A e PSPACE       A <p TQBF.
Nechť M je TM s prostorovou složitostí nk rozhodující A. Tedy M pracuje v čase ďnk\ Předpokládáme, že M má jednu akcpetující konfiguraci cacc-Důkaz kombinuje myšlenky důkazů NP-těžkosti SATu a Savitchovy věty.
Pro každé slovo w sestrojíme QBF formuli 0       H(nk), která je pravdivá,
právě když existuje výpočet stroje M z iniciální konfigurace pro w cstart do nějaké akpetující konfigurace s nejvýše d(A?/í) kroky
IB102 Automaty, gramatiky a složitost, 9.12.2013 28/29
TQBF je PSPACE-těžký
Formuli budujeme induktivně:
^Ci.c^i je pravdivá práve když Ci = C2 nebo Ci h}vrc2-pro ř > 1: <t>Cl)C2)ř =
3m V(c3, c4) g {(o,, m), (m, c2)} (^,^1]
d>
Tedy |<t>| je polynomiální vzhledem k | w\ = n a je pravdivá <^> w e A, Celkem A <p TQBF pro každé A e PSPACE.
IB102 Automaty, gramatiky a složitost, 9.12.2013
29/29