Složitost a NP-úplnost

RNDr. Ondřej Čepek, Ph.D.

Do formátu TEX převedl Ladislav Strojil Připomínky, dotazy, opravy na emailu: Ladislav@Strojil.cz

Verze 1.1.1

Nejnovější verze k nalezení vždy na http://ladislav.strojil.cz/np.php

Obsah

1 Základní definice 2 1.1 Výpočetní model . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Kódování Turingových strojů . . . . . . . . . . . . . . . . . . . . 3 1.3 Univerzální Turingův stroj . . . . . . . . . . . . . . . . . . . . . . 3 1.4 Zpracování výjimek . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5 Nedeterminismus . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.6 Prostorová složitost . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.7 Časová složitost . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.8 Nedeterministická prostorová a časová složitost . . . . . . . . . . 4

2 Základní třídy složitosti 5

3 Prostorová a časová komprese 5

3.1 Prostorová komprese . . . . . . . . . . . . . . . . . . . . . . . . . 5

3.1.1 Redukce počtu pásek . . . . . . . . . . . . . . . . . . . . . 6 3.2 Časová komprese . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.2.1 Redukce počtu pásek . . . . . . . . . . . . . . . . . . . . . 9

4 Konstruovatelnost funkcí 12

5 Hierarchie tříd složitosti 15 5.1 Časová hierarchie . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5.2 Prostorová hierarchie . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.3 Věty o hierarchii . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.4 Věta o vtazích mezi třídami složitosti . . . . . . . . . . . . . . . 18 5.5 Savičova věta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

6 Pokročilé věty o třídách složitosti 21 6.1 Věta o mezerách (Borodin) . . . . . . . . . . . . . . . . . . . . . 23 6.2 Věta o zrychlení . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1 Základní definice

1.1 Výpočetní model

Definice 1 (Turingův stroj).

Deterministický Turingův stroj (DTS) M s k-páskami, kde k je konstanta, je pětice

M = (Q, Σ, δ, q_{0}, F) (1) Q = konečná množina stavů řídící jednotky Σ = konečná pásková abeceda δ : Q × Σ^{k} ↦ Q × Σ^{k−1} × {L, N, R}^{k} je přechodová funkce (částečná) q_{0} ∈ Q = počáteční stav F ⊆ Q = množina přijímajících stavů Následující definice popisuje Turingovy stroje trochu podrobněji a uvádí

vysvětlení základních pojmů používaných ve vztahu k tomuto modelu. Definice 2.

• Všech k pásek je jednosměrně (potenciálně) nekonečných.

• Jedna z pásek je vstupní a pouze ke čtení.

• Na všech páskách se lze pohybovat oběma směry (off-line model), v on-line modelu se lze na vstupní pásce pohybovat pouze doprava.

• Konfigurace Turingova stroje je určena 1) stavem řídící jednotky

2) pozicí hlav na jednotlivých páskách

3) slovy na jednotlivých páskách (obsahem pásek)

• Počáteční konfigurace Turingova stroje 1) q_{0}

2) všechny hlavy zcela vlevo

3) na vstupní pásce vstupní slovo, ostatní pásky prázdné

• Displej Turingova stroje je stav řídící jednotky a obsah políček pod hlavami.

• Krok Turingova stroje je použítí přechodové funkce na displej, přepsání políček poh hlavami a případný posun hlav a změna stavu.

• Výpočet Turingova stroje je posloupnost kroků začínající v počáteční konfiguraci, která končí zastavením stroje nebo je nekonečná.

• Zastavení Turingova stroje je situace, kdy pro daný displej není přechodová funkce definována (předpokládá se, že to platí pro všechna q ∈ F).

• Přijímající výpočet Turingova stroje je výpočet končící zastavením v přijímajícím stavu (vstupní slovo je přijato).

• Odmítající výpočet Turingova stroje je výpočet končící zastavením v jiném než přijímajícím stavu nebo nekonečný.

• Přijímaný jazyk Turingova stroje M značíme L(M) a definujeme jako {w ∈ Σ^{∗}|w w je přijímáno M}.

Definice 3 (Transducer). Turingův stroj, který má navíc výstupní pásku, na kterou lze pouze psát (znak pod hlavou neovlivňuje přechodovou funkci) a na které se hlava může pohybovat pouze vpravo, nazýváme transducer. (Stroj bez této pásky se nazývá acceptor).

Existují různé varianty Turingových strojů, o kterých lze ukázat, že mají stejnou výpočetní sílu, tedy že přijímají stejnou třídu jazyků (rekurzivně spočetné množiny). Jsou to například:

• on-line Turingovy stroje;

• jednopáskové Turingovy stroje;

• Turingovy stroje s oboustranně nekonečnou páskou;

• Turingovy stroje s více hlavami na jedné pásce.

Důvody, proč je výhodné používat Turingovy stroje jako výpočetní model jsou zřejmé. Předně je to jasně definovaný koncept časové složitosti výpočtu (běhu algoritmu) jako počet kroků daného Turingova stroje nad daným vstupem. Analogicky jasně definovaný koncept prostorové složitosti výpočtu (běhu algoritmu) jako počet použitých buněk na pracovních páskách stroje.

Hlavní nevýhodou je fakt, že tento model je příliš elementární a nehodí se ke ”skutečnému programování”.

1.2 Kódování Turingových strojů

1) Očíslujeme stavy q ∈ Q a symboly s ∈ Σ binárními čísly.

2) Popíšeme přechodovou funkci v abecedě A = {0, 1, δ, (,), =, L, N, R, , } zřetězením zápisů typu δ(q, x_{1}, x_{2}, …, x_{k}) = (q′, y_{1}, …, y_{k}, Z).

3) Přepíšeme zápis z abecedy A do abecedy {0, 1}

Potom při pevně zvoleném kódování každý Turingův stroj jednoznačně odpovídá přirozenému číslu.

Definice 4 (Gödelovo číslo). Kód Turingova stroje M budeme nazývat jeho Gödelovým číslem.

1.3 Univerzální Turingův stroj

Definice 5 (Univerzální Turingův stroj). Univerzální Turingův stroj je Turingův stroj, který má jako vstup Gödelovo číslo nějakého Turingova stroje M a pro vstupní slovo w pro M pracuje tak, že simuluje práci M nad w.

1.4 Zpracování výjimek

Pomocí přidání nových stavů řídící jednotky lze jednoduše ošetřit libovolnou pevně danou konečnou množinu vstupů.

Provedeme to tak, že zkontruujeme konečný automat (strom) rozpoznávající danou konečnou množinu slov (konečný automat odpovídá Turingově stroji bez pásek).

Turingův stroj potom napřed simuluje chod daného konečného automatu. V případě, že je na vstupu jedno z rozpoznávaných slov, Turingův stroj se zastaví.

Pokud ne, odjede hlavou na vstupní pásce na začátek a spustí původní Turingův stroj.

1.5 Nedeterminismus

Od deterministického Turingova stroje se jeho nedeterministická varianta liší pouze definicí přechodové funkce a stanovením odlišných podmínek, za kterých je slovo přijato.

Definice 6 (Nedeterministický turingův stroj).

Definujme stroj jako v definici deterministického Turingova stroje s následujícími rozdíly:

• δ : Q × Σ^{k} ↦ P(Q × Σ^{k−1} × {L, N, R}^{k}) je přechodová funkce (částečná)

• Slovo w je přijímáno, jestliže existuje alespoň jeden přijímající výpočet.

Pro zjednodušení můžeme předpokládat binární větvení výpočetu. Snadno se dá ukázat, že se jedná o výpočetně ekvivalentní model.

1.6 Prostorová složitost

Definice 7.

Necht’ M je deterministický Turingův stroj, pro který platí, že na každém vstupu délky n použije při výpočtu nejvýše S(n) buněk na pracovních páskách. Potom říkáme, že M má prostorovou složitost S(n) a že jazyk L(M) má prostorovou složitost S(n).

1.7 Časová složitost

Definice 8.

Necht’ M je deterministický Turingův stroj, pro který platí, že na každém vstupu délky n provede při výpočtu nejvýše T (n) kroků, než se zastaví. Potom říkáme, že M má časovou složitost T (n) a že jazyk L(M) má časovou složitost T (n).

1.8 Nedeterministická prostorová a časová složitost

Definice jsou stejné jako u deterministických Turingůvých strojů s tím, že nyní požadujeme, aby ∀w ∈ Σ^{∗}, |w| = n všechny možné výpočty použily nejvýše S(n) políček a skončily nejdéle za T (n) kroků.

2 Základní třídy složitosti

DSP ACE(S(n)) = třída jazyků deterministické prostorové složitosti S(n)
NSP ACE(S(n)) = třída jazyků nedeterministické prostorové složitosti S(n)
DT IME(T (n)) = třída jazyků deterministické časové složitosti T (n)
NT IME(S(n)) = třída jazyků nedeterministické časové složitosti T (n)

Tvrzení 1 (Triviální vztahy).

∀ S(n) : DSP ACE(S(n)) ⊆ NSP ACE(S(n))  (2)
∀ T (n) : DT IME(T (n)) ⊆ NT IME(T (n))  (3)
∀ S_{1}(n) ≤ S_{2}(n) ⇒ DSP ACE(S_{1}(n)) ⊆ DSP ACE(S_{2}(n))  (4)
NSP ACE(S_{1}(n)) ⊆ NSP ACE(S_{2}(n))
∀ T_{1}(n) ≤ T_{2}(n) ⇒ DT IME(T_{1}(n)) ⊆ DT IME(T_{2}(n))  (5)
NT IME(T_{1}(n)) ⊆ NT IME(T_{2}(n))

Důkaz. Zřejmé.

3 Prostorová a časová komprese

3.1 Prostorová komprese

Věta 1 (O lineární prostorové kompresi).

Necht’ L je jazyk přijímaný k-páskovým deterministickým Turingovým strojem M s prostorovou složitostí S(n). Potom pro ∀r ∈ N^{+} existuje k-páskový deterministický Turingův stroj M’ s prostorovou složitostí ⌈\frac{1}{r}S(n)⌉, který přijímá jazyk L.

Důkaz. Každý znak abecedy stroje M’ bude kódovat jednu r-tici znaků abecedy původního stroje. |Σ_{M′}| (velikost abecedy M’) bude rovno |Σ_{M}|^{r} a vzhledem ke konečnosti Σ_{M} bude také konečná.

Jeden krok stroje M bude simulován jedním krokem stroje M’. Pozici původního stroje ”uvnitř” políčka si stroj M′ bude pamatovat ve stavech.

Nejprve necht’ k = 1.

Je-li Q_{M} = {q_{0}, q_{1}, …, q_{s}} množina stavů stroje M, potom definujeme Q_{M′} = {q_{0}^{1}, q_{0}^{2}, …, q_{0}^{r}, …, q_{s}^{1}, q_{s}^{2}, …, q_{s}^{r}}.

Přechodová funkce δ_{M′} bude simulovat pohyb hlavy změnou horního indexu stavu, v případě, že by index klesl na nulu nebo byl větší než r, dojde k vlastnímu posunu hlavy (stroje M’).

Všechna pravidla tvaru δ_{M}(q_{i}, a) = (q_{j}, b, N) nahradíme množinou pravidel δ_{M′}(q_{i}^{l}, x^{l}) = (q_{j}^{l}, y^{l}, N), ∀ 1 ≤ l ≤ r, ∀ dvojice x, y ∈ Σ_{M′}, kde x kóduje (…, a, …) a y kóduje (…, b, …) (y se liší od x pouze na l-té pozici).

Všechna pravidla tvaru δ_{M}(q_{i}, a) = (q_{j}, b, R) nahradíme množinou pravidel δ_{M′}(q_{i}^{l}, x^{l}) = (q_{j}^{l+1}, y^{l}, N), ∀ 1 ≤ l < r a δ_{M′}(q_{i}^{r}, x^{l}) = (q_{j}^{1}, y^{r}, R).

Analogicky pro pohyb doleva. δ_{M}(q_{i}, a) = (q_{j}, b, L) nahradíme množinou pravidel δ_{M′}(q_{i}^{l}, x^{l}) = (q_{j}^{l−1}, y^{l}, N), ∀ 1 < l ≤ r a δ_{M′}(q_{i}^{1}, x^{l}) = (q_{j}^{r}, y^{1}, L).

Nyní pro obecné k.

Q_{M′} = {q_{i}^{p}| 0 ≤ i ≤ s, ∀p ∈ Σ_{M}^{r}}

Proměnná p zde probíhá přes všechny r-tice znaků abecedy Σ_{M}.

Analogicky jako pro případ k = 1 se sestrojí přechodová funkce δ_{M′}.

Důsledek 1.

∀ r ∈ N^{+} : DSP ACE(S(n)) = DSP ACE(⌈\frac{S(n)}{r}⌉)

Důkaz. Plyne přímo z věty 1.

Věta 2.

∀ r ∈ N^{+} : NSP ACE(S(n)) = NSP ACE(⌈\frac{S(n)}{r}⌉)

Důkaz. Zobecněním důkazu věty 1 pro nedeterministický případ.

3.1.1 Redukce počtu pásek

Věta 3 (O redukci počtu pásek pro prostorovou složitost).

Necht’ L je jazyk přijímaný k-páskovým deterministickým Turingovým strojem s prostorovou složitostí S(n). Potom existuje deterministický Turingův stroj M′ s jednou pracovní páskou a prostorovou složitostí S(n) přijímající jazyk L.

Důkaz. Myšlenka důkazu: i-té políčko na pásce stroje M′ bude kódovat obsah k políček (z každé pásky stroje M jedno). Dále bude v políčku zakódována kromě obsahu původních pásek i informace, které z hlav se nachází nad tímto políčkem.

Nová abeceda bude definována následovně: Σ_{M′} = {x_{0}, …, x_{2^{k}−1}|∀x ∈ Σ_{M}^{k}} Indexy si můžeme představit v jejich binárním zápisu jako informaci o tom,

které hlavy simulovaného stroje M se nachází nad daným políčkem.

Jeden krok stroje M je simulován v O(S(n)) krocích stroje M′ tak, že hlava projde celou pásku, najde pozice hlav a odsimuluje krok M.

Vzhledem k tomu, že při simulaci nám nezáleží na časové složitosti, lze pro jednoduchost uvažovat výpočet, který má k fází a v každé fázi se odsimuluje práce M na jediné pásce. Na začátku fáze a po jejím ukončení bude hlava M′ na začátku pásky.

Jak bude probíhat samotná simulace? Každou instrukci původního stroje nahradíme posloupností instrukcí M′, kde stavy řídící jednotky M′ obsahují informaci o displeji stroje M. Tato posloupnost začíná s počátečním displejem a končí s koncovým displejem simulované instrukce.

1) Instrukce M očíslujeme a tato čísla zakódujeme do stavů M′. Tím zajistíme, že po začátku provádění posloupnosti instrukcí bude tato posloupnost dokončena a nebudou se míchat různé posloupnosti mezi sebou. Dále si budeme ve stavu pamatovat číslo aktuální fáze (počet fází je omezen počtem pásek, to znamená konečný a pevně daný). Výsledný počet stavů je tedy také konečný.

2) instrukci δ_{M}(q_{i}, a_{1}, …, a_{k}) = (q_{j}, b_{1}, …, b_{k}, z_{1}, …, z_{k}), která má číslo l, nahradíme posloupností stavů: (l, q_{i}, a_{1}, …, a_{k}, 1^{R}). Stroj M′ začíná v tomto stavu na první pozici své pracovní pásky. Nyní M′ projde pásku směrem doprava a hledá políčko, ve kterém je označena pozice první hlavy.

• Když x nekóduje pozici první hlavy, δ_{M′}((l, q_{i}, a_{1}, …, a_{k}, 1^{R}), x) =

((l, q_{i}, a_{1}, …, a_{k}, 1^{R}), x, R).

• Když x kóduje pozici první hlavy, rozlišíme následující případy podle směru, kterým by se první hlava posunula při práci stroje M.

a) z_{1} = N znak x kódující (a_{1}, a_{2}, …, a_{k}) se přepíše na znak y kódující (b_{1}, a_{2}, …, a_{k}) se stejnou množinou hlav. Zároveň se provede aktualizace displeje a 1^{R} se změní na 1^{L}. δ_{M′}((l, q_{i}, a_{1}, …, a_{k}, 1^{R}), x) = ((l, q_{j}, b_{1}, a_{2}, …, a_{k}, 1^{L}), y, N)

b) z_{1} = R znak x kódující (a_{1}, a_{2}, …, a_{k}) se přepíše na znak y kódující (b_{1}, a_{2}, …, a_{k}) se stejnou množinou hlav, s vyjímkou první hlavy. δ_{M′}((l, q_{i}, a_{1}, …, a_{k}, 1^{R}), x) = ((l, q_{j}, b_{1}, a_{2}, …, a_{k}, 1^{N}), y, R) δ_{M′}((l, q_{j}, a_{1}, …, a_{k}, 1^{N}), z) = ((l, q_{j}, b_{1}, a_{2}, …, a_{k}, 1^{L}), z′, N) Zde z′ kóduje stejnou k-tici jako z, ale navíc kóduje přítomnost první hlavy.

c) z_{1} = L. Zcela analogicky s případem R.

• Po a,b,c následuje odjezd hlavy M’ na začátek pásky a přepnutí do stavu (l, q_{j}, b_{1}, a_{2}, …, a_{k}, 2^{R}).

• Simulace dále pokračuje další fází.

Věta 4 (Nedeterministická verze).

Věta 3 platí ve stejném znění i pro nedeterministické Turingovy stroje.

Důkaz. Simulace uvedená v důkazu věty 3 je použitelná beze změn i pro případ nedeterministického Turingova stroje.

3.2 Časová komprese

Lemma 1 (O lineárním zrychlení).

Necht’ L je jazyk přijímaný k-páskovým deterministickým Turingovým strojem M s časovou složitostí T (n). Dále necht’ platí k ≥ 2 a necht’ r je celé číslo, r > 0.

Potom existuje deterministický Turingův stroj M′ takový, že každý vstup w délky n přijímá právě, když jej přijímá M. Pracuje-li M nad w t kroků, pracuje M′ nad w v čase n + ⌈n/r⌉ + 6⌈t/r⌉.

Poznámka: Předpokládáme, že na vstupní pásku je možno zapisovat.

Důkaz. V první fázi zkopíruje M′ obsah vstupní pásky na pracovní pásku (ta existuje, nebot’ k ≥ 2), současně s kopírováním M′ provede překódování vstupu tak, že v jednom políčku cílové pásky je kódováno r políček vstupní pásky, kde r je libovolné celé číslo > 0. Po provedení se vrátí na začátek pásky. Nadále bude tuto pásku používat jako vstupní.

Simulace M: Konkrétní ”jemnou” pozici vrámci jedné buňky nového stroje si budeme pamatovat ve stavech stroje M′.

• Stroj provede sekvenci pohybů vlevo, vpravo, vpravo, vlevo (4 kroky), pričemž si ve stavech zapamatuje obsah sousedních políček. Tím stroj získal informaci o políčku pod hlavou, políčku vpravo od hlavy a políčku vlevo od hlavy (všimněte si, že se jedná o 3·r políček stroje M).

• V další fázi M′ zjistí stav těchto 3r políček stroje M po r krocích. Uvědomte si, že během r kroků stroj M nemůže tato políčka opustit, nebot’ se jeho hlava nacházela v prostřední třetině tohoto úseku. Navíc změna stavu tohoto úseku obsahuje jenom konečnou informaci a tedy může být zakódována do přechodové funkce. Tedy celá tato fáze odpovídá 1 kroku stroje M′. Není potřeba jej ale započítávat do délky výpočtu, nebot’ získání potřebné informace lze provést již v posledním kroku předchozí fáze (návrat hlavy nad prostřední políčko bude spojen s přechodem do odpovídajícího stavu).

Navíc je zřejmé, že stroj M mohl během těchto r kroků modifikovat nejvýše 2 z těchto úseků (každý má totiž délku r, navíc nemohl modifikovat oba krajní úseky současně). V případě, že modifikoval pouze prostřední políčko, lze jeho nový obsah zapsat během jednoho kroku (v takovém případě udělá stroj jeden prázdný krok), jinak budou potřeba dva kroky (doprava a doleva, v odpovídajícím pořadí, podle toho, které z krajních políček bylo změněno).

• Stroj M′ přijme či odmítne, jestliže stroj M během simulovaného úseku přijmul či odmítnul.

Předzpracování vstupní pásky vyžadovalo n + ⌈n/r⌉ kroků (druhý sčítanec odpovídá času potřebnému pro návrat hlavy na začátek pásky).

Pro simulaci t kroků je zapotřebí ⌈t/r⌉ bloků výpočtu M′, z nichž každý trvá 6 kroků.

V součtu dostáváme tvrzení lemmatu.

Věta 5 (O lineárním zrychlení).

Necht’ L je jazyk přijímaný k-páskovým deterministickým Turingovým strojem M s časovou složitostí t(n). Dále necht’ platí k ≥ 2 a t(n) ∈ ω(n). Potom pro ∀c > 0 existuje k-páskový deterministický Turingův stroj M’ s časovou složitostí c · t(n) přijímající L.

Důkaz. Necht’ r je celé číslo takové, že r > 12/c. Sestrojíme M′ jako v předcházejícím lemmatu. M′ pracuje nad vstupem délky n v čase n+⌈n/r⌉+6⌈t(n)/r⌉. Pro r ≥ 2 lze tento výraz zhora omezit jako 2n + 6 + (6/r) · t(n).

Z předpokladu t(n) ∈ ω(n) dostáváme, že pro skoro všechna n je tento výraz menší než (c/2) · t(n) + (6/r) · t(n). Z volby r > 12/c dostáváme, že čas výpočtu je omezen c · t(n).

Konečně mnoho případů, pro které není nerovnost splněna, ošetříme konečným automatem a stroj M′ nad nimi bude pracovat v konstantním čase.

Důsledek 2.

Pokud t(n) ∈ ω(n), potom ∀ c > 0 : DT IME(t(n)) = DT IME(c · t(n))

Důkaz. Plyne přímo z věty 5.

Věta 6 (O lineárním zrychlení, část 2).

Necht’ L je jazyk přijímaný k-páskovým deterministickým Turingovým strojem M s časovou složitostí t(n) = c·n. Dále necht’ platí k ≥ 2 a c > 1. Potom pro ∀ε > 0 existuje k-páskový deterministický Turingův stroj M′ s časovou složitostí (1 + ε) · n přijímající L.

Důkaz. Budeme požadovat, aby

n + ⌈n/r⌉ + 6⌈cn/r⌉ ≤ (1 + ε) · n  (6)
n + n/r + 6cn/r + 7 ≤ (1 + ε) · n  (7)
(1 + 1/r + 6c/r + 7/n) · n ≤ (1 + ε) · n  (8)

Vztah (6) je požadovaná nerovnost, v (7) je na levé straně horní odhad levé strany (6), tedy stačí ukázat (7). Nerovnost (8) je prostá úprava (7).

Ukážeme, že lze volit r a n_{0} tak, že pro n > n_{0} platí (1/r + 6c/r + 7/n) < ε. Požadujeme:

1/r ≤ ε/3 dostáváme r ≥ 3/ε  (9)
6c/r ≤ ε/3 dostáváme r ≥ 18c/ε  (10)
7/n_{0} ≤ ε/3 dostáváme n_{0} ≥ 21/ε  (11)

Z (9) a (10) dostáváme r = max{3/ε, 18c/ε} = 18c/ε.

Z (11) dostáváme n_{0} = 21/ε.

Tvrzení věty je dokázáno.

Důsledek 3.

Pokud t(n) = cn, kde c > 1, potom ∀ ε > 0 : DT IME(t(n)) = DT IME((1 + ε)n)

Důkaz. Plyne přímo z věty 6.

Věta 7 (Nedeterministická verze).

Pokud t(n) ∈ ω(n), potom ∀c > 0 : NT IME(t(n)) = NT IME(c · t(n))

Pokud t(n) = cn, c > 1, potom ∀ε > 0 : NT IME(t(n)) = NT IME((1+ε)n)

Důkaz. Předchozí důkazy lze zobecnit (pomocí odhadu počtu dosažitelných konfigurací) i pro nedeterministický případ.

3.2.1 Redukce počtu pásek

Věta 8 (O redukci počtu pásek pro časovou složitost).

Necht’ L ∈ DT IME(T (n))^{1}. Potom existuje jednopáskový deterministický Turingův stroj M s časovou složitostí (T (n))^{2}, který přijímá L.

Důkaz. Použijeme kombinaci věty o zrychlení a věty o redukci počtu pásek pro prostorovou složitost.

Pokud je L přijímán jednopáskovým strojem, není co dokazovat.

Necht’ je tedy přijímán k-páskovým strojem, kde k > 1.

1) Necht’ T (n) ∈ ω(n). Dle věty o lineárním zrychlení existuje deterministický Turingův stroj M′ přijímající L v čase \frac{1}{\sqrt{2k}} ·T (n) = T′(n) v prostoru S′(n).

Nyní použijeme větu o redukci počtu pásek pro prostorovou složitost a z ní odvodíme stroj, který má jednu pásku a který přijímá L v čase T′′(n) ≤ 2k · S′(n) · T′(n) ≤ 2k · (T′(n))^{2} = (T (n))^{2} 2) Necht’ T (n) = cn, kde c > \sqrt{2k}. Dle věty o lineárním zrychlení zvolíme ε

1T (n) splňuje jisté ”mírné požadavky”: předpokládejme, že bud’ T (n) ∈ ω(n) nebo T (n) = cn, kde c > \sqrt{2k}

tak, aby platilo

1 + ε = \frac{c}{\sqrt{2k}} tedy (1 + ε)n = \frac{1}{\sqrt{2k}} T (n)  (12)

Zbytek stejně jako v bodě 1.

Důsledek 4.

Pokud L ∈ NT IME(T (n)), potom existuje jednopáskový nedeterministický Turingův stroj s časovou složitostí (T (n))^{2} přijímající L.

Důkaz. Plyne přímo z věty 8.

Věta 9 (O redukci počtu pásek pro časovou složitost, 2).

Necht’ je L přijímán k-páskovým deterministickým Turingovým strojem M s časovou složitostí T (n). Potom existuje 2-páskový deterministický Turingův stroj M′ s časovou složitostí T (n) log_{2} T (n) přijímající L.

Důkaz. První páska stroje bude mít 2k stop, teda každý znak abecedy Σ_{M′} bude kódovat 2k znaků původní abecedy (plus speciální prázdný symbol).

Druhá (pomocná) páska bude sloužit k přesunům dat na pásce první.

Obě pásky předpokládáme oboustranně nekonečné.

Hlavní myšlenka: Abychom se vyhnuli hledání displeje původního stroje, budeme udržovat displej na jediném políčku. Tedy místo pohybu hlav budeme pohybovat obsahem celé pásky. Přesuny dat budeme dělat tak, aby malé přesuny byly častější a velké (vzdálené) přesuny byly vzácné.

První páska stroje bude rozdělena do bloků …, B_{−2}, B_{−1}, B_{0}, B_{1}, B_{2}, . . .. Blok B_{0} se sestává z jediného políčka a bude obsahovat displej stroje M. Pro ostatní bloky platí: ∀i, |i| ≥ 1 : |B_{i}| = 2^{|i|−1}. Bloky jsou odděleny značkami, které jsou umist’ovány při prvním použití bloku.

Ukážeme simulaci práce M na první pásce (stroje M).

Na začátku výpočtu je obsah první pásky M na spodní stopě pásky M′. Po celou dobu simulace budou platit následující invarianty:

1) Pro každé i > 0 nastává právě jedna ze tří možností.

a) B_{i} má obě stopy plné a B_{−i} má obě stopy prázdné;

b) B_{−i} má obě stopy plné a B_{i} má obě stopy prázdné;

c) B_{i} i B_{−i} mají spodní stopu plnou a horní stopu prázdnou.

2) ∀i B_{i} obsahuje souvislý interval pásky stroje M. Pro i < 0 obsahuje horní stopa symboly vpravo od dolní stopy, pro i > 0 horní stopa obsahuje symboly vlevo od dolní stopy.

3) B_{0} obsahuje symbol pouze na dolní stopě, horní stopa obsahuje speciální značku, která slouží pro vyhledání tohoto bloku.

4) ∀i B_{i} obsahuje interval pásky stroje M bezprostředně nalevo od obsahu bloku B_{i+1}.

Simulace jednoho kroku M. Displej je v B_{0}. Krok se skládá ze změny dat na pásce (zřejmé) a simulace posunu hlavy. Ukážeme si případ posunu hlavy doleva, tedy data budeme posunovat doprava.

i) Hlava jede doprava, dokud nenajde blok B_{i} takový, že má alespoň jednu stopu volnou. (To znamená, že všechny bloky, které přejel, byly zcela plné!)

ii) Hlava jede zpátky a kopíruje obsah bloků B_{i−1}, B_{i−2}, …, B_{0} na pomocnou pásku. Bloky projede každý třikrát, nebot’ musí překopírovat obsah obou stop a to ve správném pořadí.

iii) Hlava jede doprava a kopíruje obsah pomocné pásky do spodní stopy bloků B_{1}, B_{2}, …, B_{i−1}. Horní stopy vyprázdní. V okamžiku, kdy hlava dojede na konec bloku B_{i−1}, zbyde na pracovní pásce přesně |B_{i}| nepřekopírovaných políček.

a) V případě, že byl B_{i} zcela prázdný, napíše je M′ do spodní stopy.

b) V případě, že byl B_{i} poloprázdný, napíše je M′ do horní stopy.

iv) Hlava jede vlevo a na pomocnou pásku si počítá vzdálenost bloku B_{i} od B_{0}.

v) Hlava jede vlevo a pomocí počítadla najde levý okraj B_{−i}.

vi) Hlava jede vpravo a na pomocnou pásku kopíruje obsah

a) horní stopy B_{−i}, v případě, že byl B_{−i} zcela plný (tj. B_{i} byl zcela prádzný)

b) dolní stopy B_{−i}, v případě, že byl B_{−i} poloplný (tj. B_{i} byl poloplný)

vii) Hlava jede vpravo a do spodní stopy bloků B_{−i+1}, B_{−i+2}, …, B_{0} kopíruje obsah pomocné pásky. Bloky B_{−i+1}, B_{−i+2}, …, B_{0} musely být prázdné, nebot’ B_{i} byl první blok napravo od B_{0}, který nebyl plný.

Kroky i - vii nazveme B_{i} operací. Pro B_{i} operaci platí, že zachovává platnost uvedených invarantů a trvá čas O(|B_{i}|).

Jaká je časová složitost celé simulace? Operace B_{i} může být provedena pouze jednou za 2^{i−1} kroků stroje M. Důvodem je fakt, že po jejím provedení jsou horní stopy bloků B_{1}, …, B_{i−1} prázdné a tedy je potřeba posunout pásku alespoň 2^{i−1}-krát, což vyžaduje nejméně takový počet kroků.

Pokud stroj M udělá T (n) kroků během výpočtu, může se B_{i} operace provést nejvýše ⌊T (n)/2^{i−1}⌋-krát.

Stačí uvažovat B_{i} operace pro i ≤ ⌈log_{2} T (n)⌉ ≤ log_{2} T (n) + 1.

Necht’ m je konstanta taková, že každá B_{i} operace trvá nejvýše m · 2^{i−1} kroků. Stroj M′ tedy udělá maximálně

T′(n) ≤ ∑_{i=1}^{log_{2} T (n)+1} m · 2^{i−1}⌊T (n)/2^{i−1}⌋ ≤

≤ ∑_{i=1}^{log_{2} T (n)+1} m · T (n) ≤ log_{2} T (n) · m · T (n)

(13)

Pro simulaci práce na všech k páskách je potřeba k · m · T (n) log_{2} T (n). Po použití věty o zrychlení dostáváme deterministický Turingův stroj M′′,

který přijímá L v čase T (n) log_{2} T (n).

4 Konstruovatelnost funkcí

Definice 9. Funkce f : N → N je rekurzivní, jestliže existuje deterministický Turingův stroj M, který pro vstup 1^{n} vydá výstup 1^{f(n)}.

Definice 10. Funkce f : N → N je vyčíslitelná v čase O(f), jestliže je rekurzivní a ∃c ≥ 1 takové, že příslušný deterministický Turingův stroj M udělá nejvýše c · f(n) kroků, než vydá výstup 1^{f(n)}.

Definice 11. Funkce f : N → N je vyčíslitelná v prostoru O(f), jestliže je rekurzivní a ∃c ≥ 1 takové, že příslušný deterministický Turingův stroj M použije nejvýše c · f(n) prostoru, než vydá výstup 1^{f(n)}.

Definice 12. Funkce f : N → N je časově konstruovatelná, pokud existuje deterministický Turingův stroj M takový, že pro každý vstup délky n zastaví právě po f(n) krocích.

Definice 13. Funkce f : N → N je prostorově konstruovatelná, pokud existuje deterministický Turingův stroj M takový, že pro každý vstup délky n zastaví s právě f(n) páskovými políčky neprázdnými a během výpočtu žádný jiný prostor na pracovních páskách nebyl použit.

Lemma 2.

Necht’ f_{1} + f_{2} a f_{2} jsou časově konstruovatelné funkce a necht’ ∃ε > 0 ∃n_{0} ∀n > n_{0} : f_{1}(n) ≥ εf_{2}(n) + (1 + ε)n. Potom je f_{1} časově konstruovatelná.

Důkaz. Metodou podobnou té z důkazu věty o lineárním zrychlení zrychlíme výpočet trvající f_{1}(n) + f_{2}(n) kroků tak, aby trval přesně f_{1}(n) kroků.

Mějme M_{1} deterministický Turingův stroj pracující v čase f_{1}(n) + f_{2}(n) a M_{2} deterministický Turingův stroj pracující v čase f_{2}(n) (z předpokladů).

Zkonstruujeme M_{r}, který pracuje v čase f_{1}(n) pro skoro všechny vstupy. Práce M_{r} je rozdělena do 4 fází.

1) V první fázi přepíše vstup na první pracovní pásku, na kterou jej zapíše r-krát zahuštěný. Zároveň přepíše (r − 6)-krát zahuštěný vstup také na 2. a 3. pracovní pásku. Na to potřebuje n kroků. Zároveň řídící jednotka počítá modulo (r − 6) a po skončení přepisu provede maximálně r − 5 kroků tak, aby celkový počet kroků první fáze byl dělitelný (r − 6). Tedy dostáváme

T_{1} = (r − 6) · ⌈\frac{n}{r − 6}⌉ .  (14)

2) V druhé fázi M_{r} souběžně simuluje stroj M_{1} na první pásce a M_{2} na druhé pásce. Šest kroků (jedna sekvence) stroje M_{r} odsimuluje r kroků M_{1} a (r − 6) kroků M_{2}.

Zvolíme r dostatečně velké, aby simulace stroje M_{2} skončila dříve, a to po ⌈f_{2}(n)/(r − 6)⌉ sekvencích stroje M_{r}.

Potřebujeme zajistit:

⌈\frac{f_{1}(n) + f_{2}(n)}{r}⌉ > ⌈\frac{f_{2}(n)}{r − 6}⌉  (15)

Přibližně:

(f_{1}(n) + f_{2}(n)) · (r − 6) > r · f_{2}(n)
f_{1}(n) · (r − 6) ≥ 6f_{2}(n)

r − 6 ≥ \frac{6f_{2}(n)}{f_{1}(n)}

f_{1}(n) ≥ \frac{6}{r − 6}f_{2}(n)

r ≥ \frac{6(f_{1}(n) + f_{2}(n))}{f_{1}(n)}

V okamžiku, kdy M_{2} skončí, zastaví stroj M′ simulaci. Pomocí řídící jednotky si počítal modulo (r − 6). V případě, že f_{2}(n) nebylo násobkem (r − 6), provede stroj M′ přesně (r − 6) ⌈f_{2}(n)/(r − 6)⌉ − f_{2}(n) prázdných kroků, čímž se trvání druhé fáze doplní na nejbližší větší násobek (r − 6). Z uvedeného dostáváme, že počet kroků stroje M′ potřebný pro druhou fázi je

\begin{matrix}T_{2} = 6 · ⌈\frac{f_{2}(n)}{r − 6}⌉ + (r − 6) ⌈\frac{f_{2}(n)}{r − 6}⌉ − f_{2}(n) & = \\ = r · ⌈\frac{f_{2}(n)}{r − 6}⌉ − f_{2}(n) \end{matrix}  (16)

Z předpokladů plyne, že T_{2} je pro skoro všechna n kladné. Je zřejmé, že během této fáze bylo odsimulováno r · ⌈f_{2}(n)/(r − 6)⌉ kroků stroje M_{1}, nebot’ během každé ze sekvencí bylo odsimulováno r kroků stroje M_{1} (kroky na doplnění na násobek (r − 6) jsou prázdné, M_{1} se v nich nesimuluje).

3) V třetí fázi pokračuje M′ simulací M_{1} stejným tempem jako předtím (tedy 6 kroků za sekvenci odsimuluje r kroků půvopdního stroje). Tato fáze bude trvat ⌈n/(r − 6)⌉ + 1 sekvencí, což zajistíme tak, že po každé sekvenci přečteme jeden symbol z přepsaného komprimovaného vstupu (viz fáze 1). Čas pro tuto fázi je

T_{3} = 6 · (⌈\frac{n}{r − 6}⌉ + 1) (17)

a je odsimulováno r · (⌈n/(r − 6)⌉ + 1) kroků stroje M_{1}. Při srovnání času výpočtu stroje M_{1} s dosud odsimulovaným počtem je zřejmé, že pro dostatečně velké hodnoty r tato simulace pro skoro všechna n nedosáhne celého výpočtu M_{1}.

4) Ve čtvrté fázi pokračuje M′ real-time simulací stroje M_{1} (jeden krok M′ odpovídá jednomu kromu M_{1}), dokud se M_{1} nezastaví. Na závěr provede M′ r − 6 prázdných kroků a zastaví se. Čas na tuto fázi je zbývající čas stroje M_{1} plus r − 6, z toho dostáváme:

T_{4} = f_{1}(n) + f_{2}(n) − r · ⌈\frac{f_{2}(n)}{r − 6}⌉ − r · (⌈\frac{n}{r − 6}⌉ + 1) + r − 6 (18)

Hodnota r musí být dost velká, aby tento výraz byl pro skoro všechna n kladný. Existence takového r plyne z předpokladů tvrzení.

Součtem T_{1}, T_{2}, T_{3}, T_{4} dostáváme, že čas pro běh stroje M′ je přesně f_{1}(n) pro skoro všechna n.

Věta 10 (O ekvivalenci definic 10 a 12).

Necht’ f : N → N je funkce taková, že ∃ε>0 ∃n_{0} ∀n≥n_{0} : f(n) ≥ (1 + ε)n. Potom f je časově konstruovatelná právě, když f je vyčíslitelná v čase O(f).

Důkaz. Implikace zleva doprava je zřemá. Stroj dokazující časovou konstruovatelnost modifikujeme tak, že na novou pásku v každém kroku napíše jeden symbol. Nový stroj vyčísluje f v čase O(f).

Nyní opačná implikace. Necht’ M je deterministický Turingův stroj, který vyčísluje f v čase O(f). Označme g(n) počet kroků stroje M nad vstupem 1^{n} (zřejmě ∃c>0 : g(n) ≤ cf(n)).

1) g je časově konstruovatelná (díky existenci stroje M).

2) g + f je časově konstruovatelná. Modifikuji M tak, aby počítal výstup na zvláštní pásku a po skončení výpočtu přejel na začátek této pásky. Doba výpočtu je g(n), délka výstupu je f(n).

3) ∃ε>0 ∃n_{0} ∀n>n_{0} : f(n) ≥ εg(n) + (1 + ε)n Zvolíme:

a) ε_{1}, jehož existenci nám zajišt’ují předpoklady věty: ∃n_{0} ∀n≥n_{0} : f(n) ≥ (1 + ε_{1})n

b) ε_{2} zvolíme tak, aby (1 + ε_{1})(1 − ε_{2}) > 1

c) ε_{3} = (1 + ε_{1})(1 − ε_{2}) − 1

d) ε_{4} = min {ε_{2}/c, ε_{3}}

Potom

\begin{matrix}f(n) = ε_{2}·f(n) + (1 − ε_{2})f(n) ≥ ε_{2}/c·g(n) + (1 + ε_{1})(1 − ε_{2})n & = \\ = (ε_{2}/c)·g(n) + (1 + ε_{3})n ≥ ε_{4}·g(n) + (1 + ε_{4})n & . \end{matrix} (19)

Funkce f a g splňují předpoklady lemmatu 2 a tedy f(n) je časově konstruovatelná.

Věta 11 (O ekvivalenci definic 11 a 13).

Funkce f : N → N je prostorově kontruovatelná právě, když f je vyčíslitelná v prostoru O(f).

Důkaz. Implikace zleva doprava je zřemá. Stroj dokazující prostorovou konstruovatelnost modifikujeme tak, že na novou výstupní pásku v každém kroku, ve kterém bylo zabráno nové políčko na pracovní pásce, napíše jeden symbol. Stroj musí rozlišovat původní a nový symbol pro prázdné políčko. Nový stroj vyčísluje f v protoru O(f).

Necht’ M je k-páskový deterministický Turingův stroj vyčíslující f(n) v prostoru c·f(n). Podle věty o lineární kompresi zkonstruujeme k-páskový stroj M′, který vyčísluje f(n) v prostoru přesně f(n). Uvědomte si, že M′ vyčísluje f(n), tedy musí pracovat v prostoru alespoň f(n). Stroj M′ dále převedeme podle věty o redukci počtu pásek na jednopáskový stroj M′′, který již dokazuje prostorovou konstruovatelnost funkce f.

Důsledek 5.

Každá časově konstruovatelná funkce je prostorově konstruovatelná.

Důkaz. Funkce f je časově konstruovatelná, tedy f je vyčíslitelná v čase O(f), tím spíše je f vyčíslitelná v protoru O(f) a tedy dostáváme dle předchozí věty, že f je prostorově konstruovatelná.

Věta 12 (O rychlosti růstu časově konstruovatelných funkcí).

Necht’ f: N→N je rekurzivní funkce. Potom existuje časově konstruovatelná funkce g: N→N taková, že ∀n g(n) > f(n).

Důkaz. Víme, že f je rekurzivní, tedy existuje deterministický Turingův stroj M, který pro vstup 1^{n} vydá výstup 1^{f(n)}.

Definujeme g(n) jako počet kroků stroje M nad vstupem 1^{n} zvětšený o jedna. Je zřejmé, že f(n) < g(n) a g(n) je časově konstruovatelná (samotný M tuto vlastnost přímo dokazuje).

5 Hierarchie tříd složitosti

5.1 Časová hierarchie

Definice 14. Jazyk L je rekurzivní, jestliže existuje deterministický Turingův stroj M, který se pro každý vstup x zastaví a který přijme právě, když x ∈ L.

Věta 13 (O otevřenosti časové hierarchie shora).

Necht’ T : N → N je rekurzivní funkce. Potom existuje rekurzivní jazyk L takový, že L ∉ DT IME(T (n)).

Důkaz. Ukážeme konstrukci takového jazyka. Nejprve očíslujeme všechny deterministické Turingovy stroje Gödelovými čísly a také očíslujeme všechny řetězce nad {0, 1}. Očíslování provedeme systematicky, aby bylo možno tyto řetězce generovat.

Definujeme L = {x_{i} : M_{i} nepřijímá x_{i} v čase T (|x_{i}|)}.

Ukažme nejprve, že L je rekurzivní.

1) Pro vstup w ∈ {0, 1}^{∗} délky n generujeme na pomocnou pásku počítadlo T (n) (lze, nebot’ T se vždy zastaví).

2) Postupným generováním najdeme i takové, že w = x_{i}. To lze v konečném počtu kroků.

3) Uvažuji i jako Gödelovo číslo nějakého stroje.

4) Provedu simulaci stroje M_{i} nad x_{i} po T (n) kroků. Slovo x_{i} přijmu v následujících případech:

a) M_{i} zastaví po méně než T (|x_{i}|) + 1 krocích a odmítne;

b) M_{i} běží více jak T (|x_{i}|) + 1 kroků.

Nyní ukažme, že L ∉ DT IME(T (n)). Pro spor předpokládejme, že uvedené platí, tedy L ∈ DT IME(T (n)). Potom existuje deterministický Turinův stroj M, který rozpozná L v čase T (n). Necht’ i je jeho Gödelovo číslo (M_{i} = M).

1) x_{i} ∈ L, potom M_{i} přijímá x_{i} v čase T (|x_{i}|), z čehož plyne, že x_{i} není přijmuto strojem M, ale M = M_{i}. Spor.

2) x_{i} ∉ L, potom M_{i} nepřijímá x_{i} v čase T (|x_{i}|), z čehož plyne, že x_{i} je přijmuto strojem M, ale M = M_{i}. Spor.

Tím je věta dokázána.

Důsledek 6 (Nekonečná časová hierarchie).

Existuje nekonečná posloupnost funkcí T_{1}, T_{2}, … taková, že DT IME(T_{1}(n)) ⊊ DT IME(T_{2}(n)) ⊊ . . ..

Důkaz. Necht’ je hiearchie vybudována až po DT IME(T_{i}(n)).

Z předchozí věty víme, že existuje rekurzivní jazyk L takový, že pro něj platí L ∉ DT IME(T_{i}(n)). Definujeme funkci T_{i+1} takovou, aby majorizovala funkci T_{i} a zároveň i dobu výpočtu stroje, který přijímá jazyk L (necht’ je tento výpočet omezen funkcí T′).

Tím budeme mít zaručeno, že DT IME(T_{i}(n)) ⊆ DT IME(T_{i+1}(n)) a také L ∈ DT IME(T_{i+1}(n)). Z faktu, že L ∉ DT IME(T_{i}(n)) dostáváme ostrou inkluzi.

K tomu stačí ale položit T_{i+1} = max{T_{i}(n), T′(n)}.

5.2 Prostorová hierarchie

Věta 14 (O otevřenosti prostorové hierarchie shora).

Necht’ S : N → N je rekurzivní funkce. Potom existuje rekurzivní jazyk L takový, že L ∉ DSP ACE(S(n)).

Důkaz. Důkaz je analogický důkazu časové verze této věty.

Definujeme L = {x_{i} : M_{i} nepřijímá x_{i} v prostoru S(|x_{i}|)}.

Rozdíl oproti časové verzi je v tom, že stroj M_{i} nyní může odmítnout konečným výpočtem ve vymezeném prostoru, překročením vymezeného prostoru nebo vstupem do nekonečné smyčky uvnitř vymezeného prostoru. To lze ale ošetřit odhadem počtu konfigurací (na omezeném prostoru existuje konečně mnoho konfigurací) a přidáním budíku, který stroj zastaví v okamžiku, kdy počet kroků bude vyšší než počet konfigurací.

Důsledek 7 (Nekonečná prostorová hierarchie).

Existuje nekonečná posloupnost funkcí S_{1}, S_{2}, … taková, že DSP ACE(S_{1}(n)) ⊊ DSP ACE(S_{2}(n)) ⊊ . . ..

Důkaz. Analogicky jako v případě časové hierarchie.

5.3 Věty o hierarchii

Věta 15 (O prostorové hierarchii).

Necht’ S_{1} : N → N a S_{2} : N → N jsou funkce takové, že S_{2} ∈ ω(S_{1}) a S_{2} je prostorově konstruovatelná.

Potom existuje jazyk L takový, že L ∈ DSP ACE(S_{2}(n))\DSP ACE(S_{1}(n)).

Důkaz. Naším cílem bude zkonstruovat deterministický Turingův stroj pracující v prostoru S_{2}(n), který se od každého stroje pracujícího v prostoru S_{1}(n) liší alespoň na jednom vstupu.

Prefixově si očíslujeme všechny jednopáskové stroje nad abecedou {0, 1}. Popíšeme práci M na vstupu w, |w| = n. V první fázi si M označí S_{2}(n)

buněk na pracovní pásce. Dojde-li v dalších fázích k opuštění vymezeného prostoru, stroj se zastaví a odmítne.

V druhé fázi M simuluje M_{w} a přijme, pokud M_{w} odmítne w a neopustí přitom vymezený prostor.

Platí L ∈ DSP ACE(S_{2}(n)) a L ∉ DSP ACE(S_{1}(n)). První vztah je zřejmý, ukážeme druhý (sporem).

Necht’ pro spor L ∈ DSP ACE(S_{1}(n)), potom existuje deterministický Turingův stroj M′ takový, že L(M′) = L(M). M′ má velikost pracovní abecedy t a pracuje v prostoru S_{1}(n). Bez újmy na obecnosti můžeme předpokládat, že M′ se vždy zastaví a je jednopáskový.

Kdyby M′ neměl požadované vlastnosti, lze jej modifiovat tak, že bude schopen rozpoznat nekonečný cyklus (pomocí horního odhadu na počet konfigurací). Počet možných konfigurací je s · (n + 1) · S_{1}(n) · t^{S_{1}(n)}, kde s je počet stavů a t je počet páskových symbolů. Tento počet lze odhadnout jako c^{S_{1}(n)} pro vhodnou konstantu c. Uložíme-li si toto číslo v základu c, vejde se do prostoru S_{1}(n). Tedy stroj si bude na nové pásce počítat kroky a přesáhne-li počet kroků počet možných konfigurací, odmítne. Podle věty o redukci počtu pásek dotáváme jednopáskový stroj s požadovanými vlastnostmi.

K simulaci M′ potřebujeme ⌈log_{2} t⌉ · S_{1}(n) prostoru. Vzhledem k volbě prefixového číslování strojů můžeme zvolit w tak, že kóduje stejný stroj, ale současně platí ⌈log_{2} t⌉ · S_{1}(|w|) ≤ S_{2}(|w|). To jistě lze, nebot’ S_{2} roste rychleji než S_{1}.

Pakliže stroj M′ přijímá w, potom L ∈ L(M′) = L(M), ale dle definice stroje M platí w ∉ L(M). Jestliže naopak M′ odmítne w, potom w ∉ L(M′) = L(M), ale M′ odmítne w ve vymezeném prostoru, tedy podle definice M platí w ∈ L(M). V obou případech dostáváme spor. Tedy L ∉ DSP ACE(S_{1}(n)).

Věta 16 (O časové hierarchii).

Necht’ T_{1} : N → N a T_{2} : N → N jsou funkce takové, že T_{2} ∈ ω(T_{1} · log T_{1}) a T_{2} je časově konstruovatelná.

Potom existuje jazyk L takový, že L ∈ DT IME(T_{2}(n)) \ DT IME(T_{1}(n)).

Důkaz. Naším cílem bude zkonstruovat deterministický Turingův stroj pracující v čase T_{2}(n), který se od každého stroje pracujícího v čase T_{1}(n) liší alespoň na jednom vstupu.

Prefixově si očíslujeme všechny dvoupáskové stroje.

Práce M na vstupu w, kde |w| = n.

1) Na dvou páskách simuluje práci stroje M_{w}.

2) Na dalších páskách stopuje T_{2}(n) kroků. To jistě lze, nebot’ T_{2} je časově konstruovatelná.

3) M přijme, pokud simulace skončí nejvýše v T_{2}(n) krocích odmítnutím w.

Označme L = L(M). Ukážeme, že L ∈ DT IME(T_{2}(n)) \ DT IME(T_{1}(n)).

Použitím čítače kroků máme zajištěno, že L ∈ DT IME(T_{2}(n)). Ukažme tedy, že L ∉ DT IME(T_{1}(n)).

Důkaz budeme dělat sporem. Předpokládejme, že existuje stroj M′ takový, že M′ přijímá L v čase T_{1}(n). Potom existuje podle věty o redukci počtu pásek stroj M′′, který má dvě pásky a přijímá L v čase T_{1}(n)·log_{2} T_{1}(n)

Necht’ pásková abeceda stroje M′′ má t symbolů. M bude na simulaci M′′ potřebovat c(t)·T_{1}(n)·log_{2} T_{1}(n), kde c(t) je konstanta závislá na t.

Necht’ v je Gödelovo číslo stroje M′′. Zvolíme w = αv, kde α je prefix takové délky, aby platilo c(t)·T_{1}(|w|)·log T_{1}(|w|)) ≤ T_{2}(|w|). Taková délka prefixu existuje z předpokladů věty.

Nyní má M dostatek času k simulaci M′′ (trik byl v tom, že jsme právě zvětšili vstup stroje, přestože stroj bude počítat totéž, pouze na to bude mít více času).

Rozlišme dva případy:

1) M_{w}(= M′′) přijímá w, potom

a) w ∈ L, protože L = L(M) = L(M′′),

b) w ∉ L, protože M odmítne w, když jej M_{w} přijme.

2) M_{w} odmítá w, potom

a) w ∉ L, protože L = L(M) = L(M′′),

b) w ∈ L, protože M přijme w, když jej M_{w} odmítne.

Spor s předpokladem, že L ∈ DT IME(T_{1}(n)). Věta je dokázána.

5.4 Věta o vtazích mezi třídami složitosti

Věta 17 (O vztazích mezi třídami složitosti).

a) DT IME(f(n)) ⊆ NT IME(f(n))

DSP ACE(f(n)) ⊆ NSP ACE(f(n))

b) DT IME(f(n)) ⊆ DSP ACE(f(n))

c) L ∈ DSP ACE(f(n)) a f(n) ≥ log_{2} n, potom ∃c_{L} : L ∈ DT IME(c_{L}^{f(n)}), kde c_{L} je konstanta závislá na L

d) L ∈ NT IME(f(n)), potom ∃c_{L} : L ∈ DT IME(c_{L}^{f(n)}), kde c_{L} je konstanta závislá na L

Důkaz.

a) Triviálně platí.

b) Z vět o lineární kompresi a o redukci počtu pásek.

c) Necht’ M je jednopáskový stroj dokazující L ∈ DSP ACE(f(n)). Počet jeho konfigurací je omezen s · (n + 1) · (f(n) + 1) · t^{f(n)} ≤ d^{f(n)}, pro vhodné d (s je počet stavů, t je počet páskových symbolů).

Zkonstruujeme M′, který simuluje stroj M a nejvýše po d^{f(n)} krocích se zastaví. (Potřebujeme předpoklad časové konstruovatelnosti funkce f). d) Necht’ M je nedeterministický k-páskový stroj, který dokazuje, že L ∈

NT IME(f(n)). Počet jeho konfigurací je omezen s · (f(n) + 1)^{k} · t^{k·f(n)} ≤ d^{f(n)}, pro vhodné d (s je počet stavů, t je počet páskových symbolů). Zkonstruujeme deterministický M′ takový, že vygeneruje seznam všech konfigurací dosažitelných z počáteční konfigurace (například průchodem stromu výpočtu M). Generování seznamu lze provést v čase kvadratickém vzhledem k délce výsledného seznamu. Tato délka je omezena součinem počtu konfigurací a délky zápisu jedné konfigurace. Tedy l ≤ d^{f(n)} ·(k·f(n)+1+k·log f(n)) ≤ c^{f(n)}. Tedy počet kroků je omezen c^{2·f(n)}.

Věta 18 (Rozšíření věty o vztazích).

b’) NT IME(f(n)) ⊆ NSP ACE(f(n))

c’) L ∈ NSP ACE(f(n)) a f(n) ≥ log_{2} n, potom ∃c_{L} : L ∈ DT IME(c_{L}^{f(n)}), kde c_{L} je konstanta závislá na L

Důkaz.

b’) Na pomocné pásce kódujeme aktuální průchod stromem výpočtu. Jednotlivé kódy můžeme systematicky generovat, (1, 1, …, 1) až (r, r, …, r), kde r je maximální stupeň větvení. Vlastní simulaci jedné větve výpočtu lze provést v prostoru f(n), na uložení informací o průchodu potřebujeme log r · f(n). Simulaci tedy lze provést v prostoru log r · f(n).

c’) Počet možných konfigurací na omezeném prostoru je d^{f(n)}, kde d je konstanta. Uvažujme graf G všech konfigurací. Hrana (a, b) znamená, že konfigurace b je z konfigurace a dosažitelná v jednom kroku.

\begin{aligned}|V (G)| & ≤ d^{f(n)} \\ |E(G)| & ≤ c · d^{f(n)} \end{aligned}  (20)

Omezení počtu hran plyne z faktu, že změny v konfiguraci po jednom kroku jsou pouze lokální, tedy každá konfigurace má pouze konstatní počet sousedů. Na pracovní pásku vygenerujeme seznam všech konfigurací, to zabere čas d^{f(n)} · q · f(n), kde q je konstanta. Deterministický stroj potom pracuje tak, že prochází graf G do hloubky a na pomocné pásce si zaznamenává, které vrcholy již navštívil. Na zjištění, který z vrcholů byl již navštíven, potřebuje čas úměrný délce dosavadního výpočtu. Stroj tedy pracuje v čase počet vrcholů · zkopírování příslušné konfigurace na pracovní pásku.

\begin{aligned}T (n) = |V (G)|qf(n) + |E(G)d^{f(n)}qf(n)| & = \\ = qf(n)(d^{f(n)} + kd^{f(n)}d^{f(n)}) & ≤ h(d^{2})^{f(n)} ≤ c_{L}^{f(n)} \end{aligned} (21)

Najde-li stroj při průchodu grafem přijímající konfiguraci, je tato dosažitelná z iniciální konfigurace a stroj přijme.

5.5 Savičova věta

Věta 19 (Savičova).

Necht’ S : N → N je prostorově konstruovatelná funkce, pro kterou platí S(n) ≥ log_{2} n. Potom NSP ACE(S(n)) ⊆ DSP ACE(S^{2}(n)).

Důkaz. Necht’ M_{1} je nedeterministický Turingův stroj přijímající jazyk L v prostoru S(n), potom existuje konstanta c_{L} taková, že M_{1} má nejvýše c_{L}^{S(n)} konfigurací.

Pokud M_{1} přijímá w, pak existuje posloupnost nejvýše c_{L}^{S(n)} = 2^{S(n)·log c_{L}} kroků končící přijetím w.

Označme I_{1} →_{i} I_{2}, pokud lze z konfigurace I_{1} přejít do I_{2} za méně než nebo přesně 2^{i} kroků. Test stačí provádět pro i ≤ S(n) · log c_{L} = m · S(n).

Popišme způsob rozhodování, že I_{1} →_{i} I_{2}.

procedure TEST(I_{1}, I_{2}, i)

if i = 0 then if (I_{1} = I_{2}) or (I_{1} → I_{2}) then return true else return false else for ∀ konfigurace I′ ∈ K do if TEST(I_{1}, I′, i − 1) and TEST(I′, I_{2}, i − 1) then return true enddo

return false end TEST

Kolik místa bude potřeba na jednu kopii procedury TEST? Procedura si musí pamatovat 3 konfigurace a parametr i. Jedna konfigurace obsahuje

• stav - konstantní prostor (log s, kde s je počet stavů)

• pozice vstupní hlavy - log_{2} n ≤ S(n)

• pozice pracovní hlavy - log_{2} n ≤ S(n)

• obsah pracovní pásky - c′ · S(n), kde c′ = log_{2} t, t je počet páskových symbolů.

Celkem je tedy potřeba na zapsání jedné konfigurace O(S(n)) prostoru. Parametr i lze zapsat v prostoru m · log S(n). Tedy prostor potřebný pro jednu kopii procedury TEST je O(S(n)).

Celá simulace potom probíhá tak, že pro všechny přijímající stavy I_{j} voláme proceduru T EST (I_{0}, I_{j}, m·S(n)) a jakmile alespoň jednou odpoví kladně, vstup přijmeme.

Při simulaci funguje pracovní páska jako zásobník na uložení parametrů procedur TEST. V každý okamžik je na zásobníku O(S(n)) záznamů. Deterministrický stroj simulující M_{1} pracuje v prostoru O(S^{2}(n)) a přijímá jazyk L.

6 Pokročilé věty o třídách složitosti

Lemma 3 (Translační).

Necht’ S_{1} : N→N, S_{2} : N→N, f: N→N jsou prostorově konstruovatelné a ∀n S_{2}(n) ≥ n, f(n) ≥ n. Potom

NSP ACE(S_{1}(n)) ⊆ NSP ACE(S_{2}(n)) ⇒
NSP ACE(S_{1}(f(n))) ⊆ NSP ACE(S_{2}(f(n))).

Důkaz. Necht’ L_{1} ∈ NSP ACE(S_{1}(f(n))) a necht’ M_{1} je stroj, který to ukazuje. Sestrojíme jazyk L_{2}, který bude patřit do NSP ACE(S_{1}(n)). Necht’ L_{2} = {x$^{i}|M_{1} přijímá x v prostoru S_{1}(|x| + i)}. Zřejmě pro všechna

i taková, že |x|+i ≥ f(|x|), platí x ∈ L_{1} ⇔ x$^{i} ∈ L_{2}. Tento argument se nazývá padding argument. Jde o to zvětšit délku slova bez přidání nové informace, čímž se stroji, který nad slovem pracuje, poskytne více prostoru (případně času).

Zkonstruujeme M_{2} přijímající L_{2} v prostoru S_{1}(n).

Vstup: x$^{i}

Algoritmus: Stroj M_{2} nejprve označí S_{1}(|x| + i) políček na pracovní pásce. Dále pokračuje M_{2} simulací stroje M_{1} a přijme právě tehdy, pokud přijme M_{1} a neopustí přitom vyznačený prostor. M_{2} zřejmě pracuje v prostoru S_{1}(n), tedy L ∈ NSP ACE(S_{1}(n)). Navíc platí x ∈ L_{1} ⇔ ∃i < f(|x|) : x$^{i} ∈ L_{2}. Jinými slovy, existuje i takové, že stroj M_{1} bude mít dost prostoru pro přijetí v prostoru S_{1}(|x| + i).

Protože podle předpokladu platí NSP ACE(S_{1}(n)) ⊆ NSP ACE(S_{2}(n)), dostáváme, že existuje nedeterministický Turingův stroj M_{3}, který přijímá L_{2} v prostoru S_{2}(n).

Nyní sestrojíme M_{4}, který přijímá L_{1} v prostoru S_{2}(f(n)).

Popis práce M_{4} nad vstupem x.

• Na půlené pracovní pásce si označí na horní stopě f(|x|) políček a potom si na dolní stopě označí S_{2}(f(|x|)) políček, přičemž používá horní stopu jako vstup. To lze, nebot’ f i S_{2} jsou prostorově konstruovatelné. Protože S_{2}(|x|) ≥ |x|, M_{4} zabere přesně S_{2}(f(|x|)).

• M_{4} simuluje M_{3} na vstupu x$^{i} (pro dostatečně velké i) s tím, že pokud je vstupní hlava M_{3} nad x, je hlava M_{4} na odpovídající pozici, je-li vstupní hlava M_{3} nad $^{i}, tak vstupní hlava M_{4} zůstává na konci slova x a pozice hlavy je počítána na zvláštní pracovní pásce M_{4}.

• Počítadlo nepustí vstupní hlavu M_{3} za pozici, kdy už by čítač přetekl z prostoru S_{2}(f(|x|)), tedy i ≤ 2^{S_{2}(f(|x|))}, nebot’ v prostoru S_{2}(f(|x|)) může počítadlo binárně počítat až do 2^{S_{2}(f(|x|))}.

• M_{4} přijme x právě, když M_{3} přijme.

Platí: x ∈ L_{1} ⇔ ∃i < f(|x|) : x$^{i} ∈ L_{2} = L(M_{3}). Víme ale, že S_{2}(n) ≥ n, tedy S_{2}(f(|x|)) ≥ f(|x|), z čehož dostáváme 2^{S_{2}(f(|x|))} ≥ f(|x|). Již dříve jsme ukázali, že stačí i ≤ f(|x|), tedy naše simulace umožňuje zkoušet dostatečně velká i.

Tedy i je dostatečně velké.

Na závěr dostáváme x ∈ L(M_{4}) ⇔ x$^{i} ∈ L(M_{3}) ⇔ x ∈ L_{1} a tedy L_{1} ∈ NSP ACE(S_{2}(f(n))).

Věta 20 (O nedeterministické prostorové hierarchii).

Necht’ ε > 0 a r ≥ 1, potom NSP ACE(n^{r}) ⊊ NSP ACE(n^{r+ε}).

Důkaz. Díky hustotě racionálních čísel víme, že

∀r ∀ε ∃s, t ∈ N : r ≤ \frac{s}{t} < \frac{s + 1}{t} ≤ r + ε. (22)

Ukážeme, že NSP ACE(n^{s/t}) ⊊ NSP ACE(n^{(s+1)/t}). Důkaz provedeme sporem. Necht’ tedy NSP ACE(n^{(s+1)/t}) ⊆ NSP ACE(n^{s/t}). Použijeme (s+1)- krát translační lemma, postupně pro funkce f(n) = n^{(s+i)t} pro i = 0, …, s.

i = 0  NSP ACE(n^{(s+1)s}) ⊆ NSP ACE(n^{s^{2}})  (23)
i = 1  NSP ACE(n^{(s+1)(s+1)}) ⊆ NSP ACE(n^{s(s+1)})
i = 2  NSP ACE(n^{(s+1)(s+2)}) ⊆ NSP ACE(n^{s(s+2)})
⋮
i = s − 1  NSP ACE(n^{(s+1)(2s−1)}) ⊆ NSP ACE(n^{s(2s−1)})
i = s  NSP ACE(n^{(s+1)(2s)}) ⊆ NSP ACE(n^{s(2s)})

Pravá strana každé inkluze je vnořená do levé strany inkluze pro i o jedničku menší. Dostaneme prostým porovnáním exponentů u n.

Zřetězením dostaneme

NSP ACE(n^{(s+1)(2s)}) ⊆ NSP ACE(n^{s^{2}}) ⊆ DSP ACE(n^{2s^{2}}) ⊊  (24)
⊊ DSP ACE(n^{2s^{2}+2s}) ⊆ NSP ACE(n^{(s+1)(2s)}).  (25)

Uvedené schéma vede ke sporu, nebot’ vpravo i vlevo je stejná třída a uprostřed je ostrá inkluze.

Definice 15.

Tvrzení parametrizované číslem n je pravdivé skoro všude, platí-li na všech kromě konečně mnoha n.

Tvrzení parametrizované číslem n je pravdivé nekonečně často, platí-li na nekonečně mnoha n.

Lemma 4.

Necht’ L je jazyk přijímaný deterministickým Turingovým strojem s prostorovou složitostí S(n) skoro všude. Potom L je přijímaný jiným strojem M′ s prostorovou složitostí S(n).

Důkaz. Konečně mnoho výjimek, kde výpočet přesáhne S(n) ošetříme pomocí tabulky. Takový stroj ale nelze efektivně sestrojit, protože nedokážeme vyjímky identifikovat.

Lemma 5.

Necht’ je dán deterministický Turingův stroj M, délka vstupu n a číslo m. Existuje algoritmus zjišt’ující, zda m je maximální počet použitých buněk na pracovních páskách při práci M na vstupech délky n. Algoritmus vždy skončí.

Důkaz. Stačí simulovat výpočet M a počítat kroky pro detekci případných nekonečných smyček (překročení počtu možných konfigurací).

6.1 Věta o mezerách (Borodin)

Věta 21 (Borodinova, o mezerách).

Necht’ g(n) ≥ n je rekurzivní funkce. Potom existuje rekurzivní funkce S(n) taková, že DSP ACE(S(n)) = DSP ACE(g(S(n)))

Důkaz. Necht’ M_{1}, M_{2}, … je očíslování všech deterministických strojů. Označme S_{i}(n) = maximum použitých buněk stroje M_{i} na vstupu délky n.

Pokud se M_{i} vždy zastaví, je S_{i}(n) jeho prostorová složitost. Pokud se M_{i} na nějakém vstupu délky n nezastaví, je S_{i}(n) nedefinováno (respektive rovno +∞).

Poznámka: zjistit, zda S_{i}(n) = +∞ nelze, ale pro libovolné pevně dané m lze zjistit, zda S_{i}(n) ≤ m (viz lemma 5).

Zkonstruujeme funkci S(n) takovou, že pro všechna k bud’

S_{k}(n) ≤ S(n) skoro všude (26)

nebo

S_{k}(n) > g(S(n)) nekonečně často. (27)

Uvedené nerovnosti požadujeme, abychom zajistili:

∀k : L(M_{k}) ∈ DSP ACE(S(n)) ⇔ L(M_{k}) ∈ DSP ACE(g(S(n))) (28)

Stroj M_{k} splňující 26 lze pomocí konečně mnoha výjimek změnit tak, aby nerovnost platila všude podle lemma 4, a stroj splňující 27 naopak nelze pomocí konečně mnoha výjimek změnit tak, aby platila opačná nerovnost.

Z 26 a 27 plyne, že neexistuje k takové, že S(n) < S_{k}(n) ≤ g(S(n)) skoro všude. Stroj M_{k} by potom přijímal jazyk, který není v DSP ACE(S(n)), ale je v DSP ACE(g(S(n))). Tomu se chceme v konstrukci vyhnout.

Popíšeme nyní konstrukci S(n) pro danou hodnotu n. Vezmeme M_{1}, …, M_{n} a zvolíme S(n) tak, že ∀i, 1 ≤ i ≤ n : S_{i}(n) ≤ S(n) nebo g(S(n)) < S_{i}(n).

V případě, že jsou všechna S_{i}(n) konečná, stačí vzít za S(n) maximum, jak bylo ale již výše uvedeno, nelze o konečnosti S_{i}(n) rozhodnout. Proto budeme problém řešit ”z druhého konce”.

Necht’ j = 1 a spočítejme g(j) (to lze, nebot’ g je rekurzivní). Zjistíme, zda existuje stroj M_{i} takový, že j < S_{i}(n) ≤ g(j) (to nám umožňuje lemma 5, nebot’ nyní máme horní odhad na S_{i}(n)).

Jestliže takové M_{i} neexistuje, můžeme položit S(n) = j, nebot’ žádný stroj M_{i} nepočítá s protorovou složitostí mezi S(n) a g(S(n)).

Jestliže takové M_{i} naopak existuje, volíme j = S_{i}(n). Pokračujeme spočítáním g(j). Cyklus se zastaví nejvýše po n interacích, nebot’ v každé se jedno S_{i} stane dolní hranicí intervalu.

Takto konstruovaná funkce S(n) splňuje podmínky 26 nebo 27, nebot’ pro dané k byl stroj M_{k} uvažován pro všechna n ≥ k v množině M_{1}, …, M_{n} při konstrukci S(n). Tedy S_{k}(n) nebylo v intervalu (S(n), g(S(n))]. Proto muselo být bud’ nekonečně mnohokrát nad tímto intervalem nebo skoro vždy pod.

Necht’ L ∈ DSP ACE(g(S(n))), potom existuje deterministický Turingův stroj M_{k} rozpoznávající L v prostoru g(S(n)), tedy ∀n S_{k}(n) ≤ g(S(n)). Z konstrukce S(n) plyne, že pro n > k platí S_{k}(n) ≤ S(n) skoro všude. Tedy M_{k} pracuje v prostoru S(n) skoro všude a podle lemma 4 existuje jiný stroj, který přijímá L v prostoru S(n) všude, tedy L ∈ DSP ACE(S(n)).

Máme DSP ACE(g(S(n))) ⊆ DSP ACE(S(n)). Inkluze na druhou stranu je triviální, tedy dostáváme rovnost a tvrzení věty je dokázáno.

6.2 Věta o zrychlení

Věta 22 (Bloomova, o zrychlení - prostorová verze).

Necht’ r(n) je rekurzivní funkce. Potom existuje rekurzivní jazyk L takový, že pro každý deterministický Turingův stroj M_{i} rozpoznávající L v prostoru S_{i}(n) existuje deterministický Turingův stroj M_{j} rozpoznávající L v prostoru S_{j}(n), kde r(S_{j}(n)) ≤ S_{i}(n) skoro všude.

Než přistoupíme k samotnému důkazu věty, uvedeme si dvě pomocná tvrzení.

Lemma 6.

Bez újmy na obecnosti můžeme předpokládat, že funkce r je neklesající a prostorově konstruovatelná. Navíc platí r(n) ≥ n^{2}.

Důkaz. Pokud r(n) nesplňuje uvedené požadavky, definujeme

r′(n) = max{počet buněk použitých k výpočtu r(1), …, r(n), n^{2}} (29)

Je zřejmé, že r′(n) je neklesající a prostorově konstruovatelná. Také zřejmě platí r′(n) ≥ r(n) a tedy stačí dokázat větu pro r′(n).

Lemma 7.

Definujeme-li h(n) = r(h(n − 1)), h(1) = 2, platí, že h(n) je prostorově konstruovatelná.

Důkaz. Plyne z prostorové konstruovatelnosti r(n).

Důkaz. Necht’ M_{1}, M_{2}, … jsou očíslované deterministické Turingovy stroje s jednoprvkovou vstupní abecedou. Dále budeme předpokládat, že délka zakódování stroje M_{i} je nejvýše log_{2} i (bez důkazu).

Zkonstruujeme jazyk L takový, že

1) pokud stroj M_{i} rozpoznává L, pak S_{i}(n) ≥ h(n − i) skoro všude

2) ∀k ∃j M_{j} : L(M_{j}) = L a S_{j}(n) ≤ h(n − k) skoro všude

Pokud takový L najdeme, jsme hotoví, nebot’ je-li dáno i takové, že L(M_{i}) = L, potom zvolíme k = i+1 a díky podmínce 2 víme, že ∃j : L(M_{j}) = L a S_{j}(n) ≤ h(n−i−1), díky podmínce 1 potom S_{i}(n) ≥ h(n−i) = r(h(n−i−1)) ≥ r(S_{j}(n)).

Popišme nyní konstrukci takového jazyka L (nad abecedou {0}).

Necht’ máme pevné n. Definujeme

σ(n) = min{j : j ≤ n, S_{j}(n) < h(n − j), ∀i<n : σ(i) ≠ j}

Pokud je σ(n) definováno, řekneme, že stroj M_{σ(n)} je zrušen číslem n.

V jednom kroku konstrukce uvažuji pevně dané n a množinu těch strojů, které nebyly zrušeny žádným k, k < n. Tato množina je v každém kroku konstrukce konečná. Z této množiny vyberu stroj s nejmenším indexem j = σ(n) takový, že S_{j}(n) < h(n − j), pokud takový index existuje.

Nyní zaručím, aby žádný zrušený stroj nepřijímal jazyk L: 0^{n} ∈ L ⇔ σ(n) je definované a M_{σ(n)} nepřijímá O^{n} Ukažme, že L splňuje obě uvedené podmínky. Necht’ i je takové, že L(M_{i}) = L a uvažujme stroje M_{1}, …, M_{i−1}. Některé

z těchto strojů jsou zrušeny, každý je zrušený nějakým konkrétním n. Necht’ n_{0} je maximum z těchto čísel. Potom platí: ∀n > max{n_{0}, i} : S_{i}(n) ≥ h(n − i). Dokážeme sporem. Necht’ ∃n > max{n_{0}, i} : S_{i}(n) < h(n − i), potom je ale splněna podmínka pro zrušení M_{i} a tedy L(M_{i}) ≠ L. Tedy podmínka 1 je splněna.

Ukažme dále, že L splňuje i podmínku 2.

Necht’ k je libovolné pevné, zkonstruujme M_{j} takový, že L(M_{j}) = L a S_{j}(n) ≤ h(n − k) skoro všude. Jinými slovy, M_{j} bude na rozhodnutí, zda 0^{n} patří do L, potřebovat prostor nejvýše h(n − k) skoro všude.

Pro vstup O^{n} musí M_{j}:

1) zjistit, zda je σ(n) definováno a pokud ano, tak σ(n) spočítat,

2) po zjištění σ(n) odsimulovat M_{σ(n)}, aby mohl rozhodnout, zda 0^{n} ∈ L.

Chceme-li zjistit σ(n), musíme nejprve zjistit, které stroje M_{i}, i ≤ n byly zrušeny nějakým číslem l < n. Pro pevné i a l stačí pracovat v prostoru h(l − i), protože pokud číslo l zruší stroj M_{i}, tak S_{i}(l) ≤ h(l−i). Pro vymezení uvedeného množství prostoru potřebujeme, aby byla h prostorově konstruovatelná.

Zde se ovšem objeví problém v případě, že l − i > n − k, protože potom se simulace do vymezeného prostoru nevejde. Problém obejdeme drobný trikem. Uvažujme M_{1}, …, M_{k} a necht’ n_{1} je největší číslo, kterým je některý z těchto strojů zrušen. Modifikujeme M tak, že ∀l ≤ n_{1} bude řídící jednotka obsahovat informace o tom, zda O^{l} ∈ L a číslo stroje zrušeného číslem l, pokud takový existuje. Potom ∀n ≤ n_{1} pracuje M s nulovou prostorovou složitostí, pro n > n_{1} stačí odsimulovat stroje M_{i} pro i = k + 1, …, n.

Stroj M_{i} pracuje na vstupu 0^{n} v prostoru h(l − i) ≤ h(n − k), protože l ≤ n a i ≥ k. Tedy stroj M_{i} se do uvedeného prostoru vejde, ještě je třeba ukázat, že se do něj vejde i stroj M při simulaci M_{i}.

Pro n > n_{1}, je-li definováno σ(n), tak σ(n) je alespoň k, tedy M_{σ(n)} na vstupu O^{n} pracuje v prostoru h(n − σ(n)), což je nejvýše h(n − k), protože σ(n) > k.

M postupně simuluje stroje M_{i} pro k + 1 ≤ i ≤ n na vstupech 0^{l} pro l ≤ n. Pro každou dvojici (i, l) stačí reprezentovat na stroji h(l − i) buněk stroje M_{i}.

i ≤ n, M_{i} je zakódován v nejvýše log_{2} i ≤ log_{2} n buňkách stroje M, tedy tím spíše libovolný symbol stroje M_{i} lze zakódovat v log_{2} n symbolech stroje M.

Protože víme, že r(x) ≥ x^{2}, platí h(x) ≥ 2^{2^{x−2}} (důkaz lze indukcí).

Tedy h(n − k) ≥ 2^{2^{n−k−2}} ≥ log_{2} n skoro všude, tedy prostor h(n − k) stačí pro simulaci M_{i} pro skoro všechna n.

Kromě místa na simulaci potřebuje M také prostor na ukládání seznamu zrušených strojů. Zrušených strojů je nejvýše n, tedy je potřeba nejvýše n·log_{2} n místa. Platí n · log_{2} n ≤ n^{2} ≤ h(n − k) skoro všude.

M tedy pracuje v prostoru 2h(n − k) skoro všude, dle lemma 4 existuje M′ pracující v prostoru 2h(n − k) všude a podle věty o kompresi existuje stroj M′′, který pracuje v prostoru h(n − k) všude.