{{theorem | $NPSPACE=PSPACE$

| Savičova, pro polynomy }}

Dk (formálně) ::

:: ∀ DTS je zvláštním případem NTS. :: Předpokládejme, že $L\in NPSPACE$, tedy existuje $k$, pro něž $L\in 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((lo{g}_2|V|{)}^2)$. :: Algoritmus popíšeme pomocí funkce $Dosa\check{z}iteln\acute{a}(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\check{z}iteln\acute{a}(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\in 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\check{z}iteln\acute{a}(i-1,K_1,K)$ && $Dosa\check{z}iteln\acute{a}(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\check{z}iteln\acute{a}(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\check{z}iteln\acute{a}$. :: 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)\in 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\check{z}iteln\acute{a}(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\in DSPACE(O(n^k))\subseteq PSPACE$.

Zdroje ::

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