SAT jeNP-těžký
SAT = {(cp) | cp je splnitelná Booleovská formule}
SAT je NP-těžký, tj. A e NP       A <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 na w.
IB102 Automaty, gramatiky a složitost, 8.12.2014
1/29
SAT jeNP-těžký
Každý výpočet stroje J\í pracujícího v čase nk na slově w lze reprezentovat tablem:
Vytvoříme 0, aby platilo:
0 je splnitelné <=^> existuje akceptující tablo reprezentující výpočet na
IB102 Automaty, gramatiky a složitost, 8.12.2014
<*> = ^cell A 4>start A 0 move A ^accept
cDceN = "každé Xjj^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 <j<nk-\-3
se C
s,teC
ocelil ^0(A72/C)
IB102 Automaty, gramatiky a složitost, 8.12.2014
<*> = ^cell A 4>start A 0 move A ^accept
0start = "na prvním řádku je iniciální konfigurace pro w =    w2... wn"
0
start —
A X1)2)ťfc A X1)3)> A *1,4,wi A *1,5,w2 A ... A Xi>A7_|_3>Wh A *1,n+4,U A *1,n+5,U A ... A X^nk+2,u A x1,n/í+3,#
^startl e 0{nk)
IB102 Automaty, gramatiky a složitost, 8.12.2014
4/29
<l> = ^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, 8.12.2014
5/29
<*> = ^cell A 4>start A 0 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+3
W        x/V-1,ai A
i    i - i ^/+1,y-1,a4 legální okno i—i—i—i
x/\/-1,ai   A A X/,y+i,a3
A */+1,y,a5 A X/+1j/-+1>ae
A
ai	a2	a3
a4	a5	a6
0
move
e 0(a72/<)
IB102 Automaty, gramatiky a složitost, 8.12.2014
<*> = ^cell A 4>start A 0 move A ^accept
^accept = "v tablu je stav qacc"
^accept —      \/ xiJ,qacc
1 </<n/í+1 1 <j<nk+3
l^acceptl e 0{ndk)
IB102 Automaty, gramatiky a složitost, 8.12.2014
7/29
<*> = ^cell A 4>start A 0 move A ^accept
<D| = 0(n2k) + 0(nK) + 0(nZK) + 0(nZK) = 0(nZK)
2k
2.k
,2/c
Počet proměnných x/J?s závisí na n = | w\ a není pevně omezen Proměnnou lze zakódovat O(\og rí) znaky. Tedy       = 0(n2k log n) = 0(a72/c+1).
0) má polynomiální délku vzhledem k n = | w\ a lze spočítat v polynomiálním čase. Tedy A <p SAT.
IB102 Automaty, gramatiky a složitost, 8.12.2014
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 každá klauzule má právě 3 literály
IB102 Automaty, gramatiky a složitost, 8.12.2014 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, 8.12.2014
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, 8.12.2014
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 /y
O" je ekvivalentní * a |<t>"| e ^(n2*). Tedy ^ <p 3SAT
IB102 Automaty, gramatiky a složitost, 8.12.2014
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, 8.12.2014 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, 8.12.2014
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, 8.12.2014 15/29
Příklad
M = ({<fo, q^, C/acc, Qrej}, {O, 1}, {0,1, >, U}, >, U, 5, C/o, qacc, Qrej)
S	>	0	1		u	
Qo	(qo,>,R)		(<h,1,		[Qacc, ~■>	")
<7i		(Qrej, ~, -)			[Qacc, ~■>	")
IB102 Automaty, gramatiky a složitost, 8.12.2014
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.
m
Důkaz.
IB102 Automaty, gramatiky a složitost, 8.12.2014
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, 8.12.2014
18/29
SAT G SPACE(n)
SAT = {(<p) | <p je splnitelná Booleovská formule}
S/47" 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, 8.12.2014
19/29
Cas a prostor
Věta. Pro každou funkci /: N -> N platí:
□ TIME(/(n)) c SPACE(/(n))
B NTIME(/(/7)) c NSPACE(/(n))
□ SPACE(/(n)) c TIME(/c'(n)) pro vhodné /c g N
□ NSPACE(f(n)) c NTIME(/c'(n)) pro vhodné k e N
Důkaz.
IB102 Automaty, gramatiky a složitost, 8.12.2014
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, 8.12.2014
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 coA7?p(c1, c2, ř), která akceptuje, pokud lze ve stroji J\f během nejvýše t kroků přejít z konfigurace c-i do c2, jinak zamítá. Je-li cw iniciální konfigurace stroje J\f pro w, stačí tedy spustit comp(cw, cacc, kf^).
comp(ci, c2, ř) lze implementovat rekursivně:
IB102 Automaty, gramatiky a složitost, 8.12.2014
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, 8.12.2014 23/29
Polynomiální prostorové složitostní třídy
PSPACE = [J SPACEJ)        NPSPACE = |J NSPACE^)
Věta. PSPACE = NPSPACE
Důkaz. Plyne přímo z definice (c) a ze Savitchovy věty Q). □
IB102 Automaty, gramatiky a složitost, 8.12.2014 24/29
Vztahy prostorových a časových tříd
P c NP c NPSPACE = PSPACE c EXPTIME c NEXPTIME
IB102 Automaty, gramatiky a složitost, 8.12.2014
25/29
Problém TQBF
QBF = kvantifikované Booleovské formule (proměnné v doméně {0,1})
3xVy((xvy) A(-xv-y))
Předpokládáme, že QBF formule jsou v prenexní formě (tedy kvantifikátory jsou pouze na začátku formule).
Definice. Problém TQBF je problém rozhodnout, zda je daná QBF formule bez volných proměnných pravdivá.
TQBF = {(cp) | <p 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, 8.12.2014 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.
B 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, 8.12.2014
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 akceptují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 <t>, která je pravdivá, právě když existuje výpočet stroje M z iniciální konfigurace pro w cstart do akceptující konfigurace cacc s nejvýše kroky.
IB102 Automaty, gramatiky a složitost, 8.12.2014 28/29
TQBF je PSPACE-těžký
Induktivně definujeme formuli <t>'c c d(nk) říkající, že existuje výpočet stroje M z £| do c2 s nejvýše kroky:
■     c-1 je pravdivá, právě když ci = c2 nebo c-\ \-1-r c2.
pror>1: ^.^ř = 3/77V(c3,c4)e{(c1,m),(/77,c2)} (0^ ^ ,
Pak0 = 3d,c2 (00!=,
A <t>~,=,
A <t>'
Tedy |<t>| je polynomiální vzhledem k \ w\ = n a je pravdivá
W € A
Celkem /A <p 7QBF pro každé 4 e PSPACE
IB102 Automaty, gramatiky a složitost, 8.12.2014
29/29