{{theorem | <math>NPSPACE = PSPACE</math>

| Savičova, pro polynomy }}

Dk (formálně)

∀ DTS je zvláštním případem NTS.

Předpokládejme, že <math>L ∈ NPSPACE</math>, tedy existuje <math>k</math>, pro něž <math>L ∈ NSPACE(n^k)</math>.

Nechť <math>M</math> je NTS přijímající <math>L</math> v prostoru <math>n^k</math> a má BUNO !1 <math>K_F</math>.

Ukážeme, že existuje DTS <math>M’</math>, který přijímá <math>L</math> v prostoru <math>O(n^{2k})</math>.

Nechť <math>G_{M,x} = (V, E)</math> je konfigurační graf výpočtů <math>M</math> nad <math>x</math>, popíšeme algoritmus, který bude testovat to, jestli v <math>G_{M,x}</math> existuje cesta z <math>K_0</math> do !1 <math>K_F</math>, a vystačí si přitom s prostorem <math>O((log_2 |V|)^2)</math>.

Algoritmus popíšeme pomocí funkce <math>Dosažitelná(i, K_1, K_2)</math>, která zjistí, zda z konfigurace <math>K_1</math> je konfigurace <math>K_2</math> dosažitelná v nejvýše <math>2^i</math> krocích Turingova stroje <math>M</math>.

Pro volání <math>Dosažitelná(0, K_1, K_2)</math> funkce skontroluje, jestli je <math>K_2</math> přímo dosažitelná z <math>K_1</math>.

Pokud je <math>i > 0</math>, je <math>K_2</math> dosažitelná z <math>K_1</math> v nejvýš <math>2^i</math> krocích, pokud existuje konfigurace <math>K</math> ( foreach <math>K ∈ V</math> ) taková, že <math>K</math> je z <math>K_1</math> dosažitelná v nejvýš <math>2^{i-1}</math> krocích a <math>K_2</math> je z <math>K</math> dosažitelná v nejvýš <math>2^{i-1}</math> krocích, což ověříme dvojicí rekurzivních volání ( if <math>Dosažitelná(i-1, K_1, K)</math> && <math>Dosažitelná(i-1, K, K_2)</math> ).

Protože TS <math>M</math> přijímá jazyk <math>L</math> v prostoru <math>n^i</math>, existuje konstanta <math>c_M</math>, pro kterou je počet konfigurací <math>M</math> nejvýš <math>2^{c_M n^k}</math>, tedy voláním <math>Dosažitelná(c_M n^k , K_0 ,K_F)</math> zjistíme, je-li v GM, <math>x</math> dosažitelná v <math>2^{c_M n^k}</math> krocích, tedy, je-li vůbec dosažitelná.

Korektnost: Pokud je <math>i = 0</math>, znamená to, že <math>K_2</math> musí být z <math>K_1</math> dosažitelná v nejvýš jednom ( <math>=2^0</math> ) kroku, jinými slovy, buď <math>(K_1, K_2)</math> je hranou v <math>G_{M, x}</math>, nebo <math>K_1 = K_2</math>. Pokud je <math>i > 0</math>, je <math>K_2</math> dosažitelná z <math>K_1</math> v nejvýš <math>2^i</math> krocích, pokud existuje konfigurace <math>K</math> taková, že <math>K</math> je z <math>K_1</math> dosažitelná v nejvýš <math>2^{i-1}</math> krocích a <math>K_2</math> je z <math>K</math> dosažitelná v nejvýš <math>2^{i-1}</math> krocích, což ověříme dvojicí rekurzivních volání.

Zbývá odhadnout, jak velký prostor požaduje volání funkce <math>Dosažitelná</math>.

Prostor <math>O(n^{2k})</math>, kterého chceme dosáhnout nám neumožňuje uložit si v paměti celý graf <math>G_{M, x}</math>, protože už jen počet jeho vrcholů je exponenciální v <math>n</math>. Nám ale ve skutečnosti stačí umět otestovat pro dvě dané konfigurace <math>K_1</math> a <math>K_2</math>, zda <math>(K_1, K_2) ∈ E</math>, tedy zda lze z konfigurace <math>K_1</math> přejít do konfigurace <math>K_2</math> pomocí přechodové funkce stroje <math>M</math>.

K tomuto testu nám tedy stačí přechodová funkce, jejíž velikost je konstantní a nezávislá na <math>n = |x|</math>.

V cyklu potřebujeme postupně generovat všechny konfigurace. Na uložení jedné konfigurace nám stačí <math>c_M n^k</math> bitů, stačí tedy generovat všechny binární řetězce této délky a vybírat si ty, které kódují konfigurace. (💡 K zakódování konfigurace v podobě, s níž by se Turingovu stroji dobře pracovalo, můžeme ve skutečnosti potřebovat více bitů, než jen <math>c_M n^k</math>).

Použijeme-li například totéž kódování jako při kódování konfigurací pro důkaz TS ⇒ ČRF, postačí nám však stále <math>O(n^k)</math> bitů { kde v „<math>O</math>“ notaci se zde schovává i konstanta <math>c_M</math> }. Můžeme tedy předpokládat, že do konstanty <math>c_M</math> jsou již nároky na uložení kódu konfigurace započítány.

Hloubka rekurze je omezena pomocí <math>c_M n^k = O(n^k)</math>, protože to je počáteční hodnota <math>i</math>, které předáváme funkci jako parametr a v každém dalším voláním toto <math>i</math> snížíme o jedna. Dohromady tedy dostaneme, že celkový prostor, který k vykonání <math>Dosažitelná(G_{M,x}, c_M n^i, K_0, K_F)</math> potřebujeme, je velký <math>O(n^k . n^k ) = O(n^{2k})</math>.

Nebylo by také obtížné na základě této funkce vytvořit DTS <math>M</math> , který by vyžadoval týž prostor a přijímal jazyk <math>L</math>. Z toho plyne, že <math>L ∈ DSPACE(O(n^k)) ⊆ PSPACE</math>.

Zdroje

• http://ktiml.mff.cuni.cz/~kucerap/NTIN090/NTIN090-poznamky.pdf