• Rq platí: D TIME(f(n)) c NTIME(f(n)) U SPACE{f{n)) c NSPACE(f(n)) □ TIME(f(n)) c SRACE(ř(n)) □ NTIME(f(n)) c NSPACE{f{n)) m SPACE(f(n)) c U,€N TIME(kf(n)) m NSPACE{f{n)) c y^eN NTIME{kfW) Důkaz: IB107 Vyčíslitelnost a složitost: prostorová složitost, vztahy složitostních tříd, TQBF 8/18 Savitchova věta Pro každou funkci f: N IRq splňující f(ri) > n platí: NSPACE(f(n)) c SPACE(f2(n)) Standardní převod nedet. TM na deterministický nefunguje: IB107 Vyčíslitelnost a složitost: prostorová složitost, vztahy složitostních tříd, TQBF 9/18 Savitchova věta Důkaz: Nechí Aí \e nedet. 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 c„ iniciální konfigurace stroje J\f pro w, stačí tedy spustit comp(cw,cacc,kŤ{n))- comp{c^, c2, ř) lze implementovat rekurzivně: IB107 Vyčíslitelnost a složitost: prostorová složitost, vztahy složitostních tříd, TQBF 10/18 Savitchova věta Algoritmus pro comp{c^, c2, t)\ t = 1: Otestujeme, zda platí c-i = c2 nebo Ci \rr Cz- N Pokud platí, akceptujeme, jinak zamítneme. t > 1: Pro každou konfiguraci ď stroje J\f využívající nejvýše f(n) políček ■ spustíme comp{c^, ď, [|]) a comp(cř, c2, r|]), ■ 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: ■ IB107 Vyčíslitelnost a složitost: prostorová složitost, vztahy složitostních tříd, TQBF 11/18 polynomiální prostorové složitostní třídy PSPACE = |J SPACE(n/c) NPSPACE = |J NSPACE^) Věta PSPACE = NPSPACE Důkaz: Plyne přímo z definice (c) a ze Savitchovy věty (d). IB107 Vyčíslitelnost a složitost: prostorová složitost, vztahy složitostních tříd, TQBF 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) L = LOGSPACE = SPACE(logn) NL = NLOGSPACE = NSPACE(logn) Příklad: {0* 1k |/c > 0} e L IB107 Vyčíslitelnost a složitost: prostorová složitost, vztahy složitostních tříd, TQBF 13/18 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: prostorová složitost, vztahy složitostních tříd, TQBF 14/18 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: prostorová složitost, vztahy složitostních tříd, TQBF 15/18 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
1: = Sni V(c3, c4) g {(C-|, /77), (/77, C2)} (V
Pak0 = 3o,,Q2 (