{{theorem

| Nechť $M$ je libovolný TS (DTS nebo NTS), který pracuje v prostoru $f(n)$, pak existuje konstanta $c_M$ (jejíž hodnota je závislá na stroji $M$), pro kterou platí, že počet konfigurací $M$ je nejvýš $2^{c_{M}f(n)}$. | počet konfigurací TS/NTS

}}

Dk ::

:: Nechť $M=(Q,\Sigma ,\delta ,q_0,F)$. Konfigurace se skládá ze slova na pásce, polohy hlavy v rámci tohoto slova a stavu, v němž se stroj $M$ nachází. Délka slova na pásce je omezená $f(n)$, počet různých poloh hlavy v rámci tohoto slova je $f(n)$ a počet stavů je $|Q|$. Počet konfigurací je tedy shora omezen pomocí $|\Sigma|^{f(n)}f(n)|Q|\stackrel{rozepíšeme~pomocí~log}{=}2^{f(n)\log_2|\Sigma|}2^{\log_2f(n)}2^{\log_2|Q|}=

2^{f(n)\log_2|\Sigma|+\log_2f(n)+\log_2|Q|}\leq 2^{f(n)\cdot(\log_2|\Sigma|+1+\log_2|Q|)}$.Sta\check{c}\acute{ı}tedyzvolit$c_M = (log_2|Σ| + log_2|Q| + 1)$.

:(💡 ani nemusíme používat 2ku stačí nějaká konstanta $c$)

{{theorem | $NPSPACE=PSPACE$

| Savičova, pro polynomy }}

Image:Savich.jpg

Dk (NPSPACE ⊇ PSPACE) ::

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

Dk (NPSPACE ⊆ PSPACE - neformální dk, <Řešené_otázky_NTIN090/Savitch> nebo [http :: //ktiml.mff.cuni.cz/~kucerap/NTIN090/NTIN090-poznamky.pdf originální dk ve skriptech])

:: Pro NTS (pracující v NPSPACE) zkonstruujeme DTS pracující v polynomiálním prostoru (💡 i když čas může být exponenciální). :: Nechť NTS $M$ přijímající $L(M)$ v prostoru $O(p(n))$, pak DTS $M’$ přijímající stejný $L$ pracující v polynomiálním prostoru může být zkonstruován pomocí bool rekurzivní funkce $Dosa\check{z}iteln\acute{a}(i,K_1,K_2)$, kde K jsou konfigurace NTS $M$ a i je číslo.

:: $Dosa\check{z}iteln\acute{a}(i,K_1,K_2)$ vrátí: * true, pokud je $K_2$ dosažitelná z $K_1$ v nejvýše i krocích, * jinak false. :: Tedy volání např $Dosa\check{z}iteln\acute{a}(i,K_1,K_2)$ rekurzivně zavolá $\forall K$: $Dosa\check{z}iteln\acute{a}(\lfloor i/2\rfloor ,K_1,K)$ a $Dosa\check{z}iteln\acute{a}(\lceil i/2\rceil ,K,K_3)$

:(💡 alg. je zřejmě korektní)

:: Nechť $w$ je vstupní slovo, zavoláme $Dosa\check{z}iteln\acute{a}(i,K_0,K_F)$ (💡 z počáteční konfigurace do BÚNO jediné přijímající) a $i=2^{c_{M}p(n)}$. :: Potřebujeme $hloubka=|log(2^{c_{M}p(n)})|=O(p(n))$ rekurzivních volání a $prostor(K_i)=O(p(n))$ místa na každé úrovni rekurze (💡 recyklace, 2 rekurzivní volání mohou používat stejný prostor). :: Tedy $prostor=hloubka\cdot prostor(K_i)=O(p(n))\cdot O(p(n))=O(p(n{)}^2)$ místa na pásce pro všechna rekurzivní volání $Dosa\check{z}iteln\acute{a}$. :: Druhá mocnina polynomu je stále polynom a takže: $NPSPACE=PSPACE$.

{{Zdroje|

• http://math.feld.cvut.cz/demlova/teaching/e-tal/e-tal08.pdf

• http://www.utdallas.edu/~dzdu/cs6382/lect5.ppt

• http://en.wikipedia.org/wiki/Savitch%27s_theorem

}}

Image:Chpvenndiagram.jpg {{theorem

| Nechť $f:N\to N$ je funkce vyčíslitelná v prostoru $O(f(n))$, pro kterou platí, že $f(n)\ge lo{g}_{2}n$ pro všechna $n\in N$. Potom platí, že $NSPACE(f(n))\subseteq DSPACE(f^2(n))$. | Savičova, obecné znění

}}

Dk ::

:: Důkaz předchozí věty nikde nevyužíval žádných zvláštních vlastností polynomů, můžeme jej tedy zobecnit a dostat tak obecnou Savičovu větu. :: Ukázali jsme vlastně, že k otestování toho, jestli v obecném orientovaném grafu $G=(V,E)$ vede cesta z daného vrcholu $0$ do vrcholu $F$, stačí prostor $O(({\log }_2|V|{)}^2)$, pokud do tohoto prostoru nepočítáme prostor nutný k uložení grafu. :: Pokud tedy místo polynomu $p(n)$ použijeme obecnou funkci $f(n)$, dostaneme tvrzení, že $NSPACE(f(n))\subseteq DSPACE(f(n{)}^2)$.