Řešené otázky NTIN090/Savitch

Věta ( Savičova, pro polynomy ):  $ NPSPACE = PSPACE $

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