{{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, Σ, δ, 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čí tedy zvolit$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žitelná(i, K_1, K_2)$, kde K jsou konfigurace NTS $M$ a i je číslo.

:: $Dosažitelná(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žitelná(i, K_1, K_2)$ rekurzivně zavolá $∀ K$: $Dosažitelná(⌊i/2⌋, K_1, K)$ a $Dosažitelná(⌈i/2⌉, K, K_3)$

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

:: Nechť $w$ je vstupní slovo, zavoláme $Dosažitelná(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žitelná$. :: 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 → N$ je funkce vyčíslitelná v prostoru $O(f(n))$, pro kterou platí, že $f(n) ≥ log_2 n$ pro všechna $n ∈ N$. Potom platí, že $NSPACE(f(n)) ⊆ 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)$.