Složitost a NP-úplnost

Sloˇzitost a NP-úplnost ˇ RNDr. Ondˇrej Cepek, Ph.D.

Do form´ atu TEX pˇrevedl Ladislav Strojil Pˇripom´ınky, dotazy, opravy na emailu: [email protected] Verze 1.1.1 Nejnovˇejˇs´ı verze k nalezen´ı vˇzdy na http://ladislav.strojil.cz/np.php

Obsah 1 Z´ akladn´ı definice 1.1 V´ ypoˇcetn´ı model . . . . . . . . . . . . . . . . . 1.2 K´ odov´ an´ı Turingov´ ych stroj˚ u . . . . . . . . . . 1.3 Univerz´ aln´ı Turing˚ uv stroj . . . . . . . . . . . . 1.4 Zpracov´ an´ı v´ yjimek . . . . . . . . . . . . . . . . 1.5 Nedeterminismus . . . . . . . . . . . . . . . . . 1.6 Prostorov´ a sloˇzitost . . . . . . . . . . . . . . . ˇ 1.7 Casov´ a sloˇzitost . . . . . . . . . . . . . . . . . . 1.8 Nedeterministick´ a prostorová a ˇcasová sloˇzitost

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

2 Z´ akladn´ı tˇ r´ıdy sloˇ zitosti

5

3 Prostorov´ aaˇ casov´ a komprese 3.1 Prostorov´ a komprese . . . . . 3.1.1 Redukce poˇctu pásek . ˇ 3.2 Casov´ a komprese . . . . . . . 3.2.1 Redukce poˇctu pásek .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

4 Konstruovatelnost funkc´ı 5 Hierarchie tˇ r´ıd sloˇ zitosti ˇ 5.1 Casov´ a hierarchie . . . . . . 5.2 Prostorov´ a hierarchie . . . . 5.3 Vˇety o hierarchii . . . . . . 5.4 Vˇeta o vtaz´ıch mezi tˇr´ıdami 5.5 Saviˇcova vˇeta . . . . . . . .

2 2 3 3 4 4 4 4 4

5 5 6 7 9 12

. . . . . . . . . . . . . . . . . . sloˇzitosti . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

15 15 16 16 18 20

6 Pokroˇ cil´ e vˇ ety o tˇ r´ıd´ ach sloˇ zitosti 21 6.1 Vˇeta o mezer´ ach (Borodin) . . . . . . . . . . . . . . . . . . . . . 23 6.2 Vˇeta o zrychlen´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1

1

Z´ akladn´ı definice

1.1

V´ ypoˇ cetn´ı model

Definice 1 (Turing˚ uv stroj). Deterministický Turing˚ uv stroj (DTS) M s k-p´ askami, kde k je konstanta, je pˇetice M = (Q, Σ, δ, q0 , F )

(1)

Q = koneˇcn´ a mnoˇzina stav˚ u ˇr´ıd´ıc´ı jednotky Σ = koneˇcn´ a p´ askov´ a abeceda δ : Q × Σk 7→ Q × Σk−1 × {L, N, R}k je pˇrechodov´ a funkce (ˇc´ asteˇcn´ a) q0 ∈ Q = poˇc´ ateˇcn´ı stav F ⊆ Q = mnoˇzina pˇrij´ımaj´ıc´ıch stav˚ u N´ asleduj´ıc´ı definice popisuje Turingovy stroje trochu podrobnˇeji a uvád´ı vysvˇetlen´ı z´ akladn´ıch pojm˚ u pouˇz´ıvan´ ych ve vztahu k tomuto modelu. Definice 2. • Vˇsech k p´ asek je jednosmˇernˇe (potenci´ alnˇe) nekoneˇcných. • Jedna z p´ asek je vstupn´ı a pouze ke ˇcten´ı. • Na vˇsech p´ ask´ ach se lze pohybovat obˇema smˇery (off-line model), v on-line modelu se lze na vstupn´ı p´ asce pohybovat pouze doprava. • Konfigurace Turingova stroje je urˇcena 1) stavem ˇr´ıd´ıc´ı jednotky 2) pozic´ı hlav na jednotlivých p´ ask´ ach 3) slovy na jednotlivých p´ ask´ ach (obsahem p´ asek) • Poˇc´ ateˇcn´ı konfigurace Turingova stroje 1) q0 2) vˇsechny hlavy zcela vlevo 3) na vstupn´ı p´ asce vstupn´ı slovo, ostatn´ı p´ asky pr´ azdné • Displej Turingova stroje je stav ˇr´ıd´ıc´ı jednotky a obsah pol´ıˇcek pod hlavami. • Krok Turingova stroje je pouˇz´ıt´ı pˇrechodové funkce na displej, pˇreps´ an´ı pol´ıˇcek poh hlavami a pˇr´ıpadný posun hlav a zmˇena stavu. • Výpoˇcet Turingova stroje je posloupnost krok˚ u zaˇc´ınaj´ıc´ı v poˇc´ ateˇcn´ı konfiguraci, kter´ a konˇc´ı zastaven´ım stroje nebo je nekoneˇcn´ a. • Zastaven´ı Turingova stroje je situace, kdy pro daný displej nen´ı pˇrechodov´ a funkce definov´ ana (pˇredpokl´ ad´ a se, ˇze to plat´ı pro vˇsechna q ∈ F ). • Pˇrij´ımaj´ıc´ı výpoˇcet Turingova stroje je výpoˇcet konˇc´ıc´ı zastaven´ım v pˇrij´ımaj´ıc´ım stavu (vstupn´ı slovo je pˇrijato).

2

• Odm´ıtaj´ıc´ı výpoˇcet Turingova stroje je výpoˇcet konˇc´ıc´ı zastaven´ım v jiném neˇz pˇrij´ımaj´ıc´ım stavu nebo nekoneˇcný. • Pˇrij´ımaný jazyk Turingova stroje M znaˇc´ıme L(M ) a definujeme jako {w ∈ Σ∗ |w w je pˇrij´ım´ ano M}. Definice 3 (Transducer). Turing˚ uv stroj, který m´ a nav´ıc výstupn´ı p´ asku, na kterou lze pouze ps´ at (znak pod hlavou neovlivˇ nuje pˇrechodovou funkci) a na které se hlava m˚ uˇze pohybovat pouze vpravo, nazýv´ ame transducer. (Stroj bez této p´ asky se nazýv´ a acceptor). Existuj´ı r˚ uzné varianty Turingov´ ych stroj˚ u, o kter´ ych lze ukázat, ˇze maj´ı stejnou v´ ypoˇcetn´ı s´ılu, tedy ˇze pˇrij´ımaj´ı stejnou tˇr´ıdu jazyk˚ u (rekurzivnˇe spoˇcetné mnoˇziny). Jsou to napˇr´ıklad: • on-line Turingovy stroje; • jednop´ askové Turingovy stroje; • Turingovy stroje s oboustrannˇe nekoneˇcnou páskou; • Turingovy stroje s v´ıce hlavami na jedné pásce. D˚ uvody, proˇc je v´ yhodné pouˇz´ıvat Turingovy stroje jako v´ ypoˇcetn´ı model jsou zˇrejmé. Pˇrednˇe je to jasnˇe definovan´ y koncept ˇcasové sloˇzitosti v´ ypoˇctu (bˇehu algoritmu) jako poˇcet krok˚ u daného Turingova stroje nad dan´ ym vstupem. Analogicky jasnˇe definovan´ y koncept prostorové sloˇzitosti v´ ypoˇctu (bˇehu algoritmu) jako poˇcet pouˇzit´ ych bunˇek na pracovn´ıch páskách stroje. Hlavn´ı nev´ yhodou je fakt, ˇze tento model je pˇr´ıliˇs elementárn´ı a nehod´ı se ke ”skuteˇcnému programov´ an´ı”.

1.2

K´ odov´ an´ı Turingov´ ych stroj˚ u

1) Oˇc´ıslujeme stavy q ∈ Q a symboly s ∈ Σ binárn´ımi ˇc´ısly. 2) Pop´ıˇseme pˇrechodovou funkci v abecedˇe A = {0, 1, δ, (, ), =, L, N, R, , } zˇretˇezen´ım z´ apis˚ u typu δ(q, x1 , x2 , . . . , xk ) = (q 0 , y1 , . . . , yk , Z). 3) Pˇrep´ıˇseme z´ apis z abecedy A do abecedy {0, 1} Potom pˇri pevnˇe zvoleném k´ odován´ı kaˇzd´ y Turing˚ uv stroj jednoznaˇcnˇe odpov´ıdá pˇrirozenému ˇc´ıslu. Definice 4 (G¨ odelovo ˇ c´ıslo). K´ od Turingova stroje M budeme nazývat jeho G¨ odelovým ˇc´ıslem.

1.3

Univerz´ aln´ı Turing˚ uv stroj

Definice 5 (Univerz´ aln´ı Turing˚ uv stroj). Univerz´ aln´ı Turing˚ uv stroj je Turing˚ uv stroj, který m´ a jako vstup G¨ odelovo ˇc´ıslo nˇejakého Turingova stroje M a pro vstupn´ı slovo w pro M pracuje tak, ˇze simuluje pr´ aci M nad w.

3

1.4

Zpracov´ an´ı v´ yjimek

Pomoc´ı pˇrid´ an´ı nov´ ych stav˚ u ˇr´ıd´ıc´ı jednotky lze jednoduˇse oˇsetˇrit libovolnou pevnˇe danou koneˇcnou mnoˇzinu vstup˚ u. Provedeme to tak, ˇze zkontruujeme koneˇcn´ y automat (strom) rozpoznávaj´ıc´ı danou koneˇcnou mnoˇzinu slov (koneˇcn´ y automat odpov´ıdá Turingovˇe stroji bez p´ asek). Turing˚ uv stroj potom napˇred simuluje chod daného koneˇcného automatu. V pˇr´ıpadˇe, ˇze je na vstupu jedno z rozpoznávan´ ych slov, Turing˚ uv stroj se zastav´ı. Pokud ne, odjede hlavou na vstupn´ı pásce na zaˇcátek a spust´ı p˚ uvodn´ı Turing˚ uv stroj.

1.5

Nedeterminismus

Od deterministického Turingova stroje se jeho nedeterministická varianta liˇs´ı pouze definic´ı pˇrechodové funkce a stanoven´ım odliˇsn´ ych podm´ınek, za kter´ ych je slovo pˇrijato. Definice 6 (Nedeterministick´ y turing˚ uv stroj). Definujme stroj jako v definici deterministického Turingova stroje s n´ asleduj´ıc´ımi rozd´ıly: • δ : Q × Σk 7→ P(Q × Σk−1 × {L, N, R}k ) je pˇrechodov´ a funkce (ˇc´ asteˇcn´ a) • Slovo w je pˇrij´ım´ ano, jestliˇze existuje alespoˇ n jeden pˇrij´ımaj´ıc´ı výpoˇcet. Pro zjednoduˇsen´ı m˚ uˇzeme pˇredpokládat binárn´ı vˇetven´ı v´ ypoˇcetu. Snadno se d´ a uk´ azat, ˇze se jedn´ a o v´ ypoˇcetnˇe ekvivalentn´ı model.

1.6

Prostorov´ a sloˇ zitost

Definice 7. Necht’ M je deterministický Turing˚ uv stroj, pro který plat´ı, ˇze na kaˇzdém vstupu délky n pouˇzije pˇri výpoˇctu nejvýˇse S(n) bunˇek na pracovn´ıch páskách. Potom ˇr´ık´ ame, ˇze M m´ a prostorovou sloˇzitost S(n) a ˇze jazyk L(M ) m´ a prostorovou sloˇzitost S(n).

1.7

ˇ Casov´ a sloˇ zitost

Definice 8. Necht’ M je deterministický Turing˚ uv stroj, pro který plat´ı, ˇze na kaˇzdém vstupu délky n provede pˇri výpoˇctu nejvýˇse T (n) krok˚ u, neˇz se zastav´ı. Potom ˇr´ık´ ame, ˇze M m´ a ˇcasovou sloˇzitost T (n) a ˇze jazyk L(M ) m´ a ˇcasovou sloˇzitost T (n).

1.8

Nedeterministick´ a prostorov´ aaˇ casov´ a sloˇ zitost

Definice jsou stejné jako u deterministick´ ych Turing˚ uv´ ych stroj˚ u s t´ım, ˇze nyn´ı poˇzadujeme, aby ∀w ∈ Σ∗ , |w| = n vˇsechny moˇzné v´ ypoˇcty pouˇzily nejv´ yˇse S(n) pol´ıˇcek a skonˇcily nejdéle za T (n) krok˚ u.

4

2

Z´ akladn´ı tˇ r´ıdy sloˇ zitosti

DSP ACE(S(n)) = tˇr´ıda N SP ACE(S(n)) = tˇr´ıda DT IM E(T (n)) = tˇr´ıda N T IM E(S(n)) = tˇr´ıda

jazyk˚ u deterministické prostorové sloˇzitosti S(n) jazyk˚ u nedeterministické prostorové sloˇzitosti S(n) jazyk˚ u deterministické ˇcasové sloˇzitosti T (n) jazyk˚ u nedeterministické ˇcasové sloˇzitosti T (n)

Tvrzen´ı 1 (Trivi´ aln´ı vztahy). ∀ S(n) : DSP ACE(S(n)) ⊆ N SP ACE(S(n)) ∀ T (n) : DT IM E(T (n)) ⊆ N T IM E(T (n)) ∀ S1 (n) ≤ S2 (n) ⇒ DSP ACE(S1 (n)) ⊆ DSP ACE(S2 (n)) N SP ACE(S1 (n)) ⊆ N SP ACE(S2 (n)) ∀ T1 (n) ≤ T2 (n) ⇒ DT IM E(T1 (n)) ⊆ DT IM E(T2 (n)) N T IM E(T1 (n)) ⊆ N T IM E(T2 (n))

(2) (3) (4) (5)

D˚ ukaz. Zˇrejmé.

3 3.1

Prostorov´ aaˇ casov´ a komprese Prostorov´ a komprese

Vˇ eta 1 (O line´ arn´ı prostorov´ e kompresi). Necht’ L je jazyk pˇrij´ımaný k-p´ askovým deterministickým Turingovým strojem M s prostorovou sloˇzitost´ı S(n). Potom pro ∀r ∈ N+ existuje k-p´ askový deterministický Turing˚ uv stroj M’ s prostorovou sloˇzitost´ı d 1r S(n)e, který pˇrij´ım´ a jazyk L. D˚ ukaz. Kaˇzd´ y znak abecedy stroje M’ bude kódovat jednu r-tici znak˚ u abecedy p˚ uvodn´ıho stroje. |ΣM 0 | (velikost abecedy M’) bude rovno |ΣM |r a vzhledem ke koneˇcnosti ΣM bude také koneˇcná. Jeden krok stroje M bude simulován jedn´ım krokem stroje M’. Pozici p˚ uvodn´ıho stroje ”uvnitˇr” pol´ıˇcka si stroj M 0 bude pamatovat ve stavech. Nejprve necht’ k = 1. Je-li QM = {q0 , q1 , . . . , qs } mnoˇzina stav˚ u stroje M , potom definujeme QM 0 = {q01 , q02 , . . . , q0r , . . . , qs1 , qs2 , . . . , qsr }. Pˇrechodov´ a funkce δM 0 bude simulovat pohyb hlavy zmˇenou horn´ıho indexu stavu, v pˇr´ıpadˇe, ˇze by index klesl na nulu nebo byl vˇetˇs´ı neˇz r, dojde k vlastn´ımu posunu hlavy (stroje M’). Vˇsechna pravidla tvaru δM (qi , a) = (qj , b, N ) nahrad´ıme mnoˇzinou pravidel δM 0 (qil , xl ) = (qjl , y l , N ), ∀ 1 ≤ l ≤ r, ∀ dvojice x, y ∈ ΣM 0 , kde x kóduje (. . . , a, . . .) a y k´ oduje (. . . , b, . . .) (y se liˇs´ı od x pouze na l-té pozici). Vˇsechna pravidla tvaru δM (qi , a) = (qj , b, R) nahrad´ıme mnoˇzinou pravidel δM 0 (qil , xl ) = (qjl+1 , y l , N ), ∀ 1 ≤ l < r a δM 0 (qir , xl ) = (qj1 , y r , R). Analogicky pro pohyb doleva. δM (qi , a) = (qj , b, L) nahrad´ıme mnoˇzinou pravidel δM 0 (qil , xl ) = (qjl−1 , y l , N ), ∀ 1 < l ≤ r a δM 0 (qi1 , xl ) = (qjr , y 1 , L). Nyn´ı pro obecné k. 5

QM 0 = {qip | 0 ≤ i ≤ s, ∀p ∈ ΣrM } Promˇenn´ a p zde prob´ıh´ a pˇres vˇsechny r-tice znak˚ u abecedy ΣM . Analogicky jako pro pˇr´ıpad k = 1 se sestroj´ı pˇrechodová funkce δM 0 . D˚ usledek 1. ∀ r ∈ N+ : DSP ACE(S(n)) = DSP ACE(d S(n) r e) D˚ ukaz. Plyne pˇr´ımo z vˇety 1. Vˇ eta 2. ∀ r ∈ N+ : N SP ACE(S(n)) = N SP ACE(d S(n) r e) D˚ ukaz. Zobecnˇen´ım d˚ ukazu vˇety 1 pro nedeterministick´ y pˇr´ıpad. 3.1.1

Redukce poˇ ctu p´ asek

Vˇ eta 3 (O redukci poˇ ctu p´ asek pro prostorovou sloˇ zitost). Necht’ L je jazyk pˇrij´ımaný k-p´ askovým deterministickým Turingovým strojem s prostorovou sloˇzitost´ı S(n). Potom existuje deterministický Turing˚ uv stroj M 0 s jednou pracovn´ı p´ askou a prostorovou sloˇzitost´ı S(n) pˇrij´ımaj´ıc´ı jazyk L. D˚ ukaz. Myˇslenka d˚ ukazu: i-té pol´ıˇcko na pásce stroje M 0 bude kódovat obsah k pol´ıˇcek (z kaˇzdé p´ asky stroje M jedno). Dále bude v pol´ıˇcku zakódována kromˇe obsahu p˚ uvodn´ıch p´ asek i informace, které z hlav se nacház´ı nad t´ımto pol´ıˇckem. Nov´ a abeceda bude definována následovnˇe: ΣM 0 = {x0 , . . . , x2k −1 |∀x ∈ ΣkM } Indexy si m˚ uˇzeme pˇredstavit v jejich binárn´ım zápisu jako informaci o tom, které hlavy simulovaného stroje M se nacház´ı nad dan´ ym pol´ıˇckem. Jeden krok stroje M je simulován v O(S(n)) kroc´ıch stroje M 0 tak, ˇze hlava projde celou p´ asku, najde pozice hlav a odsimuluje krok M . Vzhledem k tomu, ˇze pˇri simulaci nám nezáleˇz´ı na ˇcasové sloˇzitosti, lze pro jednoduchost uvaˇzovat v´ ypoˇcet, kter´ y má k fáz´ı a v kaˇzdé fázi se odsimuluje pr´ ace M na jediné p´ asce. Na zaˇcátku fáze a po jej´ım ukonˇcen´ı bude hlava M 0 na zaˇc´ atku p´ asky. Jak bude prob´ıhat samotná simulace? Kaˇzdou instrukci p˚ uvodn´ıho stroje nahrad´ıme posloupnost´ı instrukc´ı M 0 , kde stavy ˇr´ıd´ıc´ı jednotky M 0 obsahuj´ı informaci o displeji stroje M . Tato posloupnost zaˇc´ıná s poˇcáteˇcn´ım displejem a konˇc´ı s koncov´ ym displejem simulované instrukce. 1) Instrukce M oˇc´ıslujeme a tato ˇc´ısla zakódujeme do stav˚ u M 0 . T´ım zajist´ıme, ˇze po zaˇc´ atku provádˇen´ı posloupnosti instrukc´ı bude tato posloupnost dokonˇcena a nebudou se m´ıchat r˚ uzné posloupnosti mezi sebou. Dále si budeme ve stavu pamatovat ˇc´ıslo aktuáln´ı fáze (poˇcet fáz´ı je omezen poˇctem p´ asek, to znamená koneˇcn´ y a pevnˇe dan´ y). V´ ysledn´ y poˇcet stav˚ u je tedy také koneˇcn´ y. 2) instrukci δM (qi , a1 , . . . , ak ) = (qj , b1 , . . . , bk , z1 , . . . , zk ), která má ˇc´ıslo l, nahrad´ıme posloupnost´ı stav˚ u: (l, qi , a1 , . . . , ak , 1R ). Stroj M 0 zaˇc´ıná v tomto stavu na prvn´ı pozici své pracovn´ı pásky. Nyn´ı M 0 projde pásku smˇerem doprava a hled´ a pol´ıˇcko, ve kterém je oznaˇcena pozice prvn´ı hlavy. • Kdyˇz x nek´ oduje pozici prvn´ı hlavy, δM 0 ((l, qi , a1 , . . . , ak , 1R ), x) = ((l, qi , a1 , . . . , ak , 1R ), x, R).

6

• Kdyˇz x k´ oduje pozici prvn´ı hlavy, rozliˇs´ıme následuj´ıc´ı pˇr´ıpady podle smˇeru, kter´ ym by se prvn´ı hlava posunula pˇri práci stroje M . a) z1 = N znak x kóduj´ıc´ı (a1 , a2 , . . . , ak ) se pˇrep´ıˇse na znak y k´ oduj´ıc´ı (b1 , a2 , . . . , ak ) se stejnou mnoˇzinou hlav. Zároveˇ n se provede aktualizace displeje a 1R se zmˇen´ı na 1L . δM 0 ((l, qi , a1 , . . . , ak , 1R ), x) = ((l, qj , b1 , a2 , . . . , ak , 1L ), y, N ) b) z1 = R znak x kóduj´ıc´ı (a1 , a2 , . . . , ak ) se pˇrep´ıˇse na znak y k´ oduj´ıc´ı (b1 , a2 , . . . , ak ) se stejnou mnoˇzinou hlav, s vyj´ımkou prvn´ı hlavy. δM 0 ((l, qi , a1 , . . . , ak , 1R ), x) = ((l, qj , b1 , a2 , . . . , ak , 1N ), y, R) δM 0 ((l, qj , a1 , . . . , ak , 1N ), z) = ((l, qj , b1 , a2 , . . . , ak , 1L ), z 0 , N ) Zde z 0 k´ oduje stejnou k-tici jako z, ale nav´ıc kóduje pˇr´ıtomnost prvn´ı hlavy. c) z1 = L. Zcela analogicky s pˇr´ıpadem R. • Po a,b,c n´ asleduje odjezd hlavy M’ na zaˇcátek pásky a pˇrepnut´ı do stavu (l, qj , b1 , a2 , . . . , ak , 2R ). • Simulace d´ ale pokraˇcuje dalˇs´ı fáz´ı.

Vˇ eta 4 (Nedeterministick´ a verze). Vˇeta 3 plat´ı ve stejném znˇen´ı i pro nedeterministické Turingovy stroje. D˚ ukaz. Simulace uveden´ a v d˚ ukazu vˇety 3 je pouˇzitelná beze zmˇen i pro pˇr´ıpad nedeterministického Turingova stroje.

3.2

ˇ Casov´ a komprese

Lemma 1 (O line´ arn´ım zrychlen´ı). Necht’ L je jazyk pˇrij´ımaný k-p´ askovým deterministickým Turingovým strojem M s ˇcasovou sloˇzitost´ı T (n). D´ ale necht’ plat´ı k ≥ 2 a necht’ r je celé ˇc´ıslo, r > 0. Potom existuje deterministický Turing˚ uv stroj M 0 takový, ˇze kaˇzdý vstup w délky n pˇrij´ım´ a pr´ avˇe, kdyˇz jej pˇrij´ım´ a M . Pracuje-li M nad w t krok˚ u, pracuje M 0 nad w v ˇcase n + dn/re + 6dt/re. Pozn´ amka: Pˇredpokl´ ad´ ame, ˇze na vstupn´ı pásku je moˇzno zapisovat. D˚ ukaz. V prvn´ı f´ azi zkop´ıruje M 0 obsah vstupn´ı pásky na pracovn´ı pásku (ta ’ existuje, nebot k ≥ 2), souˇcasnˇe s kop´ırován´ım M 0 provede pˇrekódován´ı vstupu tak, ˇze v jednom pol´ıˇcku c´ılové pásky je kódováno r pol´ıˇcek vstupn´ı pásky, kde r je libovolné celé ˇc´ıslo > 0. Po proveden´ı se vrát´ı na zaˇcátek pásky. Nadále bude tuto p´ asku pouˇz´ıvat jako vstupn´ı. Simulace M : Konkrétn´ı ”jemnou” pozici vrámci jedné buˇ nky nového stroje si budeme pamatovat ve stavech stroje M 0 . • Stroj provede sekvenci pohyb˚ u vlevo, vpravo, vpravo, vlevo (4 kroky), priˇcemˇz si ve stavech zapamatuje obsah sousedn´ıch pol´ıˇcek. T´ım stroj z´ıskal informaci o pol´ıˇcku pod hlavou, pol´ıˇcku vpravo od hlavy a pol´ıˇcku vlevo od hlavy (vˇsimnˇete si, ˇze se jedná o 3·r pol´ıˇcek stroje M ).

7

• V dalˇs´ı f´ azi M 0 zjist´ı stav tˇechto 3r pol´ıˇcek stroje M po r kroc´ıch. Uvˇedomte si, ˇze bˇehem r krok˚ u stroj M nem˚ uˇze tato pol´ıˇcka opustit, nebot’ se jeho hlava nach´ azela v prostˇredn´ı tˇretinˇe tohoto u ´seku. Nav´ıc zmˇena stavu tohoto u ´seku obsahuje jenom koneˇcnou informaci a tedy m˚ uˇze b´ yt zak´ odov´ ana do pˇrechodové funkce. Tedy celá tato fáze odpov´ıdá 1 kroku stroje M 0 . Nen´ı potˇreba jej ale zapoˇc´ıtávat do délky v´ ypoˇctu, nebot’ z´ıskán´ı potˇrebné informace lze provést jiˇz v posledn´ım kroku pˇredchoz´ı fáze (návrat hlavy nad prostˇredn´ı pol´ıˇcko bude spojen s pˇrechodem do odpov´ıdaj´ıc´ıho stavu). Nav´ıc je zˇrejmé, ˇze stroj M mohl bˇehem tˇechto r krok˚ u modifikovat nejv´ yˇse 2 z tˇechto u ´sek˚ u (kaˇzd´ y má totiˇz délku r, nav´ıc nemohl modifikovat oba krajn´ı u ´seky souˇcasnˇe). V pˇr´ıpadˇe, ˇze modifikoval pouze prostˇredn´ı pol´ıˇcko, lze jeho nov´ y obsah zapsat bˇehem jednoho kroku (v takovém pˇr´ıpadˇe udˇel´ a stroj jeden prázdn´ y krok), jinak budou potˇreba dva kroky (doprava a doleva, v odpov´ıdaj´ıc´ım poˇrad´ı, podle toho, které z krajn´ıch pol´ıˇcek bylo zmˇenˇeno). • Stroj M 0 pˇrijme ˇci odm´ıtne, jestliˇze stroj M bˇehem simulovaného u ´seku pˇrijmul ˇci odm´ıtnul. Pˇredzpracov´ an´ı vstupn´ı p´ asky vyˇzadovalo n + dn/re krok˚ u (druh´ y sˇc´ıtanec odpov´ıd´ a ˇcasu potˇrebnému pro návrat hlavy na zaˇcátek pásky). Pro simulaci t krok˚ u je zapotˇreb´ı dt/re blok˚ u v´ ypoˇctu M 0 , z nichˇz kaˇzd´ y trv´ a 6 krok˚ u. V souˇctu dost´ av´ ame tvrzen´ı lemmatu. Vˇ eta 5 (O line´ arn´ım zrychlen´ı). Necht’ L je jazyk pˇrij´ımaný k-p´ askovým deterministickým Turingovým strojem M s ˇcasovou sloˇzitost´ı t(n). D´ ale necht’ plat´ı k ≥ 2 a t(n) ∈ ω(n). Potom pro ∀c > 0 existuje k-p´ askový deterministický Turing˚ uv stroj M’ s ˇcasovou sloˇzitost´ı c · t(n) pˇrij´ımaj´ıc´ı L. D˚ ukaz. Necht’ r je celé ˇc´ıslo takové, ˇze r > 12/c. Sestroj´ıme M 0 jako v pˇredcházej´ıc´ım lemmatu. M 0 pracuje nad vstupem délky n v ˇcase n + dn/re + 6dt(n)/re. Pro r ≥ 2 lze tento v´ yraz zhora omezit jako 2n + 6 + (6/r) · t(n). Z pˇredpokladu t(n) ∈ ω(n) dostáváme, ˇze pro skoro vˇsechna n je tento v´ yraz menˇs´ı neˇz (c/2) · t(n) + (6/r) · t(n). Z volby r > 12/c dostáváme, ˇze ˇcas v´ ypoˇctu je omezen c · t(n). Koneˇcnˇe mnoho pˇr´ıpad˚ u, pro které nen´ı nerovnost splnˇena, oˇsetˇr´ıme koneˇcn´ ym automatem a stroj M 0 nad nimi bude pracovat v konstantn´ım ˇcase. D˚ usledek 2. Pokud t(n) ∈ ω(n), potom ∀ c > 0 : DT IM E(t(n)) = DT IM E(c · t(n)) D˚ ukaz. Plyne pˇr´ımo z vˇety 5. Vˇ eta 6 (O line´ arn´ım zrychlen´ı, ˇ c´ ast 2). Necht’ L je jazyk pˇrij´ımaný k-p´ askovým deterministickým Turingovým strojem M s ˇcasovou sloˇzitost´ı t(n) = c·n. D´ ale necht’ plat´ı k ≥ 2 a c > 1. Potom pro ∀ε > 0 existuje k-p´ askový deterministický Turing˚ uv stroj M 0 s ˇcasovou sloˇzitost´ı (1 + ε) · n pˇrij´ımaj´ıc´ı L.

8

D˚ ukaz. Budeme poˇzadovat, aby n + dn/re + 6dcn/re ≤ (1 + ε) · n n + n/r + 6cn/r + 7 ≤ (1 + ε) · n (1 + 1/r + 6c/r + 7/n) · n ≤ (1 + ε) · n

(6) (7) (8)

Vztah (6) je poˇzadovan´ a nerovnost, v (7) je na levé stranˇe horn´ı odhad levé strany (6), tedy staˇc´ı uk´ azat (7). Nerovnost (8) je prostá u ´prava (7). Uk´ aˇzeme, ˇze lze volit r a n0 tak, ˇze pro n > n0 plat´ı (1/r + 6c/r + 7/n) < ε. Poˇzadujeme: 1/r ≤ ε/3 6c/r ≤ ε/3 7/n0 ≤ ε/3

dost´ av´ ame r ≥ 3/ε dost´ av´ ame r ≥ 18c/ε dost´ av´ ame n0 ≥ 21/ε

(9) (10) (11)

Z (9) a (10) dost´ av´ ame r = max{3/ε, 18c/ε} = 18c/ε. Z (11) dost´ av´ ame n0 = 21/ε. Tvrzen´ı vˇety je dok´ az´ ano. D˚ usledek 3. Pokud t(n) = cn, kde c > 1, potom ∀ ε > 0 : DT IM E(t(n)) = DT IM E((1 + ε)n) D˚ ukaz. Plyne pˇr´ımo z vˇety 6. Vˇ eta 7 (Nedeterministick´ a verze). Pokud t(n) ∈ ω(n), potom ∀c > 0 : N T IM E(t(n)) = N T IM E(c · t(n)) Pokud t(n) = cn, c > 1, potom ∀ε > 0 : N T IM E(t(n)) = N T IM E((1+ε)n) D˚ ukaz. Pˇredchoz´ı d˚ ukazy lze zobecnit (pomoc´ı odhadu poˇctu dosaˇziteln´ ych konfigurac´ı) i pro nedeterministick´ y pˇr´ıpad. 3.2.1

Redukce poˇ ctu p´ asek

Vˇ eta 8 (O redukci poˇ ctu p´ asek pro ˇ casovou sloˇ zitost). Necht’ L ∈ DT IM E(T (n))1 . Potom existuje jednop´ askový deterministický Turing˚ uv stroj M s ˇcasovou sloˇzitost´ı (T (n))2 , který pˇrij´ım´ a L. D˚ ukaz. Pouˇzijeme kombinaci vˇety o zrychlen´ı a vˇety o redukci poˇctu pásek pro prostorovou sloˇzitost. Pokud je L pˇrij´ım´ an jednopáskov´ ym strojem, nen´ı co dokazovat. Necht’ je tedy pˇrij´ım´ an k-páskov´ ym strojem, kde k > 1. 1) Necht’ T (n) ∈ ω(n). Dle vˇety o lineárn´ım zrychlen´ı existuje deterministick´ y Turing˚ uv stroj M 0 pˇrij´ımaj´ıc´ı L v ˇcase √12k ·T (n) = T 0 (n) v prostoru S 0 (n). Nyn´ı pouˇzijeme vˇetu o redukci poˇctu pásek pro prostorovou sloˇzitost a z n´ı odvod´ıme stroj, kter´ y má jednu pásku a kter´ y pˇrij´ımá L v ˇcase T 00 (n) ≤ 2k · S 0 (n) · T 0 (n) ≤ 2k · (T 0 (n))2 = (T (n))2 1 T (n)

splˇ nuje jist´ e ”m´ırn´ e poˇ zadavky”: pˇredpokl´ adejme, ˇ ze bud’ T (n) ∈ ω(n) nebo T (n) = √ cn, kde c > 2k

9

2) Necht’ T (n) = cn, kde c > tak, aby platilo c 1+ε= √ 2k

tedy

√

2k. Dle vˇety o lineárn´ım zrychlen´ı zvol´ıme ε

1 (1 + ε)n = √ T (n) 2k

(12)

Zbytek stejnˇe jako v bodˇe 1.

D˚ usledek 4. Pokud L ∈ N T IM E(T (n)), potom existuje jednop´ askový nedeterministický Turing˚ uv stroj s ˇcasovou sloˇzitost´ı (T (n))2 pˇrij´ımaj´ıc´ı L. D˚ ukaz. Plyne pˇr´ımo z vˇety 8. Vˇ eta 9 (O redukci poˇ ctu p´ asek pro ˇ casovou sloˇ zitost, 2). Necht’ je L pˇrij´ım´ an k-p´ askovým deterministickým Turingovým strojem M s ˇcasovou sloˇzitost´ı T (n). Potom existuje 2-p´ askový deterministický Turing˚ uv stroj M 0 s ˇcasovou sloˇzitost´ı T (n) log2 T (n) pˇrij´ımaj´ıc´ı L. D˚ ukaz. Prvn´ı p´ aska stroje bude m´ıt 2k stop, teda kaˇzd´ y znak abecedy ΣM 0 bude k´ odovat 2k znak˚ u p˚ uvodn´ı abecedy (plus speciáln´ı prázdn´ y symbol). Druh´ a (pomocn´ a) p´ aska bude slouˇzit k pˇresun˚ um dat na pásce prvn´ı. Obˇe p´ asky pˇredpokl´ ad´ ame oboustrannˇe nekoneˇcné. Hlavn´ı myˇslenka: Abychom se vyhnuli hledán´ı displeje p˚ uvodn´ıho stroje, budeme udrˇzovat displej na jediném pol´ıˇcku. Tedy m´ısto pohybu hlav budeme pohybovat obsahem celé p´ asky. Pˇresuny dat budeme dˇelat tak, aby malé pˇresuny byly ˇcastˇejˇs´ı a velké (vzd´ alené) pˇresuny byly vzácné. Prvn´ı p´ aska stroje bude rozdˇelena do blok˚ u . . . , B−2 , B−1 , B0 , B1 , B2 , . . .. Blok B0 se sest´ av´ a z jediného pol´ıˇcka a bude obsahovat displej stroje M . Pro ostatn´ı bloky plat´ı: ∀i, |i| ≥ 1 : |Bi | = 2|i|−1 . Bloky jsou oddˇeleny znaˇckami, které jsou umist’ov´ any pˇri prvn´ım pouˇzit´ı bloku. Uk´ aˇzeme simulaci pr´ ace M na prvn´ı pásce (stroje M ). Na zaˇc´ atku v´ ypoˇctu je obsah prvn´ı pásky M na spodn´ı stopˇe pásky M 0 . Po celou dobu simulace budou platit následuj´ıc´ı invarianty: 1) Pro kaˇzdé i > 0 nast´ av´ a právˇe jedna ze tˇr´ı moˇznost´ı. a) Bi m´ a obˇe stopy plné a B−i má obˇe stopy prázdné; b) B−i m´ a obˇe stopy plné a Bi má obˇe stopy prázdné; c) Bi i B−i maj´ı spodn´ı stopu plnou a horn´ı stopu prázdnou. 2) ∀i Bi obsahuje souvisl´ y 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) B0 obsahuje symbol pouze na doln´ı stopˇe, horn´ı stopa obsahuje speciáln´ı znaˇcku, kter´ a slouˇz´ı pro vyhledán´ı tohoto bloku. 4) ∀i Bi obsahuje interval pásky stroje M bezprostˇrednˇe nalevo od obsahu bloku Bi+1 .

10

Simulace jednoho kroku M . Displej je v B0 . Krok se skládá ze zmˇeny dat na p´ asce (zˇrejmé) a simulace posunu hlavy. Ukáˇzeme si pˇr´ıpad posunu hlavy doleva, tedy data budeme posunovat doprava. i) Hlava jede doprava, dokud nenajde blok Bi takov´ y, ˇze má alespoˇ n jednu stopu volnou. (To znamená, ˇze vˇsechny bloky, které pˇrejel, byly zcela plné!) ii) Hlava jede zp´ atky a kop´ıruje obsah blok˚ u Bi−1 , Bi−2 , . . . , B0 na pomocnou p´ asku. Bloky projede kaˇzd´ y tˇrikrát, nebot’ mus´ı pˇrekop´ırovat obsah obou stop a to ve spr´ avném poˇrad´ı. iii) Hlava jede doprava a kop´ıruje obsah pomocné pásky do spodn´ı stopy blok˚ u B1 , B2 , . . . , Bi−1 . Horn´ı stopy vyprázdn´ı. V okamˇziku, kdy hlava dojede na konec bloku Bi−1 , zbyde na pracovn´ı pásce pˇresnˇe |Bi | nepˇrekop´ırovan´ ych pol´ıˇcek. a) V pˇr´ıpadˇe, ˇze byl Bi zcela prázdn´ y, nap´ıˇse je M 0 do spodn´ı stopy. b) V pˇr´ıpadˇe, ˇze byl Bi poloprázdn´ y, nap´ıˇse je M 0 do horn´ı stopy. iv) Hlava jede vlevo a na pomocnou pásku si poˇc´ıtá vzdálenost bloku Bi od B0 . v) Hlava jede vlevo a pomoc´ı poˇc´ıtadla najde lev´ y okraj B−i . vi) Hlava jede vpravo a na pomocnou pásku kop´ıruje obsah a) horn´ı stopy B−i , v pˇr´ıpadˇe, ˇze byl B−i zcela pln´ y (tj. Bi byl zcela pr´ adzn´ y) b) doln´ı stopy B−i , v pˇr´ıpadˇe, ˇze byl B−i polopln´ y (tj. Bi byl polopln´ y) vii) Hlava jede vpravo a do spodn´ı stopy blok˚ u B−i+1 , B−i+2 , . . . , B0 kop´ıruje obsah pomocné p´ asky. Bloky B−i+1 , B−i+2 , . . . , B0 musely b´ yt prázdné, nebot’ Bi byl prvn´ı blok napravo od B0 , kter´ y nebyl pln´ y. Kroky i - vii nazveme Bi operac´ı. Pro Bi operaci plat´ı, ˇze zachovává platnost uveden´ ych invarant˚ u a trv´ a ˇcas O(|Bi |). Jak´ a je ˇcasov´ a sloˇzitost celé simulace? Operace Bi m˚ uˇze b´ yt provedena pouze jednou za 2i−1 krok˚ u stroje M . D˚ uvodem je fakt, ˇze po jej´ım proveden´ı jsou horn´ı stopy blok˚ u B1 , . . . , Bi−1 pr´ azdné a tedy je potˇreba posunout pásku alespoˇ n 2i−1 -kr´ at, coˇz vyˇzaduje nejménˇe takov´ y poˇcet krok˚ u. Pokud stroj M udˇel´ a T (n) krok˚ u bˇehem v´ ypoˇctu, m˚ uˇze se Bi operace provést nejv´ yˇse bT (n)/2i−1 c-kr´ at. Staˇc´ı uvaˇzovat Bi operace pro i ≤ dlog2 T (n)e ≤ log2 T (n) + 1. Necht’ m je konstanta taková, ˇze kaˇzdá Bi operace trvá nejv´ yˇse m · 2i−1 0 krok˚ u. Stroj M tedy udˇel´ a maximálnˇe log2 T (n)+1 0

T (n) ≤

X

m · 2i−1 bT (n)/2i−1 c ≤

i=1

(13)

log2 T (n)+1

≤

X

m · T (n) ≤ log2 T (n) · m · T (n)

i=1

Pro simulaci pr´ ace na vˇsech k páskách je potˇreba k · m · T (n) log2 T (n). Po pouˇzit´ı vˇety o zrychlen´ı dostáváme deterministick´ y Turing˚ uv stroj M 00 , kter´ y pˇrij´ım´ a L v ˇcase T (n) log2 T (n). 11

4

Konstruovatelnost funkc´ı

Definice 9. Funkce f : N → N je rekurzivn´ı, jestliˇze existuje deterministický Turing˚ uv stroj M , který pro vstup 1n vyd´ a výstup 1f (n) . Definice 10. Funkce f : N → N je vyˇc´ısliteln´ a v ˇcase O(f ), jestliˇze je rekurzivn´ı a ∃c ≥ 1 takové, ˇze pˇr´ısluˇsný deterministický Turing˚ uv stroj M udˇel´ a nejvýˇse c · f (n) krok˚ u, neˇz vyd´ a výstup 1f (n) . Definice 11. Funkce f : N → N je vyˇc´ısliteln´ a v prostoru O(f ), jestliˇze je rekurzivn´ı a ∃c ≥ 1 takové, ˇze pˇr´ısluˇsný deterministický Turing˚ uv stroj M pouˇzije nejvýˇse c · f (n) prostoru, neˇz vyd´ a výstup 1f (n) . Definice 12. Funkce f : N → N je ˇcasovˇe konstruovateln´ a, pokud existuje deterministický Turing˚ uv stroj M takový, ˇze pro kaˇzdý vstup délky n zastav´ı pr´ avˇe po f (n) kroc´ıch. Definice 13. Funkce f : N → N je prostorovˇe konstruovateln´ a, pokud existuje deterministický Turing˚ uv stroj M takový, ˇze pro kaˇzdý vstup délky n zastav´ı s pr´ avˇe f (n) p´ askovými pol´ıˇcky nepr´ azdnými a bˇehem výpoˇctu ˇz´ adný jiný prostor na pracovn´ıch p´ ask´ ach nebyl pouˇzit. Lemma 2. Necht’ f1 + f2 a f2 jsou ˇcasovˇe konstruovatelné funkce a necht’ ∃ε > 0 ∃n0 ∀n > n0 : f1 (n) ≥ εf2 (n) + (1 + ε)n. Potom je f1 ˇcasovˇe konstruovateln´ a. D˚ ukaz. Metodou podobnou té z d˚ ukazu vˇety o lineárn´ım zrychlen´ı zrychl´ıme v´ ypoˇcet trvaj´ıc´ı f1 (n) + f2 (n) krok˚ u tak, aby trval pˇresnˇe f1 (n) krok˚ u. Mˇejme M1 deterministick´ y Turing˚ uv stroj pracuj´ıc´ı v ˇcase f1 (n) + f2 (n) a M2 deterministick´ y Turing˚ uv stroj pracuj´ıc´ı v ˇcase f2 (n) (z pˇredpoklad˚ u). Zkonstruujeme Mr , kter´ y pracuje v ˇcase f1 (n) pro skoro vˇsechny vstupy. Pr´ ace Mr je rozdˇelena do 4 fáz´ı. 1) V prvn´ı f´ azi pˇrep´ıˇse vstup na prvn´ı pracovn´ı pásku, na kterou jej zap´ıˇse r-kr´ at zahuˇstˇen´ y. Z´ aroveˇ n pˇrep´ıˇse (r − 6)-krát zahuˇstˇen´ y vstup také na 2. a 3. pracovn´ı p´ asku. Na to potˇrebuje n krok˚ u. Zároveˇ n ˇr´ıd´ıc´ı jednotka poˇc´ıt´ a modulo (r − 6) a po skonˇcen´ı pˇrepisu provede maximálnˇe r − 5 krok˚ u tak, aby celkov´ y poˇcet krok˚ u prvn´ı fáze byl dˇeliteln´ y (r − 6). Tedy dost´ av´ ame n . (14) T1 = (r − 6) · r−6 2) V druhé f´ azi Mr soubˇeˇznˇe simuluje stroj M1 na prvn´ı pásce a M2 na ˇ druhé p´ asce. Sest krok˚ u (jedna sekvence) stroje Mr odsimuluje r krok˚ u M1 a (r − 6) krok˚ u M2 . Zvol´ıme r dostateˇcnˇe velké, aby simulace stroje M2 skonˇcila dˇr´ıve, a to po df2 (n)/(r − 6)e sekvenc´ıch stroje Mr . Potˇrebujeme zajistit: f1 (n) + f2 (n) f2 (n) > r r−6 12

(15)

Pˇribliˇznˇe: (f1 (n) + f2 (n)) · (r − 6) > r · f2 (n) f1 (n) · (r − 6) ≥ 6f2 (n) 6f2 (n) r−6≥ f1 (n) 6 f1 (n) ≥ f2 (n) r−6 6(f1 (n) + f2 (n)) r≥ f1 (n) V okamˇziku, kdy M2 skonˇc´ı, zastav´ı stroj M 0 simulaci. Pomoc´ı ˇr´ıd´ıc´ı jednotky si poˇc´ıtal modulo (r − 6). V pˇr´ıpadˇe, ˇze f2 (n) nebylo násobkem (r − 6), provede stroj M 0 pˇresnˇe (r − 6) df2 (n)/(r − 6)e − f2 (n) prázdn´ ych krok˚ u, ˇc´ımˇz se trv´ an´ı druhé fáze dopln´ı na nejbliˇzˇs´ı vˇetˇs´ı násobek (r − 6). Z uvedeného dost´ av´ ame, ˇze poˇcet krok˚ u stroje M 0 potˇrebn´ y pro druhou f´ azi je f2 (n) f2 (n) + (r − 6) − f2 (n) = T2 = 6 · r−6 r−6 f2 (n) =r· − f2 (n) r−6

(16)

Z pˇredpoklad˚ u plyne, ˇze T2 je pro skoro vˇsechna n kladné. Je zˇrejmé, ˇze bˇehem této fáze bylo odsimulováno r · df2 (n)/(r − 6)e krok˚ u stroje M1 , nebot’ bˇehem kaˇzdé ze sekvenc´ı bylo odsimulováno r krok˚ u stroje M1 (kroky na doplnˇen´ı na násobek (r − 6) jsou prázdné, M1 se v nich nesimuluje). 3) V tˇret´ı f´ azi pokraˇcuje M 0 simulac´ı M1 stejn´ ym tempem jako pˇredt´ım (tedy 6 krok˚ u za sekvenci odsimuluje r krok˚ u p˚ uvopdn´ıho stroje). Tato fáze bude trvat dn/(r − 6)e + 1 sekvenc´ı, coˇz zajist´ıme tak, ˇze po kaˇzdé sekvenci pˇreˇcteme jeden symbol z pˇrepsaného komprimovaného vstupu (viz fáze 1). ˇ pro tuto f´ Cas azi je n T3 = 6 · +1 (17) r−6 a je odsimulov´ ano r · (dn/(r − 6)e + 1) krok˚ u stroje M1 . Pˇri srovn´ an´ı ˇcasu v´ ypoˇctu stroje M1 s dosud odsimulovan´ ym poˇctem je zˇrejmé, ˇze pro dostateˇcnˇe velké hodnoty r tato simulace pro skoro vˇsechna n nedos´ ahne celého v´ ypoˇctu M1 . 4) Ve ˇctvrté f´ azi pokraˇcuje M 0 real-time simulac´ı stroje M1 (jeden krok M 0 odpov´ıd´ a jednomu kromu M1 ), dokud se M1 nezastav´ı. Na závˇer provede ˇ na tuto fázi je zb´ M 0 r − 6 pr´ azdn´ ych krok˚ u a zastav´ı se. Cas yvaj´ıc´ı ˇcas stroje M1 plus r − 6, z toho dostáváme: f2 (n) n T4 = f1 (n) + f2 (n) − r · −r· + 1 + r − 6 (18) r−6 r−6 13

Hodnota r mus´ı b´ yt dost velká, aby tento v´ yraz byl pro skoro vˇsechna n kladn´ y. Existence takového r plyne z pˇredpoklad˚ u tvrzen´ı. Souˇctem T1 , T2 , T3 , T4 dostáváme, ˇze ˇcas pro bˇeh stroje M 0 je pˇresnˇe f1 (n) pro skoro vˇsechna n. Vˇ eta 10 (O ekvivalenci definic 10 a 12). Necht’ f : N → N je funkce takov´ a, ˇze ∃ε > 0 ∃n0 ∀n ≥ n0 : f (n) ≥ (1 + ε)n. Potom f je ˇcasovˇe konstruovateln´ a pr´ avˇe, kdyˇz f je vyˇc´ısliteln´ a v ˇcase O(f ). D˚ ukaz. Implikace zleva doprava je zˇremá. Stroj dokazuj´ıc´ı ˇcasovou konstruovatelnost modifikujeme tak, ˇze na novou pásku v kaˇzdém kroku nap´ıˇse jeden symbol. Nov´ y stroj vyˇc´ısluje f v ˇcase O(f ). Nyn´ı opaˇcn´ a implikace. Necht’ M je deterministick´ y Turing˚ uv stroj, kter´ y vyˇc´ısluje f v ˇcase O(f ). Oznaˇcme g(n) poˇcet krok˚ u stroje M nad vstupem 1n (zˇrejmˇe ∃c > 0 : g(n) ≤ cf (n)). 1) g je ˇcasovˇe konstruovatelná (d´ıky existenci stroje M ). 2) g + f je ˇcasovˇe konstruovatelná. Modifikuji M tak, aby poˇc´ıtal v´ ystup na zvl´ aˇstn´ı p´ asku a po skonˇcen´ı v´ ypoˇctu pˇrejel na zaˇcátek této pásky. Doba v´ ypoˇctu je g(n), délka v´ ystupu je f (n). 3) ∃ε > 0 ∃n0 ∀n > n0 : f (n) ≥ εg(n) + (1 + ε)n Zvol´ıme: a) ε1 , jehoˇz existenci nám zajiˇst’uj´ı pˇredpoklady vˇety: ∃n0 ∀n ≥ n0 : 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 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.

(19)

Funkce f a g splˇ nuj´ı pˇredpoklady lemmatu 2 a tedy f (n) je ˇcasovˇe konstruovateln´ a. Vˇ eta 11 (O ekvivalenci definic 11 a 13). Funkce f : N → N je prostorovˇe kontruovateln´ a pr´ avˇe, kdyˇz f je vyˇc´ısliteln´ a v prostoru O(f ). D˚ ukaz. Implikace zleva doprava je zˇremá. Stroj dokazuj´ıc´ı prostorovou konstruovatelnost modifikujeme tak, ˇze na novou v´ ystupn´ı pásku v kaˇzdém kroku, ve kterém bylo zabr´ ano nové pol´ıˇcko na pracovn´ı pásce, nap´ıˇse jeden symbol. Stroj mus´ı rozliˇsovat p˚ uvodn´ı a nov´ y symbol pro prázdné pol´ıˇcko. Nov´ y stroj vyˇc´ısluje f v protoru O(f ). Necht’ M je k-p´ askov´ y deterministick´ y Turing˚ uv stroj vyˇc´ısluj´ıc´ı f (n) v prostoru c·f (n). Podle vˇety o line´ arn´ı kompresi zkonstruujeme k-páskov´ y stroj M 0 , 0 kter´ y vyˇc´ısluje f (n) v prostoru pˇresnˇe f (n). Uvˇedomte si, ˇze M vyˇc´ısluje f (n), tedy mus´ı pracovat v prostoru alespoˇ n f (n). Stroj M 0 dále pˇrevedeme podle vˇety o redukci poˇctu p´ asek na jednopáskov´ y stroj M 00 , kter´ y jiˇz dokazuje prostorovou konstruovatelnost funkce f . 14

D˚ usledek 5. Kaˇzd´ a ˇcasovˇe konstruovateln´ a funkce je prostorovˇe konstruovateln´ a. D˚ ukaz. Funkce f je ˇcasovˇe konstruovatelná, tedy f je vyˇc´ıslitelná v ˇcase O(f ), t´ım sp´ıˇse je f vyˇc´ısliteln´ a v protoru O(f ) a tedy dostáváme dle pˇredchoz´ı vˇety, ˇze f je prostorovˇe konstruovatelná. Vˇ eta 12 (O rychlosti r˚ ustu ˇ casovˇ e konstruovateln´ ych funkc´ı). Necht’ f : N → N je rekurzivn´ı funkce. Potom existuje ˇcasovˇe konstruovateln´ a funkce g : N → N takov´ a, ˇze ∀n g(n) > f (n). D˚ ukaz. V´ıme, ˇze f je rekurzivn´ı, tedy existuje deterministick´ y Turing˚ uv stroj M , kter´ y pro vstup 1n vyd´ a v´ ystup 1f (n) . Definujeme g(n) jako poˇcet krok˚ u stroje M nad vstupem 1n zvˇetˇsen´ y o jedna. Je zˇrejmé, ˇze f (n) < g(n) a g(n) je ˇcasovˇe konstruovatelná (samotn´ y M tuto vlastnost pˇr´ımo dokazuje).

5

Hierarchie tˇ r´ıd sloˇ zitosti

5.1

ˇ Casov´ a hierarchie

Definice 14. Jazyk L je rekurzivn´ı, jestliˇze existuje deterministický Turing˚ uv stroj M , který se pro kaˇzdý vstup x zastav´ı a který pˇrijme pr´ avˇe, kdyˇz x ∈ L. Vˇ eta 13 (O otevˇ renosti ˇ casov´ e hierarchie shora). Necht’ T : N → N je rekurzivn´ı funkce. Potom existuje rekurzivn´ı jazyk L takový, ˇze L ∈ / DT IM E(T (n)). D˚ ukaz. Uk´ aˇzeme konstrukci takového jazyka. Nejprve oˇc´ıslujeme vˇsechny deterministické Turingovy stroje G¨ odelov´ ymi ˇc´ısly a také oˇc´ıslujeme vˇsechny ˇretˇezce nad {0, 1}. Oˇc´ıslov´ an´ı provedeme systematicky, aby bylo moˇzno tyto ˇretˇezce generovat. Definujeme L = {xi : Mi nepˇrij´ımá xi v ˇcase T (|xi |)}. Ukaˇzme nejprve, ˇze L je rekurzivn´ı. 1) Pro vstup w ∈ {0, 1}∗ délky n generujeme na pomocnou pásku poˇc´ıtadlo T (n) (lze, nebot’ T se vˇzdy zastav´ı). 2) Postupn´ ym generov´ an´ım najdeme i takové, ˇze w = xi . To lze v koneˇcném poˇctu krok˚ u. 3) Uvaˇzuji i jako G¨ odelovo ˇc´ıslo nˇejakého stroje. 4) Provedu simulaci stroje Mi nad xi po T (n) krok˚ u. Slovo xi pˇrijmu v n´ asleduj´ıc´ıch pˇr´ıpadech: a) Mi zastav´ı po ménˇe neˇz T (|xi |) + 1 kroc´ıch a odm´ıtne; b) Mi bˇeˇz´ı v´ıce jak T (|xi |) + 1 krok˚ u. Nyn´ı ukaˇzme, ˇze L ∈ / DT IM E(T (n)). Pro spor pˇredpokládejme, ˇze uvedené plat´ı, tedy L ∈ DT IM E(T (n)). Potom existuje deterministick´ y Turin˚ uv stroj M , kter´ y rozpozn´ a L v ˇcase T (n). Necht’ i je jeho Gödelovo ˇc´ıslo (Mi = M ).

15

1) xi ∈ L, potom Mi pˇrij´ımá xi v ˇcase T (|xi |), z ˇcehoˇz plyne, ˇze xi nen´ı pˇrijmuto strojem M , ale M = Mi . Spor. 2) xi ∈ / L, potom Mi nepˇrij´ımá xi v ˇcase T (|xi |), z ˇcehoˇz plyne, ˇze xi je pˇrijmuto strojem M , ale M = Mi . Spor. T´ım je vˇeta dok´ az´ ana. D˚ usledek 6 (Nekoneˇ cn´ aˇ casov´ a hierarchie). Existuje nekoneˇcn´ a posloupnost funkc´ı T1 , T2 , . . . takov´ a, ˇze DT IM E(T1 (n)) DT IM E(T2 (n)) . . .. D˚ ukaz. Necht’ je hiearchie vybudována aˇz po DT IM E(Ti (n)). Z pˇredchoz´ı vˇety v´ıme, ˇze existuje rekurzivn´ı jazyk L takov´ y, ˇze pro nˇej plat´ı L ∈ / DT IM E(Ti (n)). Definujeme funkci Ti+1 takovou, aby majorizovala funkci Ti a z´ aroveˇ n i dobu v´ ypoˇctu stroje, kter´ y pˇrij´ımá jazyk L (necht’ je tento v´ ypoˇcet omezen funkc´ı T 0 ). T´ım budeme m´ıt zaruˇceno, ˇze DT IM E(Ti (n)) ⊆ DT IM E(Ti+1 (n)) a také L ∈ DT IM E(Ti+1 (n)). Z faktu, ˇze L ∈ / DT IM E(Ti (n)) dostáváme ostrou inkluzi. K tomu staˇc´ı ale poloˇzit Ti+1 = max{Ti (n), T 0 (n)}.

5.2

Prostorov´ a hierarchie

Vˇ eta 14 (O otevˇ renosti prostorov´ e hierarchie shora). Necht’ S : N → N je rekurzivn´ı funkce. Potom existuje rekurzivn´ı jazyk L takový, ˇze L ∈ / DSP ACE(S(n)). D˚ ukaz. D˚ ukaz je analogick´ y d˚ ukazu ˇcasové verze této vˇety. Definujeme L = {xi : Mi nepˇrij´ımá xi v prostoru S(|xi |)}. Rozd´ıl oproti ˇcasové verzi je v tom, ˇze stroj Mi nyn´ı m˚ uˇze odm´ıtnout koneˇcn´ ym v´ ypoˇctem ve vymezeném prostoru, pˇrekroˇcen´ım vymezeného prostoru nebo vstupem do nekoneˇcné smyˇcky uvnitˇr vymezeného prostoru. To lze ale oˇsetˇrit odhadem poˇctu konfigurac´ı (na omezeném prostoru existuje koneˇcnˇe mnoho konfigurac´ı) a pˇrid´ an´ım bud´ıku, kter´ y stroj zastav´ı v okamˇziku, kdy poˇcet krok˚ u bude vyˇsˇs´ı neˇz poˇcet konfigurac´ı. D˚ usledek 7 (Nekoneˇ cn´ a prostorov´ a hierarchie). Existuje nekoneˇcn´ a posloupnost funkc´ı S1 , S2 , . . . takov´ a, ˇze DSP ACE(S1 (n)) DSP ACE(S2 (n)) . . .. D˚ ukaz. Analogicky jako v pˇr´ıpadˇe ˇcasové hierarchie.

5.3

Vˇ ety o hierarchii

Vˇ eta 15 (O prostorov´ e hierarchii). Necht’ S1 : N → N a S2 : N → N jsou funkce takové, ˇze S2 ∈ ω(S1 ) a S2 je prostorovˇe konstruovateln´ a. Potom existuje jazyk L takový, ˇze L ∈ DSP ACE(S2 (n))\DSP ACE(S1 (n)).

16

D˚ ukaz. Naˇs´ım c´ılem bude zkonstruovat deterministick´ y Turing˚ uv stroj pracuj´ıc´ı v prostoru S2 (n), kter´ y se od kaˇzdého stroje pracuj´ıc´ıho v prostoru S1 (n) liˇs´ı alespoˇ n na jednom vstupu. Prefixovˇe si oˇc´ıslujeme vˇsechny jednopáskové stroje nad abecedou {0, 1}. Pop´ıˇseme pr´ aci M na vstupu w, |w| = n. V prvn´ı fázi si M oznaˇc´ı S2 (n) bunˇek na pracovn´ı p´ asce. Dojde-li v dalˇs´ıch fáz´ıch k opuˇstˇen´ı vymezeného prostoru, stroj se zastav´ı a odm´ıtne. V druhé f´ azi M simuluje Mw a pˇrijme, pokud Mw odm´ıtne w a neopust´ı pˇritom vymezen´ y prostor. Plat´ı L ∈ DSP ACE(S2 (n)) a L ∈ / DSP ACE(S1 (n)). Prvn´ı vztah je zˇrejm´ y, uk´ aˇzeme druh´ y (sporem). Necht’ pro spor L ∈ DSP ACE(S1 (n)), potom existuje deterministick´ y Turing˚ uv stroj M 0 takov´ y, ˇze L(M 0 ) = L(M ). M 0 má velikost pracovn´ı abecedy t a pracuje v prostoru S1 (n). Bez u ´jmy na obecnosti m˚ uˇzeme pˇredpokládat, ˇze M 0 se vˇzdy zastav´ı a je jednopáskov´ y. Kdyby M 0 nemˇel poˇzadované vlastnosti, lze jej modifiovat tak, ˇze bude schopen rozpoznat nekoneˇcn´ y cyklus (pomoc´ı horn´ıho odhadu na poˇcet konfigurac´ı). Poˇcet moˇzn´ ych konfigurac´ı je s · (n + 1) · S1 (n) · tS1 (n) , kde s je poˇcet stav˚ u a t je poˇcet p´ askov´ ych symbol˚ u. Tento poˇcet lze odhadnout jako cS1 (n) pro vhodnou konstantu c. Uloˇz´ıme-li si toto ˇc´ıslo v základu c, vejde se do prostoru S1 (n). Tedy stroj si bude na nové pásce poˇc´ıtat kroky a pˇresáhne-li poˇcet krok˚ u poˇcet moˇzn´ ych konfigurac´ı, odm´ıtne. Podle vˇety o redukci poˇctu pásek dot´ av´ ame jednop´ askov´ y stroj s poˇzadovan´ ymi vlastnostmi. K simulaci M 0 potˇrebujeme dlog2 te · S1 (n) prostoru. Vzhledem k volbˇe prefixového ˇc´ıslov´ an´ı stroj˚ u m˚ uˇzeme zvolit w tak, ˇze kóduje stejn´ y stroj, ale souˇcasnˇe plat´ı dlog2 te · S1 (|w|) ≤ S2 (|w|). To jistˇe lze, nebot’ S2 roste rychleji neˇz S1 . Pakliˇze stroj M 0 pˇrij´ım´ a w, potom L ∈ L(M 0 ) = L(M ), ale dle definice stroje M plat´ı w ∈ / L(M ). Jestliˇze naopak M 0 odm´ıtne w, potom w ∈ / L(M 0 ) = 0 L(M ), ale M odm´ıtne w ve vymezeném prostoru, tedy podle definice M plat´ı w ∈ L(M ). V obou pˇr´ıpadech dostáváme spor. Tedy L ∈ / DSP ACE(S1 (n)). Vˇ eta 16 (O ˇ casov´ e hierarchii). Necht’ T1 : N → N a T2 : N → N jsou funkce takové, ˇze T2 ∈ ω(T1 · log T1 ) a T2 je ˇcasovˇe konstruovateln´ a. Potom existuje jazyk L takový, ˇze L ∈ DT IM E(T2 (n)) \ DT IM E(T1 (n)). D˚ ukaz. Naˇs´ım c´ılem bude zkonstruovat deterministick´ y Turing˚ uv stroj pracuj´ıc´ı v ˇcase T2 (n), kter´ y se od kaˇzdého stroje pracuj´ıc´ıho v ˇcase T1 (n) liˇs´ı alespoˇ n na jednom vstupu. Prefixovˇe si oˇc´ıslujeme vˇsechny dvoupáskové stroje. Pr´ ace M na vstupu w, kde |w| = n. 1) Na dvou p´ ask´ ach simuluje práci stroje Mw . 2) Na dalˇs´ıch p´ ask´ ach stopuje T2 (n) krok˚ u. To jistˇe lze, nebot’ T2 je ˇcasovˇe konstruovateln´ a. 3) M pˇrijme, pokud simulace skonˇc´ı nejv´ yˇse v T2 (n) kroc´ıch odm´ıtnut´ım w. Oznaˇcme L = L(M ). Uk´ aˇzeme, ˇze L ∈ DT IM E(T2 (n)) \ DT IM E(T1 (n)).

17

Pouˇzit´ım ˇc´ıtaˇce krok˚ u m´ ame zajiˇstˇeno, ˇze L ∈ DT IM E(T2 (n)). Ukaˇzme tedy, ˇze L ∈ / DT IM E(T1 (n)). D˚ ukaz budeme dˇelat sporem. Pˇredpokládejme, ˇze existuje stroj M 0 takov´ y, ˇze M 0 pˇrij´ım´ a L v ˇcase T1 (n). Potom existuje podle vˇety o redukci poˇctu pásek stroj M 00 , kter´ y m´ a dvˇe p´ asky a pˇrij´ımá L v ˇcase T1 (n)·log2 T1 (n) Necht’ p´ askov´ a abeceda stroje M 00 má t symbol˚ u. M bude na simulaci M 00 potˇrebovat c(t)·T1 (n)·log2 T1 (n), kde c(t) je konstanta závislá na t. Necht’ v je G¨ odelovo ˇc´ıslo stroje M 00 . Zvol´ıme w = αv, kde α je prefix takové délky, aby platilo c(t)·T1 (|w|)·log T1 (|w|)) ≤ T2 (|w|). Taková délka prefixu existuje z pˇredpoklad˚ u vˇety. Nyn´ı m´ a M dostatek ˇcasu k simulaci M 00 (trik byl v tom, ˇze jsme právˇe zvˇetˇsili vstup stroje, pˇrestoˇze stroj bude poˇc´ıtat totéˇz, pouze na to bude m´ıt v´ıce ˇcasu). Rozliˇsme dva pˇr´ıpady: 1) Mw (= M 00 ) pˇrij´ım´ a w, potom a) w ∈ L, protoˇze L = L(M ) = L(M 00 ), b) w ∈ / L, protoˇze M odm´ıtne w, kdyˇz jej Mw pˇrijme. 2) Mw odm´ıt´ a w, potom a) w ∈ / L, protoˇze L = L(M ) = L(M 00 ), b) w ∈ L, protoˇze M pˇrijme w, kdyˇz jej Mw odm´ıtne. Spor s pˇredpokladem, ˇze L ∈ DT IM E(T1 (n)). Vˇeta je dokázána.

5.4

Vˇ eta o vtaz´ıch mezi tˇ r´ıdami sloˇ zitosti

Vˇ eta 17 (O vztaz´ıch mezi tˇ r´ıdami sloˇ zitosti). a) DT IM E(f (n)) ⊆ N T IM E(f (n)) DSP ACE(f (n)) ⊆ N SP ACE(f (n)) b) DT IM E(f (n)) ⊆ DSP ACE(f (n)) c) L ∈ DSP ACE(f (n)) a f (n) ≥ log2 n, potom ∃cL : L ∈ DT IM E(cL f (n) ), kde cL je konstanta z´ avisl´ a na L d) L ∈ N T IM E(f (n)), potom ∃cL : L ∈ DT IM E(cL f (n) ), kde cL je konstanta z´ avisl´ a na L D˚ ukaz. a) Trivi´ alnˇe plat´ı. b) Z vˇet o line´ arn´ı kompresi a o redukci poˇctu pásek. c) Necht’ M je jednop´ askov´ y stroj dokazuj´ıc´ı L ∈ DSP ACE(f (n)). Poˇcet jeho konfigurac´ı je omezen s · (n + 1) · (f (n) + 1) · tf (n) ≤ df (n) , pro vhodné d (s je poˇcet stav˚ u, t je poˇcet páskov´ ych symbol˚ u). Zkonstruujeme M 0 , kter´ y simuluje stroj M a nejv´ yˇse po df (n) kroc´ıch se zastav´ı. (Potˇrebujeme pˇredpoklad ˇcasové konstruovatelnosti funkce f ). 18

d) Necht’ M je nedeterministick´ y k-páskov´ y stroj, kter´ y dokazuje, ˇze L ∈ N T IM E(f (n)). Poˇcet jeho konfigurac´ı je omezen s · (f (n) + 1)k · tk·f (n) ≤ df (n) , pro vhodné d (s je poˇcet stav˚ u, t je poˇcet páskov´ ych symbol˚ u). Zkonstruujeme deterministick´ y M 0 takov´ y, ˇze vygeneruje seznam vˇsech konfigurac´ı dosaˇziteln´ ych z poˇcáteˇcn´ı konfigurace (napˇr´ıklad pr˚ uchodem stromu v´ ypoˇctu M ). Generov´ an´ı seznamu lze provést v ˇcase kvadratickém vzhledem k délce v´ ysledného seznamu. Tato délka je omezena souˇcinem poˇctu konfigurac´ı a délky z´ apisu jedné konfigurace. Tedy l ≤ df (n) ·(k ·f (n)+1+k ·log f (n)) ≤ f (n) c . Tedy poˇcet krok˚ u je omezen c2·f (n) .

Vˇ eta 18 (Rozˇ s´ıˇ ren´ı vˇ ety o vztaz´ıch). b’) N T IM E(f (n)) ⊆ N SP ACE(f (n)) c’) L ∈ N SP ACE(f (n)) a f (n) ≥ log2 n, potom ∃cL : L ∈ DT IM E(cL f (n) ), kde cL je konstanta z´ avisl´ a na L D˚ ukaz. b’) Na pomocné p´ asce k´ odujeme aktuáln´ı pr˚ uchod stromem v´ ypoˇctu. Jednotlivé k´ ody m˚ uˇzeme systematicky generovat, (1, 1, . . . , 1) aˇz (r, r, . . . , r), kde r je maxim´ aln´ı stupeˇ n vˇetven´ı. Vlastn´ı simulaci jedné vˇetve v´ ypoˇctu lze provést v prostoru f (n), na uloˇzen´ı informac´ı o pr˚ uchodu potˇrebujeme log r · f (n). Simulaci tedy lze provést v prostoru log r · f (n). c’) Poˇcet moˇzn´ ych konfigurac´ı na omezeném prostoru je df (n) , kde d je konstanta. Uvaˇzujme graf G vˇsech konfigurac´ı. Hrana (a, b) znamená, ˇze konfigurace b je z konfigurace a dosaˇzitelná v jednom kroku. |V (G)| ≤ df (n)

(20)

|E(G)| ≤ c · df (n)

Omezen´ı poˇctu hran plyne z faktu, ˇze zmˇeny v konfiguraci po jednom kroku jsou pouze lok´ aln´ı, tedy kaˇzdá konfigurace má pouze konstatn´ı poˇcet soused˚ u. Na pracovn´ı p´ asku vygenerujeme seznam vˇsech konfigurac´ı, to zabere ˇcas df (n) · q · f (n), kde q je konstanta. Deterministick´ y stroj potom pracuje tak, ˇze procház´ı graf G do hloubky a na pomocné p´ asce si zaznamenává, které vrcholy jiˇz navˇst´ıvil. Na zjiˇstˇen´ı, kter´ y z vrchol˚ u byl jiˇz navˇst´ıven, potˇrebuje ˇcas u ´mˇern´ y délce dosavadn´ıho v´ ypoˇctu. Stroj tedy pracuje v ˇcase poˇcet vrchol˚ u · zkop´ırov´ an´ı pˇr´ısluˇsné konfigurace na pracovn´ı p´ asku. T (n) = |V (G)|qf (n) + |E(G)df (n) qf (n)| = f (n)

= qf (n)(df (n) + kdf (n) df (n) ) ≤ h(d2 )f (n) ≤ cL 19

(21)

Najde-li stroj pˇri pr˚ uchodu grafem pˇrij´ımaj´ıc´ı konfiguraci, je tato dosaˇziteln´ a z inici´ aln´ı konfigurace a stroj pˇrijme.

5.5

Saviˇ cova vˇ eta

Vˇ eta 19 (Saviˇ cova). Necht’ S : N → N je prostorovˇe konstruovateln´ a funkce, pro kterou plat´ı S(n) ≥ log2 n. Potom N SP ACE(S(n)) ⊆ DSP ACE(S 2 (n)). D˚ ukaz. Necht’ M1 je nedeterministick´ y Turing˚ uv stroj pˇrij´ımaj´ıc´ı jazyk L v prostoru S(n), potom existuje konstanta cL taková, ˇze M1 má nejv´ yˇse cL S(n) konfigurac´ı. Pokud M1 pˇrij´ım´ a w, pak existuje posloupnost nejv´ yˇse cL S(n) = 2S(n)·log cL krok˚ u konˇc´ıc´ı pˇrijet´ım w. Oznaˇcme I1 →i I2 , pokud lze z konfigurace I1 pˇrej´ıt do I2 za ménˇe neˇz nebo pˇresnˇe 2i krok˚ u. Test staˇc´ı provádˇet pro i ≤ S(n) · log cL = m · S(n). Popiˇsme zp˚ usob rozhodov´ an´ı, ˇze I1 →i I2 . procedure TEST(I1 , I2 , i) if i = 0 then if (I1 = I2 ) or (I1 → I2 ) then return true else return false else for ∀ konfigurace I 0 ∈ K do if TEST(I1 , I 0 , i − 1) and TEST(I 0 , I2 , i − 1) then return true enddo return false end TEST Kolik m´ısta bude potˇreba 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ˇcet stav˚ u) • pozice vstupn´ı hlavy - log2 n ≤ S(n) • pozice pracovn´ı hlavy - log2 n ≤ S(n) • obsah pracovn´ı p´ asky - c0 · S(n), kde c0 = log2 t, t je poˇcet páskov´ ych symbol˚ u. Celkem je tedy potˇreba na zapsán´ı jedné konfigurace O(S(n)) prostoru. Parametr i lze zapsat v prostoru m · log S(n). Tedy prostor potˇrebn´ y pro jednu kopii procedury TEST je O(S(n)). Cel´ a simulace potom prob´ıhá tak, ˇze pro vˇsechny pˇrij´ımaj´ıc´ı stavy Ij voláme proceduru T EST (I0 , Ij , m·S(n)) a jakmile alespoˇ n jednou odpov´ı kladnˇe, vstup pˇrijmeme. Pˇri simulaci funguje pracovn´ı páska jako zásobn´ık na uloˇzen´ı parametr˚ u procedur TEST. V kaˇzd´ y okamˇzik je na zásobn´ıku O(S(n)) záznam˚ u. Deterministrick´ y stroj simuluj´ıc´ı M1 pracuje v prostoru O(S 2 (n)) a pˇrij´ımá jazyk L.

20

6

Pokroˇ cil´ e vˇ ety o tˇ r´ıd´ ach sloˇ zitosti

Lemma 3 (Translaˇ cn´ı). Necht’ S1 : N → N, S2 : N → N, f : N → N jsou prostorovˇe konstruovatelné a ∀n S2 (n) ≥ n, f (n) ≥ n. Potom N SP ACE(S1 (n)) ⊆ N SP ACE(S2 (n)) ⇒ N SP ACE(S1 (f (n))) ⊆ N SP ACE(S2 (f (n))). D˚ ukaz. Necht’ L1 ∈ N SP ACE(S1 (f (n))) a necht’ M1 je stroj, kter´ y to ukazuje. Sestroj´ıme jazyk L2 , kter´ y bude patˇrit do N SP ACE(S1 (n)). Necht’ L2 = {x$i |M1 pˇrij´ımá x v prostoru S1 (|x| + i)}. Zˇrejmˇe pro vˇsechna i takov´ a, ˇze |x| + i ≥ f (|x|), plat´ı x ∈ L1 ⇔ x$i ∈ L2 . Tento argument se naz´ yvá padding argument. Jde o to zvˇetˇsit délku slova bez pˇridán´ı nové informace, ˇc´ımˇz se stroji, kter´ y nad slovem pracuje, poskytne v´ıce prostoru (pˇr´ıpadnˇe ˇcasu). Zkonstruujeme M2 pˇrij´ımaj´ıc´ı L2 v prostoru S1 (n). Vstup: x$i Algoritmus: Stroj M2 nejprve oznaˇc´ı S1 (|x| + i) pol´ıˇcek na pracovn´ı pásce. D´ ale pokraˇcuje M2 simulac´ı stroje M1 a pˇrijme právˇe tehdy, pokud pˇrijme M1 a neopust´ı pˇritom vyznaˇcen´ y prostor. M2 zˇrejmˇe pracuje v prostoru S1 (n), tedy L ∈ N SP ACE(S1 (n)). Nav´ıc plat´ı x ∈ L1 ⇔ ∃i < f (|x|) : x$i ∈ L2 . Jin´ ymi slovy, existuje i takové, ˇze stroj M1 bude m´ıt dost prostoru pro pˇrijet´ı v prostoru S1 (|x| + i). Protoˇze podle pˇredpokladu plat´ı N SP ACE(S1 (n)) ⊆ N SP ACE(S2 (n)), dost´ av´ ame, ˇze existuje nedeterministick´ y Turing˚ uv stroj M3 , kter´ y pˇrij´ımá L2 v prostoru S2 (n). Nyn´ı sestroj´ıme M4 , kter´ y pˇrij´ımá L1 v prostoru S2 (f (n)). Popis pr´ ace M4 nad vstupem x. • Na p˚ ulené pracovn´ı p´ asce si oznaˇc´ı na horn´ı stopˇe f (|x|) pol´ıˇcek a potom si na doln´ı stopˇe oznaˇc´ı S2 (f (|x|)) pol´ıˇcek, pˇriˇcemˇz pouˇz´ıvá horn´ı stopu jako vstup. To lze, nebot’ f i S2 jsou prostorovˇe konstruovatelné. Protoˇze S2 (|x|) ≥ |x|, M4 zabere pˇresnˇe S2 (f (|x|)). • M4 simuluje M3 na vstupu x$i (pro dostateˇcnˇe velké i) s t´ım, ˇze pokud je vstupn´ı hlava M3 nad x, je hlava M4 na odpov´ıdaj´ıc´ı pozici, je-li vstupn´ı hlava M3 nad $i , tak vstupn´ı hlava M4 z˚ ustává na konci slova x a pozice hlavy je poˇc´ıt´ ana na zvl´ aˇstn´ı pracovn´ı pásce M4 . • Poˇc´ıtadlo nepust´ı vstupn´ı hlavu M3 za pozici, kdy uˇz by ˇc´ıtaˇc pˇretekl z prostoru S2 (f (|x|)), tedy i ≤ 2S2 (f (|x|)) , nebot’ v prostoru S2 (f (|x|)) m˚ uˇze poˇc´ıtadlo bin´ arnˇe poˇc´ıtat aˇz do 2S2 (f (|x|)) . • M4 pˇrijme x pr´ avˇe, kdyˇz M3 pˇrijme. Plat´ı: x ∈ L1 ⇔ ∃i < f (|x|) : x$i ∈ L2 = L(M3 ). V´ıme ale, ˇze S2 (n) ≥ n, tedy S2 (f (|x|)) ≥ f (|x|), z ˇcehoˇz dostáváme 2S2 (f (|x|)) ≥ f (|x|). Jiˇz dˇr´ıve jsme uk´ azali, ˇze staˇc´ı i ≤ f (|x|), tedy naˇse simulace umoˇzn ˇuje zkouˇset dostateˇcnˇe velk´ a i. Tedy i je dostateˇcnˇe velké. Na z´ avˇer dost´ av´ ame x ∈ L(M4 ) ⇔ x$i ∈ L(M3 ) ⇔ x ∈ L1 a tedy L1 ∈ N SP ACE(S2 (f (n))). 21

Vˇ eta 20 (O nedeterministick´ e prostorov´ e hierarchii). Necht’ ε > 0 a r ≥ 1, potom N SP ACE(nr ) N SP ACE(nr+ε ). D˚ ukaz. D´ıky hustotˇe racion´ aln´ıch ˇc´ısel v´ıme, ˇze ∀r ∀ε ∃s, t ∈ N : r ≤

s s+1 < ≤ r + ε. t t

(22)

Uk´ aˇzeme, ˇze N SP ACE(ns/t ) N SP ACE(n(s+1)/t ). D˚ ukaz provedeme (s+1)/t sporem. Necht’ tedy N SP ACE(n ) ⊆ N SP ACE(ns/t ). Pouˇzijeme (s + 1)kr´ at translaˇcn´ı lemma, postupnˇe pro funkce f (n) = n(s+i)t pro i = 0, . . . , s. i=0 i=1 i=2 .. . i=s−1 i=s

2

N SP ACE(n(s+1)s ) ⊆ N SP ACE(ns ) N SP ACE(n

(s+1)(s+1)

N SP ACE(n

(s+1)(s+2)

(23)

) ⊆ N SP ACE(n

s(s+1)

)

) ⊆ N SP ACE(n

s(s+2)

)

N SP ACE(n(s+1)(2s−1) ) ⊆ N SP ACE(ns(2s−1) ) N SP ACE(n(s+1)(2s) ) ⊆ N SP ACE(ns(2s) )

Prav´ a strana kaˇzdé inkluze je vnoˇrená do levé strany inkluze pro i o jedniˇcku menˇs´ı. Dostaneme prost´ ym porovnán´ım exponent˚ u u n. Zˇretˇezen´ım dostaneme 2

2

N SP ACE(n(s+1)(2s) ) ⊆ N SP ACE(ns ) ⊆ DSP ACE(n2s ) DSP ACE(n

2s2 +2s

) ⊆ N SP ACE(n

(s+1)(2s)

(24) ).

(25)

Uvedené schéma vede ke sporu, nebot’ vpravo i vlevo je stejná tˇr´ıda a uprostˇred je ostr´ a inkluze. Definice 15. Tvrzen´ı parametrizované ˇc´ıslem n je pravdivé skoro vˇsude, plat´ı-li na vˇsech kromˇe koneˇcnˇe mnoha n. Tvrzen´ı parametrizované ˇc´ıslem n je pravdivé nekoneˇcnˇe ˇcasto, plat´ı-li na nekoneˇcnˇe mnoha n. Lemma 4. Necht’ L je jazyk pˇrij´ımaný deterministickým Turingovým strojem s prostorovou sloˇzitost´ı S(n) skoro vˇsude. Potom L je pˇrij´ımaný jiným strojem M 0 s prostorovou sloˇzitost´ı S(n). D˚ ukaz. Koneˇcnˇe mnoho v´ yjimek, kde v´ ypoˇcet pˇresáhne S(n) oˇsetˇr´ıme pomoc´ı tabulky. Takov´ y stroj ale nelze efektivnˇe sestrojit, protoˇze nedokáˇzeme vyj´ımky identifikovat. Lemma 5. Necht’ je d´ an deterministický Turing˚ uv stroj M , délka vstupu n a ˇc´ıslo m. Existuje algoritmus zjiˇst’uj´ıc´ı, zda m je maxim´ aln´ı poˇcet pouˇzitých bunˇek na pracovn´ıch p´ ask´ ach pˇri pr´ aci M na vstupech délky n. Algoritmus vˇzdy skonˇc´ı. D˚ ukaz. Staˇc´ı simulovat v´ ypoˇcet M a poˇc´ıtat kroky pro detekci pˇr´ıpadn´ ych nekoneˇcn´ ych smyˇcek (pˇrekroˇcen´ı poˇctu moˇzn´ ych konfigurac´ı). 22

6.1

Vˇ eta o mezer´ ach (Borodin)

Vˇ eta 21 (Borodinova, o mezer´ ach). Necht’ g(n) ≥ n je rekurzivn´ı funkce. Potom existuje rekurzivn´ı funkce S(n) takov´ a, ˇze DSP ACE(S(n)) = DSP ACE(g(S(n))) D˚ ukaz. Necht’ M1 , M2 , . . . je oˇc´ıslován´ı vˇsech deterministick´ ych stroj˚ u. Oznaˇcme Si (n) = maximum pouˇzit´ ych bunˇek stroje Mi na vstupu délky n. Pokud se Mi vˇzdy zastav´ı, je Si (n) jeho prostorová sloˇzitost. Pokud se Mi na nˇejakém vstupu délky n nezastav´ı, je Si (n) nedefinováno (respektive rovno +∞). Pozn´ amka: zjistit, zda Si (n) = +∞ nelze, ale pro libovolné pevnˇe dané m lze zjistit, zda Si (n) ≤ m (viz lemma 5). Zkonstruujeme funkci S(n) takovou, ˇze pro vˇsechna k bud’ Sk (n) ≤ S(n) skoro vˇsude

(26)

Sk (n) > g(S(n)) nekoneˇcnˇe ˇcasto.

(27)

nebo

Uvedené nerovnosti poˇzadujeme, abychom zajistili: ∀k : L(Mk ) ∈ DSP ACE(S(n)) ⇔ L(Mk ) ∈ DSP ACE(g(S(n)))

(28)

Stroj Mk splˇ nuj´ıc´ı 26 lze pomoc´ı koneˇcnˇe mnoha v´ yjimek zmˇenit tak, aby nerovnost platila vˇsude podle lemma 4, a stroj splˇ nuj´ıc´ı 27 naopak nelze pomoc´ı koneˇcnˇe mnoha v´ yjimek zmˇenit tak, aby platila opaˇcná nerovnost. Z 26 a 27 plyne, ˇze neexistuje k takové, ˇze S(n) < Sk (n) ≤ g(S(n)) skoro vˇsude. Stroj Mk by potom pˇrij´ımal jazyk, kter´ y nen´ı v DSP ACE(S(n)), ale je v DSP ACE(g(S(n))). Tomu se chceme v konstrukci vyhnout. Pop´ıˇseme nyn´ı konstrukci S(n) pro danou hodnotu n. Vezmeme M1 , . . . , Mn a zvol´ıme S(n) tak, ˇze ∀i, 1 ≤ i ≤ n : Si (n) ≤ S(n) nebo g(S(n)) < Si (n). V pˇr´ıpadˇe, ˇze jsou vˇsechna Si (n) koneˇcná, staˇc´ı vz´ıt za S(n) maximum, jak bylo ale jiˇz v´ yˇse uvedeno, nelze o koneˇcnosti Si (n) rozhodnout. Proto budeme problém ˇreˇsit ”z druhého konce”. Necht’ j = 1 a spoˇc´ıtejme g(j) (to lze, nebot’ g je rekurzivn´ı). Zjist´ıme, zda existuje stroj Mi takov´ y, ˇze j < Si (n) ≤ g(j) (to nám umoˇzn ˇuje lemma 5, nebot’ nyn´ı m´ ame horn´ı odhad na Si (n)). Jestliˇze takové Mi neexistuje, m˚ uˇzeme poloˇzit S(n) = j, nebot’ ˇzádn´ y stroj Mi nepoˇc´ıt´ a s protorovou sloˇzitost´ı mezi S(n) a g(S(n)). Jestliˇze takové Mi naopak existuje, vol´ıme j = Si (n). Pokraˇcujeme spoˇc´ıtán´ım g(j). Cyklus se zastav´ı nejv´ yˇse po n interac´ıch, nebot’ v kaˇzdé se jedno Si stane doln´ı hranic´ı intervalu. Takto konstruovan´ a funkce S(n) splˇ nuje podm´ınky 26 nebo 27, nebot’ pro dané k byl stroj Mk uvaˇzov´ an pro vˇsechna n ≥ k v mnoˇzinˇe M1 , . . . , Mn pˇri konstrukci S(n). Tedy Sk (n) nebylo v intervalu (S(n), g(S(n))]. Proto muselo b´ yt bud’ nekoneˇcnˇe mnohokr´ at nad t´ımto intervalem nebo skoro vˇzdy pod. Necht’ L ∈ DSP ACE(g(S(n))), potom existuje deterministick´ y Turing˚ uv stroj Mk rozpozn´ avaj´ıc´ı L v prostoru g(S(n)), tedy ∀n Sk (n) ≤ g(S(n)). Z konstrukce S(n) plyne, ˇze pro n > k plat´ı Sk (n) ≤ S(n) skoro vˇsude. Tedy Mk

23

pracuje v prostoru S(n) skoro vˇsude a podle lemma 4 existuje jin´ y stroj, kter´ y pˇrij´ım´ a L v prostoru S(n) vˇsude, tedy L ∈ DSP ACE(S(n)). M´ ame DSP ACE(g(S(n))) ⊆ DSP ACE(S(n)). Inkluze na druhou stranu je trivi´ aln´ı, tedy dost´ av´ ame rovnost a tvrzen´ı vˇety je dokázáno.

6.2

Vˇ eta o zrychlen´ı

Vˇ eta 22 (Bloomova, o zrychlen´ı - prostorov´ a verze). Necht’ r(n) je rekurzivn´ı funkce. Potom existuje rekurzivn´ı jazyk L takový, ˇze pro kaˇzdý deterministický Turing˚ uv stroj Mi rozpozn´ avaj´ıc´ı L v prostoru Si (n) existuje deterministický Turing˚ uv stroj Mj rozpozn´ avaj´ıc´ı L v prostoru Sj (n), kde r(Sj (n)) ≤ Si (n) skoro vˇsude. Neˇz pˇristoup´ıme k samotnému d˚ ukazu vˇety, uvedeme si dvˇe pomocná tvrzen´ı. Lemma 6. Bez u ´jmy na obecnosti m˚ uˇzeme pˇredpokl´ adat, ˇze funkce r je neklesaj´ıc´ı a prostorovˇe konstruovateln´ a. Nav´ıc plat´ı r(n) ≥ n2 . D˚ ukaz. Pokud r(n) nesplˇ nuje uvedené poˇzadavky, definujeme r0 (n) = max{poˇcet bunˇek pouˇzit´ ych k v´ ypoˇctu r(1), . . . , r(n), n2 }

(29)

Je zˇrejmé, ˇze r0 (n) je neklesaj´ıc´ı a prostorovˇe konstruovatelná. Také zˇrejmˇe plat´ı r0 (n) ≥ r(n) a tedy staˇc´ı dokázat vˇetu pro r0 (n). Lemma 7. Definujeme-li h(n) = r(h(n − 1)), h(1) = 2, plat´ı, ˇze h(n) je prostorovˇe konstruovateln´ a. D˚ ukaz. Plyne z prostorové konstruovatelnosti r(n). D˚ ukaz. Necht’ M1 , M2 , . . . jsou oˇc´ıslované deterministické Turingovy stroje s jednoprvkovou vstupn´ı abecedou. Dále budeme pˇredpokládat, ˇze délka zakódov´ an´ı stroje Mi je nejv´ yˇse log2 i (bez d˚ ukazu). Zkonstruujeme jazyk L takov´ y, ˇze 1) pokud stroj Mi rozpozn´ avá L, pak Si (n) ≥ h(n − i) skoro vˇsude 2) ∀k ∃j Mj : L(Mj ) = L a Sj (n) ≤ h(n − k) skoro vˇsude Pokud takov´ y L najdeme, jsme hotov´ı, nebot’ je-li dáno i takové, ˇze L(Mi ) = L, potom zvol´ıme k = i+1 a d´ıky podm´ınce 2 v´ıme, ˇze ∃j : L(Mj ) = L a Sj (n) ≤ h(n−i−1), d´ıky podm´ınce 1 potom Si (n) ≥ h(n−i) = r(h(n−i−1)) ≥ r(Sj (n)). Popiˇsme nyn´ı konstrukci takového jazyka L (nad abecedou {0}). Necht’ m´ ame pevné n. Definujeme σ(n) = min{j : j ≤ n, Sj (n) < h(n − j), ∀i < n : σ(i) 6= j} Pokud je σ(n) definov´ ano, ˇrekneme, ˇze stroj Mσ(n) je zruˇsen ˇc´ıslem n. V jednom kroku konstrukce uvaˇzuji pevnˇe dané n a mnoˇzinu tˇech stroj˚ u, které nebyly zruˇseny ˇz´ adn´ ym k, k < n. Tato mnoˇzina je v kaˇzdém kroku konstrukce koneˇcn´ a. Z této mnoˇziny vyberu stroj s nejmenˇs´ım indexem j = σ(n) takov´ y, ˇze Sj (n) < h(n − j), pokud takov´ y index existuje. Nyn´ı zaruˇc´ım, aby ˇz´ adn´ y zruˇsen´ y stroj nepˇrij´ımal jazyk L: 0n ∈ L ⇔ σ(n) je definované a Mσ(n) nepˇrij´ımá On 24

Ukaˇzme, ˇze L splˇ nuje obˇe uvedené podm´ınky. Necht’ i je takové, ˇze L(Mi ) = L a uvaˇzujme stroje M1 , . . . , Mi−1 . Nˇekteré z tˇechto stroj˚ u jsou zruˇseny, kaˇzd´ y je zruˇsen´ y nˇejak´ ym konkrétn´ım n. Necht’ n0 je maximum z tˇechto ˇc´ısel. Potom plat´ı: ∀n > max{n0 , i} : Si (n) ≥ h(n − i). Dok´ aˇzeme sporem. Necht’ ∃n > max{n0 , i} : Si (n) < h(n − i), potom je ale splnˇena podm´ınka pro zruˇsen´ı Mi a tedy L(Mi ) 6= L. Tedy podm´ınka 1 je splnˇena. Ukaˇzme d´ ale, ˇze L splˇ nuje i podm´ınku 2. Necht’ k je libovolné pevné, zkonstruujme Mj takov´ y, ˇze L(Mj ) = L a Sj (n) ≤ h(n − k) skoro vˇsude. Jin´ ymi slovy, Mj bude na rozhodnut´ı, zda 0n patˇr´ı do L, potˇrebovat prostor nejv´ yˇse h(n − k) skoro vˇsude. Pro vstup On mus´ı Mj : 1) zjistit, zda je σ(n) definováno a pokud ano, tak σ(n) spoˇc´ıtat, 2) po zjiˇstˇen´ı σ(n) odsimulovat Mσ(n) , aby mohl rozhodnout, zda 0n ∈ L. Chceme-li zjistit σ(n), mus´ıme nejprve zjistit, které stroje Mi , i ≤ n byly zruˇseny nˇejak´ ym ˇc´ıslem l < n. Pro pevné i a l staˇc´ı pracovat v prostoru h(l − i), protoˇze pokud ˇc´ıslo l zruˇs´ı stroj Mi , tak Si (l) ≤ h(l−i). Pro vymezen´ı uvedeného mnoˇzstv´ı prostoru potˇrebujeme, aby byla h prostorovˇe konstruovatelná. Zde se ovˇsem objev´ı problém v pˇr´ıpadˇe, ˇze l − i > n − k, protoˇze potom se simulace do vymezeného prostoru nevejde. Problém obejdeme drobn´ y trikem. Uvaˇzujme M1 , . . . , Mk a necht’ n1 je nejvˇetˇs´ı ˇc´ıslo, kter´ ym je nˇekter´ y z tˇechto stroj˚ u zruˇsen. Modifikujeme M tak, ˇze ∀l ≤ n1 bude ˇr´ıd´ıc´ı jednotka obsahovat informace o tom, zda Ol ∈ L a ˇc´ıslo stroje zruˇseného ˇc´ıslem l, pokud takov´ y existuje. Potom ∀n ≤ n1 pracuje M s nulovou prostorovou sloˇzitost´ı, pro n > n1 staˇc´ı odsimulovat stroje Mi pro i = k + 1, . . . , n. Stroj Mi pracuje na vstupu 0n v prostoru h(l − i) ≤ h(n − k), protoˇze l ≤ n a i ≥ k. Tedy stroj Mi se do uvedeného prostoru vejde, jeˇstˇe je tˇreba ukázat, ˇze se do nˇej vejde i stroj M pˇri simulaci Mi . Pro n > n1 , je-li definov´ ano σ(n), tak σ(n) je alespoˇ n k, tedy Mσ(n) na vstupu On pracuje v prostoru h(n − σ(n)), coˇz je nejv´ yˇse h(n − k), protoˇze σ(n) > k. M postupnˇe simuluje stroje Mi pro k + 1 ≤ i ≤ n na vstupech 0l pro l ≤ n. Pro kaˇzdou dvojici (i, l) staˇc´ı reprezentovat na stroji h(l − i) bunˇek stroje Mi . i ≤ n, Mi je zak´ odov´ an v nejv´ yˇse log2 i ≤ log2 n buˇ nkách stroje M , tedy t´ım sp´ıˇse libovoln´ y symbol stroje Mi lze zakódovat v log2 n symbolech stroje M . x−2 Protoˇze v´ıme, ˇze r(x) ≥ x2 , plat´ı h(x) ≥ 22 (d˚ ukaz lze indukc´ı). n−k−2 2 Tedy h(n − k) ≥ 2 ≥ log2 n skoro vˇsude, tedy prostor h(n − k) staˇc´ı pro simulaci Mi pro skoro vˇsechna n. Kromˇe m´ısta na simulaci potˇrebuje M také prostor na ukládán´ı seznamu zruˇsen´ ych stroj˚ u. Zruˇsen´ ych stroj˚ u je nejv´ yˇse n, tedy je potˇreba nejv´ yˇse n·log2 n m´ısta. Plat´ı n · log2 n ≤ n2 ≤ h(n − k) skoro vˇsude. M tedy pracuje v prostoru 2h(n − k) skoro vˇsude, dle lemma 4 existuje M 0 pracuj´ıc´ı v prostoru 2h(n − k) vˇsude a podle vˇety o kompresi existuje stroj M 00 , kter´ y pracuje v prostoru h(n − k) vˇsude.

25

Složitost a NP-úplnost

Recommend Documents