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, 14.12.2015
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, 14.12.2015
<*> = ^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 ^ O(^)
IB102 Automaty, gramatiky a složitost, 14.12.2015
<*> = ^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>Wn 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, 14.12.2015
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, L), (g2, a, /?)}:
IB102 Automaty, gramatiky a složitost, 14.12.2015
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/+i j+i >ae
A
ai	a2	a3
a4	a5	a6
0
move
e C(n2/<)
IB102 Automaty, gramatiky a složitost, 14.12.2015
<*> = ^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, 14.12.2015
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       = O(n2k\o$n) = 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, 14.12.2015
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, 14.12.2015 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, 14.12.2015
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í <t>' v cnf pomocí ekvivalence
(<p A VO V p = ((f v p) A (ip v p)
IB102 Automaty, gramatiky a složitost, 14.12.2015
11/29
3SAT je NP-těžký
<t>' převedeme na <t>" v 3cnf pomocí vztahů
h v /2 v /3
/•) V /2 V /3 V /4
/! V /2 V ... V /,
O" je splnitelná
<t> je splnitelná. |<t>"| e C(n2/(). Tedy 4 <p 3SAT. □
IB102 Automaty, gramatiky a složitost, 14.12.2015
12/29
Lemma
Redukce a ť-těžkost
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ý, 4<peaeeNP, pak e je také NP-úplný.
IB102 Automaty, gramatiky a složitost, 14.12.2015 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, 14.12.2015
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, 14.12.2015 15/29
Příklad
M = ({<fo, q^, qaCc, Qrej}, {0,1}, {0,1, >, □}, >, u, S, q0l qacc, qrej)
S	>	0	1		u	
qo	(Qo,>,R)		(<h,1,		(qacc-, ~■>	")
		(qrej, ~, -)	(<h,1,		(qacc-, ~■>	")
IB102 Automaty, gramatiky a složitost, 14.12.2015
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
SMin) = ^- + n + 2.
m
Důkaz.
IB102 Automaty, gramatiky a složitost, 14.12.2015
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 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, 14.12.2015
18/29
SAT G SPACE(n)
SAT = {(<p) | cp je splnitelná Booleovská formule}
S/17" 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, 14.12.2015
19/29
Cas a prostor
Věta. Pro každou funkci /: N ->■ N platí:
□ TIME(7(/7)) c SPACE(7(n))
B NTIME(/(n)) c NSPACE(7(n))
□ SPACE(7(n)) c TIME(/cř(n)) pro vhodné keN
□ NSPACE(7(/7)) c NTIME(/cř(n)) pro vhodné keN
Důkaz.
IB102 Automaty, gramatiky a složitost, 14.12.2015
Savitchova věta
Savitchova věta. Pro každou funkci f: N -> N splňující f(rí) > n platí
NSPACE(f(n)) c SPACE(ř2(n))
Standardní převod nedeterministického TM na deterministický nefunguje
IB102 Automaty, gramatiky a složitost, 14.12.2015
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, 14.12.2015
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(ď, 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, 14.12.2015 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, 14.12.2015 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, 14.12.2015
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 = {((p) | 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, 14.12.2015 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(^/), 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 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, 14.12.2015
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 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, 14.12.2015 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, c 1 Je Pravdivá, právě když ^ = c2 nebo ci hrr c2.
proř>1: d>'CiCž)ř = 3mV(Q3,c4)G{(c1,/77),(m,c2)} (V^^
Pak* = 3c1,c2 (<t>Cl=Csfart A Q^cacc A ^^j)-Tedy |<t>| je polynomiální vzhledem k \ w\ = n a je pravdivá
w e A.
Celkem A <p 7Q8F pro každé A e PSPACE
IB102 Automaty, gramatiky a složitost, 14.12.2015
29/29