{{theorem | $NPSPACE = PSPACE$

| Savičova, pro polynomy }}

Dk (formálně) ::

:: ∀ DTS je zvláštním případem NTS. :: Předpokládejme, že $L ∈ NPSPACE$, tedy existuje $k$, pro něž $L ∈ NSPACE(n^k)$. :: Nechť $M$ je NTS přijímající $L$ v prostoru $n^k$ a má BUNO !1 $K_F$. :: Ukážeme, že existuje DTS $M’$, který přijímá $L$ v prostoru $O(n^{2k})$. :: Nechť $G_{M,x} = (V, E)$ je konfigurační graf výpočtů $M$ nad $x$, popíšeme algoritmus, který bude testovat to, jestli v $G_{M,x}$ existuje cesta z $K_0$ do !1 $K_F$, a vystačí si přitom s prostorem $O((log_2 |V|)^2)$. :: Algoritmus popíšeme pomocí funkce $Dosažitelná(i, K_1, K_2)$, která zjistí, zda z konfigurace $K_1$ je konfigurace $K_2$ dosažitelná v nejvýše $2^i$ krocích Turingova stroje $M$. :: Pro volání $Dosažitelná(0, K_1, K_2)$ funkce skontroluje, jestli je $K_2$ přímo dosažitelná z $K_1$. :: Pokud je $i > 0$, je $K_2$ dosažitelná z $K_1$ v nejvýš $2^i$ krocích, pokud existuje konfigurace $K$ ( foreach $K ∈ V$ ) taková, že $K$ je z $K_1$ dosažitelná v nejvýš $2^{i-1}$ krocích a $K_2$ je z $K$ dosažitelná v nejvýš $2^{i-1}$ krocích, což ověříme dvojicí rekurzivních volání ( if $Dosažitelná(i-1, K_1, K)$ && $Dosažitelná(i-1, K, K_2)$ ). :: Protože TS $M$ přijímá jazyk $L$ v prostoru $n^i$, existuje konstanta $c_M$, pro kterou je počet konfigurací $M$ nejvýš $2^{c_M n^k}$, tedy voláním $Dosažitelná(c_M n^k , K_0 ,K_F)$ zjistíme, je-li v GM, $x$ dosažitelná v $2^{c_M n^k}$ krocích, tedy, je-li vůbec dosažitelná.

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

:: Zbývá odhadnout, jak velký prostor požaduje volání funkce $Dosažitelná$. :: Prostor $O(n^{2k})$, kterého chceme dosáhnout nám neumožňuje uložit si v paměti celý graf $G_{M, x}$, protože už jen počet jeho vrcholů je exponenciální v $n$. Nám ale ve skutečnosti stačí umět otestovat pro dvě dané konfigurace $K_1$ a $K_2$, zda $(K_1, K_2) ∈ E$, tedy zda lze z konfigurace $K_1$ přejít do konfigurace $K_2$ pomocí přechodové funkce stroje $M$. :: K tomuto testu nám tedy stačí přechodová funkce, jejíž velikost je konstantní a nezávislá na $n = |x|$. :: V cyklu potřebujeme postupně generovat všechny konfigurace. Na uložení jedné konfigurace nám stačí $c_M n^k$ 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 $c_M n^k$). :: 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 $O(n^k)$ bitů { kde v „$O$“ notaci se zde schovává i konstanta $c_M$ }. Můžeme tedy předpokládat, že do konstanty $c_M$ jsou již nároky na uložení kódu konfigurace započítány. :: Hloubka rekurze je omezena pomocí $c_M n^k = O(n^k)$, protože to je počáteční hodnota $i$, které předáváme funkci jako parametr a v každém dalším voláním toto $i$ snížíme o jedna. Dohromady tedy dostaneme, že celkový prostor, který k vykonání $Dosažitelná(G_{M,x}, c_M n^i, K_0, K_F)$ potřebujeme, je velký $O(n^k . n^k ) = O(n^{2k})$. :: Nebylo by také obtížné na základě této funkce vytvořit DTS $M$ , který by vyžadoval týž prostor a přijímal jazyk $L$. Z toho plyne, že $L ∈ DSPACE(O(n^k)) ⊆ PSPACE$.

Zdroje ::

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