IB107 Vyčíslitelnost a složitost
sublineární prostorové složitostní třídy*, TQBF
Jan Strejček
Fakulta informatiky Masarykova univerzita
sublineární prostorové složitostní třídy
■ chceme podchytit prostor využívaný nad rámec vstupu
■ upravíme výpočetní model:
■ (vícepáskový) Turingův stroj se speciální vstupní páskou
■ vstupní páska je konečná, za vstupem je koncová značka <
■ vstupní pásku lze pouze číst, nelze na ni zapsat
■ čtení ze vstupní pásky se nezapočítává do počtu přečtených políček Sm(w)
■ v tomto modelu je každý regulární jazyk v SPACE(1)
IB107 Vyčíslitelnost a složitost: sublineární prostorové složitostní třídy*, TQBF
2/9
sublineární prostorové složitostní třídy
L = LOGSPACE = SPACE(logn) NL = N LOGSPACE = NSPACE(logn)
Příklad: {0*1 * | k > 0} e L
IB107 Vyčíslitelnost a složitost: sublineární prostorové složitostní třídy*, TQBF
3/9
vztah N L a P
A/L c P
Důkaz: Nechí >A g NL a A//\ je nedet. TM se speciální vstupní páskou rozhodující A s prostorovou složitostí c log n. Konfigurace Na je dána stavem, polohou hlavy na vstupní pásce, obsahem a polohou hlavy na pracovní pásce. Celkem konfigurací: \Q\ • \n + 2\ • |r|clo«n • (clogn+ 1)
Zkonstruujeme graf konfigurací Na pro vstup w, kde hrany odpovídají kroku výpočtu Na- Zjistíme, zda je z iniciální konfigurace dosažitelná nějaká akceptující konfigurace. ■
IB107 Vyčíslitelnost a složitost: sublineární prostorové složitostní třídy*, TQBF 4/9
vztahy prostorových a časových tříd
LCNLCPCNPC NPSPACE = PSPACE c EXPTIME c NEXPTIME
NL c PSPACE P c EXPTIME
IB107 Vyčíslitelnost a složitost: sublineární prostorové složitostní třídy*, TQBF 5/9
problém TQBF
QBF = kvantifikované výrokové formule (proměnné v doméně {0,1})
3xVy ((x v y) A (-.x V -.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 (true quantified Boolean formula))
Problém TQBF je problém rozhodnout, zda je daná QBF formule bez volných proměnných pravdivá.
TQBF = {((p) | (p je pravdivá QBF formule bez volných proměnných}
Věta 2.9
TQBF je PSPACE-úplný.
IB107 Vyčíslitelnost a složitost: sublineární prostorové složitostní třídy*, TQBF 6/9
TQBF je PSPACE-úplný
Důkaz: TQBF e PSPACE: lze řešit rekurzivní procedurou t(cp)\
D Je-li y tvaru 3x(cp'), 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 t((př[x h> 1]). Pokud obě volání akceptují, akceptujeme. Jinak zamítneme.
□ Pokud (p neobsahuje kvantifikátory, snadno vyhodnotíme a akceptujeme, pokud je <p pravdivá. Jinak zamítneme.
Prostorová složitost:
■ v jednom zavolání t si pamatujeme pouze něco konstantního
■ hloubka rekurzivního volání:
■ celkem:
IB107 Vyčíslitelnost a složitost: sublineární prostorové složitostní třídy*, TQBF
7/9
TQBFje PSPACE-úplný
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 O, 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.
IB107 Vyčíslitelnost a složitost: sublineární prostorové složitostní třídy*, TQBF 8/9
TQBF je PSPACE-úplný
Induktivně definujeme formuli ^ ^ ř říkající, že existuje výpočet stroje M z c-i do c2 s nejvýše ř kroky:
t = 1: 0;C1 C2 -i je pravdivá, právě když c-i = c2 nebo Ci
A4
C2
ř>1: = Sni V(C3, C4) g {(C-|, /77), (/77, C2)} (V
Pak <D = 3Ci, P2 (*c1=csřart A 0C2=cacc A ^^d(nk))-
| <t> | je polynomiální vzhledem k | iv| = n a 0 je pravdivá we/l Celkem A <p TQBF pro každé A e PSPACE. ■
IB107 Vyčíslitelnost a složitost: sublineární prostorové složitostní třídy*, TQBF 9/9