SAT jeNP-těžký
SAT = {(cp) | Lp 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, 5.12.2016
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, 5.12.2016
<*> = ^cell A 4>start A 0 move A 0accept
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 </<n*+i 1 <j<nk-\-3
se C
s,teC
ocelil G0(a72/í)
IB102 Automaty, gramatiky a složitost, 5.12.2016
<l> = ^cell A 0start A 4> move A 0accept
0start = "na prvním řádku je iniciální konfigurace pro w = \n\ w2 ... wn"
0
start —
<t>start| eO(nk)
x^,^,# A x1>2>qb A x1)3>> A
^1,4,^1  A X|,5,i/i/2 A ... A X-|?n+3?M/n A
*1,n+4,u A X-|,n+5,u A ... A X-|?A?/<+2,u A Xl5A?/c+3?#
ib102 Automaty, gramatiky a složitost, 5.12.2016
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) = {((fe, c, L), (g2j a,
IB102 Automaty, gramatiky a složitost, 5.12.2016
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 <i<rř+J\ 1 <j<nk+3
W        x/j-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
0
move
e 0(a72/<)
IB102 Automaty, gramatiky a složitost, 5.12.2016
<*> = ^cell A 4>start A 0 move A ^accept
^accept = "v tablu je stav qacc"
^accept —      \/ xiJ,qacc
1 </<A?/í + 1
1 <j<nk+3
l^acceptl e 0{ndK)
IB102 Automaty, gramatiky a složitost, 5.12.2016
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(n2/clogn) = 0(n2/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, 5.12.2016
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, 5.12.2016 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. 3SAT\e NP-úplný. Důkaz. 3SAT e NP:
IB102 Automaty, gramatiky a složitost, 5.12.2016
1
3S/\7jeNP-těžký
3SAT = {(cp) I Lp 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í 0; v cnf pomocí ekvivalence
(<p A ip) V p = ((f v p) A (ip v p)
IB102 Automaty, gramatiky a složitost, 5.12.2016
11/29
3SAT je NP-těžký
<t>' převedeme na <t>" v 3cnf pomocí vztahů
h v/2 /1 v l2 v /3
/! V l2 V /3 V /4
/i V ^ V ... V /,
O" je splnitelná       0' je splnitelná       O je splnitelná g e>(n2/c). Tedy /\ <p 3SAT.
IB102 Automaty, gramatiky a složitost, 5.12.2016
Redukce a C-těžkost
Lemma. Nechť C je složitostní třída.
A je C-těžký a A <p B      e je C-těžký
Důkaz.
□
Důsledek. Je-li A NP-úplný, A <p B a e e NP, pak fí je také NP-úplný.
IB102 Automaty, gramatiky a složitost, 5.12.2016 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, 5.12.2016
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) = vnax{sM(w) \ w e Z"}.
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, 5.12.2016 15/29
Příklad
M = ({Qo, q^, <7acc, Qrej}, {O, 1}, {0,1, >, U}, >, U, 5, q0l Qacc, Qrej)
S	>	0	1		u	
Qo	(Qo,>,Fl)	(cfe,0,fí)	(Qi, 1,		\Qacc-, ~■>	-)
<7i		(Qrej,-, -)	(Qi, 1,		\Qacc-, ~■>	-)
IB102 Automaty, gramatiky a složitost, 5.12.2016
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(Mř) a
SM>(n) =
SM(n)
m
+ a7 + 2.
Důkaz.
IB102 Automaty, gramatiky a složitost, 5.12.2016
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 f: N0 -> K+ definuje prostorové složitostní třídy problémů:
SPACE(/r(n)) = {L | L je rozhodovaný nějakým deterministickým TM M
s prostorovou složitostí SM(n) = 0(f(n))}
NSPACE(ř(n)) = {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, 5.12.2016
18/29
SAT G SPACE(n)
SAT = {(<p) | (p je splnitelná Booleovská formule}
S/AT 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, 5.12.2016
19/29
Determinismus a nedeterminismus, čas a prostor
Věta. Pro každou funkci f : N0 ->• K+ platí:
D TIME(f(n)) c NTIME(ŕ(n))
B SPACE(f(n)) c NSPACE(f(n))
Q TIME(/(n)) c SPACE(/(n))
□ NTIME(ř(n)) c NSPACE(f(n))
m SPACE(f(n)) c TIME(/cř(n)) pro vhodné /c e N
Q NSPACE(f(n)) c NTIME(frřC>) pro vhodné k e N
Důkaz.
IB102 Automaty, gramatiky a složitost, 5.12.2016
20/29
Savitchova věta
Savitchova věta. Pro každou funkci f: N0 -> K+ splňující f(ri) > n platí
NSPACE(ř(n)) c SPACE(ř2(n))
Standardní převod nedeterministického TM na deterministický nefunguje
IB102 Automaty, gramatiky a složitost, 5.12.2016
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{c^, 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, 5.12.2016
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 ď stroje J\f využívající max. f (n) políček
spustíme comp{c^, ď, [|]) a comp(cř, c2, [|]).
Pokud obojí akceptuje, akceptujeme. Pokud žádné d nevedlo k akceptování, zamítneme.
Prostorová složitost:
■ comp potřebuje prostor na c-i, c2, d a t (a něco konstantního):
■ hloubka rekurzivního volání:
■ celkem: □
IB102 Automaty, gramatiky a složitost, 5.12.2016 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, 5.12.2016 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, 5.12.2016
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) | cp 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, 5.12.2016 26/29
TQBF g PSPACE
TQBF lze rozhodovat pomocí rekurzivní procedury ř(^):
□ Pokud (p neobsahuje kvantifikátory, snadno vyhodnotíme a akceptujeme, pokud je <p pravdivá. Jinak zamítneme.
H Je-li (p tvaru 3x(cpr), spustíme t(cpr[x h> 0]) a t(cpr[x h> 1]). Pokud alespoň jedno z volání akceptuje, akceptujeme. Jinak zamítneme.
B Je-li (p tvaru Vx(^/), spustíme t((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, 5.12.2016
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 d^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 0, 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, 5.12.2016 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 gK"*) kroky:
■ ^c, co 1 Je pravdivá, právě když ci = c2 nebo d ho-c2.
prof>1: ^c.cfe.ř = 3mV(c3,c4)e{(c1,m),(/77,c2)} (0^ ^ ,
Pak0 = 3d,C2 (<t>Cl=csřart A <D^=Cacc A */Ci;Cžd(n/<))-Tedy |<t>j 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, 5.12.2016
29/29