Složitost a NP-úplnost. Ladislav Strojil podle přednášek RNDr. O. Čepka, Ph.D

Složitost a NP-úplnost Ladislav Strojil ˇ podle pˇrednášek RNDr. O. Cepka, Ph.D.

c 2003-2014 Ladislav Strojil Copyright ˇ ˇ NAPSÁNO PODLE P REDNÁŠEK DOCENTA RND R . O ND REJE Cˇ EPKA , P H .D. LADISLAV. STROJIL . CZ / SKOLA

Licensed under the Creative Commons Attribution-NonCommercial 3.0 Unported License (the “License”). You may not use this file except in compliance with the License. You may obtain a copy of the License at http://creativecommons.org/licenses/by-nc/3.0. Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an “AS IS ” BASIS , WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Contents

1

Motivace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.1

Složitost

2

Výpoˇ cetní model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1

Deterministický Turinguv ˚ stroj

7

2.2

Kódování Turingových stroju˚

8

2.3

Univerzální Turinguv ˚ stroj

10

2.4

Zpracování výjimek

10

2.5

Nedeterminismus

11

2.6

Mˇ eˇrení složitosti

11

2.6.1 2.6.2 2.6.3

Prostorová složitost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 ˇ Casová složitost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 ˇ asová složitost . . . . . . . . . . . . . . . . . . . . . . 11 Nedeterministická prostorová a c

2.7

Základní tˇrídy složitosti

3

Vˇ ety o kompresi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.1

Prostorová komprese

3.1.1

Redukce poˇ ctu pásek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.2

ˇ Casová komprese

3.2.1

Redukce poˇ ctu pásek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4

Konstruovatelnost funkcí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4.1

Definice konstruovatelnosti funkcí

21

4.2

Vˇ ety o konstruovatelnosti funkcí

21

5

11

13 15

5

Hierarchie tˇríd složitosti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

5.1

ˇ Casová hierarchie

25

5.2

Prostorová hierarchie

26

5.3

Vˇ ety o hierarchii

27

5.3.1 5.3.2

Prostorová hierarchie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 ˇ Casová hierarchie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

5.4

Vztahy mezi tˇrídami složitosti

5.4.1

Vˇ eta o vtazích mezi tˇrídami složitosti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

28

5.5

Savitchova vˇ eta

30

5.6

Pokroˇ cilé vˇ ety o tˇrídách složitosti

30

5.6.1 5.6.2

Vˇ eta o mezerách (Borodin) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Vˇ eta o zrychlení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

Složitost

1. Motivace

1.1

Složitost Tento text vznikl pˇred lety jako m˚uj zp˚usob, jak se tuto látku nauˇcit na zkoušku. Až pozdˇeji jsem zjistil, že pomohl se zkouškou nejen mnˇe, ale i dalším student˚um. Po mnoha letech, kdy jsem se od akademického svˇeta hodnˇe vzdálil, jsem se vrátil k TeXu, znova si všechno pˇreˇcetl, znova se to pokusil pochopit a jen tak, z cˇ isté radosti, že mohu, jsem texty maliˇcko pˇrepsal, maliˇcko doplnil a novˇe naformátoval. Budu rád, když budou i nadále užiteˇcné, když i nadále budou sloužit k tomu, aby ti, kdo chtˇejí, mohli nahlédnout do svˇeta výpoˇcetní složitosti. • test

Deterministický Turinguv ˚ stroj Kódování Turingových stroju˚ Univerzální Turinguv ˚ stroj Zpracování výjimek Nedeterminismus Mˇ eˇrení složitosti Prostorová složitost ˇ Casová složitost ˇ asová Nedeterministická prostorová a c složitost Základní tˇrídy složitosti

2. Výpoˇ cetní model

2.1

Deterministický Turinguv ˚ stroj Základním výpoˇcetním modelem využívaným pro studium výpoˇcetní složitosti je deterministický Turing˚uv stroj. ˇ ceno lidskou ˇreˇcí se jedná o stroj, který má k dispozici pamˇet’ovou pásku (nebo více Reˇ pásek), cˇ tecí a zapisovací hlavu pro každou pásku a ˇrídící jednotku, která stroj ovládá. Stroj je velmi základní, umí pouze cˇ íst políˇcko pod pˇríslušnou hlavou, pod pˇreˇctené hodnoty a podle aktuálního vnitˇrního stavu ˇrídící jednotky provést jednoduchou akci sestávající se ze zápisu na pásku a pˇrípadného posunu hlavy o jedno pole doprava nebo doleva. Pˇres svou jednoduchost a zdánlivou omezenost je takto definovaný stroj výpoˇcetnˇe velmi silný. Definice 2.1.1 — Deterministický Turinguv ˚ stroj.

Deterministický Turing˚uv stroj (DTS) M s k-páskami, kde k je konstanta, je pˇetice M = (Q, Σ, δ , q0 , F)

(2.1)

Q = koneˇcná množina stav˚u ˇrídící jednotky Σ = koneˇcná pásková abeceda δ : Q × Σk 7→ Q × Σk−1 × {L, N, R}k je pˇrechodová funkce (ˇcásteˇcná) q0 ∈ Q = poˇcáteˇcní stav F ⊆ Q = množina pˇrijímajících stav˚u Následující body popisují Turingovy stroje trochu podrobnˇeji a uvádí vysvˇetlení základních pojm˚u používaných ve vztahu k tomuto modelu. • Všech k pásek je jednosmˇernˇe (potenciálnˇe) nekoneˇcných. • Jedna z pásek je vstupní a pouze ke cˇ tení. • Na všech páskách se lze pohybovat obˇema smˇery (off-line model), v on-line modelu se lze na vstupní pásce pohybovat pouze doprava. • Konfigurace Turingova stroje je urˇcena: 1. stavem ˇrídící jednotky 2. pozicí hlav na jednotlivých páskách 3. slovy na jednotlivých páskách (obsahem pásek)

Chapter 2. Výpoˇ cetní model

8

• Poˇcáteˇcní konfigurace Turingova stroje: 1. ˇrídící jednotka je ve stavu q0 ; 2. všechny hlavy jsou zcela vlevo; 3. na vstupní pásce je zapsané vstupní slovo, ostatní pásky jsou prázdné. • Displej Turingova stroje je stav ˇrídící jednotky a obsah políˇcek pod hlavami. • Krok Turingova stroje je použítí pˇrechodové funkce na displej, pˇrepsání políˇcek pod 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áteˇcní konfiguraci, která konˇcí zastavením stroje nebo je nekoneˇcná. • Zastavení Turingova stroje je situace, kdy pro daný displej není pˇrechodová funkce definována (pˇredpokládá se, že to platí pro všechna 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). • Odmítající výpoˇcet Turingova stroje je výpoˇcet konˇcící zastavením v jiném než 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 je pˇrijímáno M}. P

2.2

Je potˇreba si uvˇedomit, že výpoˇcetní síla Turingova stroje plyne primárnˇe z nekoneˇcnosti jeho výpoˇcetního prostoru a možnosti posunovat cˇ tecí hlavu libovolnˇe daleko od poˇcáteˇcní buˇnky, jakkoliv tento posun musí být krok po kroku. Pˇri zkoumání výpoˇcetní složitosti navíc sledujeme asymptotické chování na neomezenˇe rostoucí délce vstupních dat, není tˇreba se tedy pˇríliš zabývat urˇcitou neohrabaností výpoˇctu. Dále v textu si uvedeme nˇekoliv vˇet, které nám umožní urˇcitou volnost pˇri využívání modelu – ukážeme, že lze redukovat poˇcty pásek, zrychlovat výpoˇcet, provádˇet pomocné výpoˇcty a podobné.

Kódování Turingových stroju˚ Pro pochopení mnoha d˚ukaz˚u je tˇreba mít na pamˇeti, že takto definovaný výpoˇcetní model umožˇnuje nahlížet na popis konkrétního TS jako na „ˇcíslo“ – to nám umožní, abychom mohli mluvit o všech TS a abychom mohli s TS pracovat jako se vstupem pro výpoˇcet. To nám obratem dovolí používat diagonální metodu a sebereferenˇcí d˚ukazy. Abychom mohli prezentovat stroj cˇ íslem, musíme si zvolit nˇejaké kódování stroje do naší pracovní abecedy. 1. Oˇcíslujeme stavy q ∈ Q a symboly s ∈ Σ binárními cˇ ísly. 2. Popíšeme pˇrechodovou funkci v abecedˇe A = {0, 1, δ , (, ), =, L, N, R, , } zˇretˇezením zápis˚u typu δ (q, x1 , x2 , . . . , xk ) = (q0 , y1 , . . . , yk , Z). 3. Pˇrepíšeme zápis z abecedy A do abecedy {0, 1} Potom pˇri pevnˇe zvoleném kódování každý Turing˚uv stroj jednoznaˇcnˇe odpovídá pˇrirozenému cˇ íslu. ˇ íslo. Kód Turingova stroje M budeme nazývat jeho GödeDefinice 2.2.1 — Gödelovo c lovým cˇ íslem.

Example 2.1 Jako pˇríklad si uved’me kódování zápisu TS v binární abecedˇe. M˚užeme pro

názornost použít klidnˇe ASCII kódování. Mˇejme napˇríklad tˇrístavový TS, který vypíše 21 jedniˇcek a skonˇcí (Busy Beaver).

M = (Q, Σ, δ , q0 , F) = ({A, B,C, HALT } , {0, 1} , {(0, A, 1, R, B), (0, B, 1, L, A), (0,C, 1, L, B), (1, A, 1, L,C), (1, B, 1, R, B Pˇrepsáno do ASCII a pˇrevedeno do binární podoby je to 00101000011110110100000100101 1000100001000101100010000110010110001001000010000010100110001010100011111010

2.2 Kódování Turingových stroju˚

9

010110001111011001100000010110000110001011111010010110001111011001010000011 0000001011000100000100101100001100010010110001010010001011000100001000101001 001011000010100000110000001011000100001000101100001100010010110001001100001 011000100000100101001001011000010100000110000001011000100001100101100001100 0100101100010011000010110001000010001010010010110000101000001100010010110001 000001001011000011000100101100010011000010110001000011001010010010110000101 000001100010010110001000010001011000011000100101100010100100010110001000010 0010100100101100001010000011000100101100010000110010110000110001001011000101 0010001011000100100001000001010011000101010000101001011111010010110001000001 0010110001111011010010000100000101001100010101000111110100101001. Pro poˇrádek se dohodneme, že pˇred každý takto získaný kód pˇridáme jedniˇcku. Dostaneme tedy 10010100001111011010000010010110001000010001011000100001100101100010010 0001000001010011000101010001111101001011000111101100110000001011000011000101 1111010010110001111011001010000011000000101100010000010010110000110001001011 00010100100010110001000010001010010010110000101000001100000010110001000010 00101100001100010010110001001100001011000100000100101001001011000010100000 110000001011000100001100101100001100010010110001001100001011000100001000101 00100101100001010000011000100101100010000010010110000110001001011000100110 00010110001000011001010010010110000101000001100010010110001000010001011000 011000100101100010100100010110001000010001010010010110000101000001100010010 110001000011001011000011000100101100010100100010110001001000010000010100110 001010100001010010111110100101100010000010010110001111011010010000100000101 001100010101000111110100101001, což je 5340935228926660811. V našem kódování má tedy stroj pro Busy Beaver problém Gödelovo cˇ íslo 5340935228926660811 a oznaˇcujeme jej M5340935228926660811 V nˇekterých pˇrípadech budeme chtít využít speciální cˇ íslování stroj˚u, které nám umožní v d˚ukazech provádˇet „triky“ s délkou vstupu – napˇríklad si volbou delšího cˇ ísla stroje jako vstupu „koupit“ více místa pro výpoˇcet. Jedním z takovách cˇ íslování je prefixové cˇ íslování – ke každému cˇ íslu Turingova stroje pˇridáme postupnˇe prefixy délky 1, 2, 3, ... nekoneˇcno. V praxi to m˚užeme udˇelat tˇreba tak, že zápis (v naší abecedˇe) rozšíˇríme o prefix "XXXX...X" všech možný délek. Alternativnˇe m˚užeme použít kódování, kde binární podobu indexu nastavíme zleva o 10000...0 pro všechny délky tohoto prefixu. Když budeme chtít potom z cˇ ísla stroje získat jeho popis, zaˇcneme tím, že prefix odstraníme (je jednoznaˇcnˇe rozpoznatelný). P

Pro pochopení práce s indexy stroj˚u je kritické si uvˇedomit, že každý stroj má své cˇ íslo (pˇrípadnˇe nekoneˇcnˇe mnoho cˇ ísel), nemusí ale platit, že každé cˇ íslo kóduje nˇejaký stroj. Když se ale na d˚ukazy podíváte pozornˇe, zjistíte, že to v˚ubec nevadí. Proto také m˚užeme jako kódování volit libovolnˇe neefektivní zápis. Výhodou také je, že v d˚ukazek pracujeme s existencí takového kódování/ˇcíslování, nikdy ale nejsme nuceni jej algoritmicky popisovat a detailnˇeji s ním pracovat.

Pro úplnost pˇridáme ještˇe pˇridáme jednu definici. Definice 2.2.2 — Transducer. Turing˚uv stroj, který má navíc výstupní pásku, na kterou

lze pouze psát (znak pod hlavou neovlivˇnuje pˇrechodovou funkci) a na které se hlava m˚uže pohybovat pouze vpravo, nazýváme transducer. (Stroj bez této pásky se nazývá acceptor). Existují r˚uzné varianty Turingových stroj˚u, o kterých lze ukázat, že mají stejnou výpoˇcetní sílu, tedy že pˇrijímají stejnou tˇrídu jazyk˚u (tu nazýváme rekurzivnˇe spoˇcetné množiny). Jsou to napˇríklad: • on-line Turingovy stroje;


10

• jednopáskové 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ýhodné používat Turingovy stroje jako výpoˇcetní model jsou zˇrejmé. Pˇrednˇe je to jasnˇe definovaný koncept cˇ asové složitosti výpoˇctu (bˇehu algoritmu) jako poˇcet krok˚u daného Turingova stroje nad daným vstupem. Analogicky jasnˇe definovaný koncept prostorové složitosti výpoˇctu (bˇehu algoritmu) jako poˇcet použitých bunˇek na pracovních páskách stroje.

2.3

Univerzální Turinguv ˚ stroj Když máme zavedené kódování a cˇ íslování stroj˚u (Gödelova cˇ ísla), m˚užeme si nadefinovat stroj, který bude simulovat libovolný jiný Turing˚uv stroj na základˇe jeho Gödelova cˇ ísla. Definice 2.3.1 — Univerzální Turinguv ˚ stroj. Univerzální Turing˚uv stroj je Turing˚uv stroj,

který má jako vstup Gödelovo cˇ íslo nˇejakého Turingova stroje M a pro vstupní slovo w pro M pracuje tak, že simuluje práci M nad w. Nebudeme zde popisovat detaily konstrukce univerzálního stroje, zmíníme jenom základní princip simulace. Stroj si dekóduje Gödelovo cˇ íslo a na pomocnou pracovní pásku si pˇripraví pˇrechodovou funkci (tabulku). Pˇri své práci stroj cˇ te hodnotu z pásky, „nahlédne“ do pˇrechodové tabulky a poté zapíše hodnotu a zmˇení stav. Zmˇena stavu v tomto pˇrípadˇe není zmˇena vnitˇrího stavu ˇrídící jednotky, ale stroj si bude simulovaný stav pamatovat zapsáním na pomocnou pásku. Pro zjednodušení si m˚užete pˇredstavit, že stroj má definované „podprocedury“ pro cˇ tení, zápis, pohyb hlavy a zmˇenu stavu, které vždy zavolá. Je zˇrejmé, že tato simulace vyžaduje více cˇ asu i prostoru. Dále si ukážeme nˇekteré konkrétní vztahy mezi univerzálním a simulovaným TS. V mnoha pˇrípadech nám ale staˇcí, že stroj existuje a vrací správný výsledek – jeho zvýšenou cˇ asovou a prostorovou složitost jsme schopni kompenzovat pomocnými výpoˇcty. P

2.4

Jak jsme již zmiˇnovali výše, není d˚uležité, že v našem kódování jsou „mezery“, že existují cˇ ísla, která nejsou Gödelovým cˇ íslem žádného stroje. Náš univerzální stroj dokáže neplatné cˇ íslo rozlišit a v takovém pˇrípadˇe výpoˇcet ukonˇcí a vstup odmítne. M˚užeme to brát tak, že všechna cˇ ísla, která nepˇredstavují syntakticky správný popis TS jsou Gödelovým cˇ íslem Turingova stroje, který okamžitˇe odmítá všechny vstupy (a tedy pˇrijímá prázdnou množinu, L(M) = 0. /

Zpracování výjimek Pomocí pˇridání nových stav˚u ˇrídící jednotky lze jednoduše ošetˇrit libovolnou pevnˇe danou koneˇcnou množinu vstup˚u. Provedeme to tak, že zkontruujeme koneˇcný automat (strom) rozpoznávající danou koneˇcnou množinu slov (koneˇcný automat odpovídá Turingovˇe stroji bez pásek). Turing˚uv stroj potom napˇred simuluje chod daného koneˇcného automatu. V pˇrípadˇe, že je na vstupu jedno z rozpoznávaných 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. P

Tato zdánlivá technikálie nám umožˇnuje efektivnˇe zanedbávat koneˇcné množiny vstup˚u a zjednodušuje mnoho d˚ukaz˚u.

2.5 Nedeterminismus

2.5

11

Nedeterminismus Od deterministického Turingova stroje se jeho nedeterministická varianta liší pouze definicí pˇrechodové funkce a stanovením odlišných podmínek, za kterých je slovo pˇrijato. Definice 2.5.1 — Nedeterministický turinguv ˚ stroj.

Definujme stroj jako v definici deterministického Turingova stroje s následujícími rozdíly: • δ : Q × Σk 7→ P(Q × Σk−1 × {L, N, R}k ) je pˇrechodová funkce (ˇcásteˇcná) • Slovo w je pˇrijímáno, jestliže existuje alespoˇn jeden pˇrijímající výpoˇcet. Pro zjednodušení m˚užeme pˇredpokládat binární vˇetvení výpoˇcetu. Snadno se dá ukázat, že se jedná o výpoˇcetnˇe ekvivalentní model. Existuje nˇekolik pohled˚u, jak na nedeterminismum pohlížet. M˚užete si pˇredstavovat, že stroj provede všechny výpoˇcty soubˇežnˇe (tedy kdykoliv pˇrechodová funkce vrací více jako jednu výslednou konfiguraci, stroj se namnoží a dále pokraˇcuje všemi cestami). Nebo si m˚užete pˇredstavit, že stroj vždy uhodne správnou cestu (jestliže existuje), napˇríklad protože má k dispozici nˇejakého „rádce“ (orakulum). Nebo si m˚užete pˇredstavit klasické sekvenˇcní zkoušení všech možností (backtracking). D˚uležité je, jakým zp˚usobem budeme potom mˇeˇrit složitost (ˇcasovou a prostorovou) takového výpoˇctu.

2.6 2.6.1

Mˇ eˇrení složitosti Prostorová složitost Prostorová složitost se vztahuje k délce pásky, kterou stroj potˇrebuje pro sv˚uj výpoˇcet. Složitost mˇeˇríme vždy ve vztahu k velikosti vstupního slova. Definice 2.6.1

Necht’ M je deterministický Turing˚uv stroj, pro který platí, že na každém vstupu délky n použije pˇri výpoˇctu nejvýše S(n) bunˇek na pracovních páskách. Potom ˇríkáme, že M má prostorovou složitost S(n) a že jazyk L(M) má prostorovou složitost S(n). 2.6.2

ˇ Casová složitost ˇ Casová složitost se vztahuje k poˇctu krok˚u, které stroj potˇrebuje pro sv˚uj výpoˇcet. Složitost mˇeˇríme vždy ve vztahu k velikosti vstupního slova. Definice 2.6.2

Necht’ M je deterministický Turing˚uv stroj, pro který platí, že na každém vstupu délky n provede pˇri výpoˇctu nejvýše T (n) krok˚u, než se zastaví. Potom ˇríkáme, že M má cˇ asovou složitost T (n) a že jazyk L(M) má cˇ asovou složitost T (n). 2.6.3

2.7

ˇ asová složitost Nedeterministická prostorová a c Definice jsou stejné jako u deterministických Turing˚uvých stroj˚u s tím, že nyní požadujeme, aby ∀w ∈ Σ∗ , |w| = n všechny možné výpoˇcty použily nejvýše S(n) políˇcek a skonˇcily nejdéle za T (n) krok˚u.

Základní tˇrídy složitosti DSPACE(S(n)) = tˇrída jazyk˚u deterministické prostorové složitosti S(n) NSPACE(S(n)) = tˇrída jazyk˚u nedeterministické prostorové složitosti S(n) DT IME(T (n)) = tˇrída jazyk˚u deterministické cˇ asové složitosti T (n) NT IME(S(n)) = tˇrída jazyk˚u nedeterministické cˇ asové složitosti T (n)


12 Vˇ eta 2.7.1 — Triviální vztahy.

∀ S(n) : DSPACE(S(n)) ⊆ NSPACE(S(n))

(2.2)

∀ T (n) : DT IME(T (n)) ⊆ NT IME(T (n))

(2.3)

∀ S1 (n) ≤ S2 (n) ⇒ DSPACE(S1 (n)) ⊆ DSPACE(S2 (n))

(2.4)

NSPACE(S1 (n)) ⊆ NSPACE(S2 (n)) ∀ T1 (n) ≤ T2 (n) ⇒ DT IME(T1 (n)) ⊆ DT IME(T2 (n))

(2.5)

NT IME(T1 (n)) ⊆ NT IME(T2 (n)) Proof. Zˇrejmé.

Prostorová komprese Redukce poˇ ctu pásek ˇ Casová komprese Redukce poˇ ctu pásek

3. Vˇ ety o kompresi

V této kapitole si pˇredvedeme, jakým zp˚usobem lze modifikovat Turing˚uv stroj tak, aby využíval ménˇe zdroj˚u – ukážeme, jak stroj libovolnˇe zrychlit, jak stroji umožnit poˇcítat v libovolnˇe menším prostoru cˇ i jak stroj modifikovat tak, aby mu staˇcila jedna páska místo mnoha. Všechny tyto vˇety použijeme v dalším textu pro zjednodušení d˚ukaz˚u.

3.1

Prostorová komprese Vˇ eta 3.1.1 — O lineární prostorové kompresi.

Necht’ L je jazyk pˇrijí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˚uv stroj M’ s prostorovou složitostí d 1r S(n)e, který pˇrijímá jazyk L. Proof. Každý znak abecedy stroje M’ bude kódovat jednu r-tici znak˚u abecedy p˚uvodního stroje. Velikost abecedy M’ |ΣM0 | bude rovna |Σ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 pro jednopáskový stroj. Je-li QM = {q0 , q1 , . . . , qs } množina stav˚u stroje M, potom definujeme 0 QM = {q10 , q20 , . . . , qr0 , . . . , q1s , q2s , . . . , qrs }. Pˇrechodová funkce δM0 bude simulovat pohyb hlavy zmˇenou horního indexu stavu, v pˇrípadˇe, že by index klesl na nulu nebo byl vˇetší než r, dojde k vlastnímu posunu hlavy (stroje M’). Všechna pravidla tvaru δM (qi , a) = (q j , b, N) nahradíme množinou pravidel δM0 (qli , xl ) = l (q j , yl , N), ∀ 1 ≤ l ≤ r, ∀ dvojice x, y ∈ ΣM0 , 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 (qi , a) = (q j , b, R) nahradíme množinou pravidel δM0 (qli , xl ) = l r l 1 r (ql+1 j , y , N), ∀ 1 ≤ l < r a δM 0 (qi , x ) = (q j , y , R). Analogicky pro pohyb doleva. δM (qi , a) = (q j , b, L) nahradíme množinou pravidel δM0 (qli , xl ) = l−1 l (q j , y , N), ∀ 1 < l ≤ r a δM0 (q1i , xl ) = (qrj , y1 , L). Nyní pro obecný stroj s k páskami. QM0 = {qip | 0 ≤ i ≤ s, ∀p ∈ {1, ..., r}kM } Promˇenná p zde probíhá pˇres všechny k-tice index˚u mezi 1 a r.

Chapter 3. Vˇ ety o kompresi

14

Analogicky jako pro pˇrípad jednopáskového stroje se sestrojí pˇrechodová funkce δM0 .

Corollary 3.1.2

∀ r ∈ N+ : DSPACE(S(n)) = DSPACE(d S(n) r e) Proof. Plyne pˇrímo z vˇety 3.1.1.

Vˇ eta 3.1.3

∀ r ∈ N+ : NSPACE(S(n)) = NSPACE(d S(n) r e) Proof. Zobecnˇením d˚ukazu vˇety 3.1.1 pro nedeterministický pˇrípad. 3.1.1

Redukce poˇ ctu pásek Jiným pˇrístupem k prostorové redukci je redukce poˇctu pracovních pásek. Obecnˇe pracujeme se stroji, které mají libovolné množství pásek. Zde si ukážeme, že lze všechny takové stroje ekvivalentnˇe pˇrevést na stroje jednopáskové pˇri zachování prostorové složitosti. Vˇ eta 3.1.4 — O redukci poˇ ctu pásek pro prostorovou složitost.

Necht’ L je jazyk pˇrijímaný k-páskovým deterministickým Turingovým strojem s prostorovou složitostí S(n). Potom existuje deterministický Turing˚uv stroj M 0 s jednou pracovní páskou a prostorovou složitostí S(n) pˇrijímající jazyk L. Proof. Myšlenka d˚ukazu: každé políˇcko na pásce stroje M 0 bude kódovat obsah k políˇcek (z každé pásky stroje M jedno). Dále bude v políˇcku zakódována kromˇe obsahu p˚uvodních pásek i informace, které z hlav se nachází nad tímto políˇckem. Nová abeceda bude definována následovnˇe: ΣM0 = {x0 , . . . , x2k −1 |∀x ∈ ΣkM } Tedy jsme nafoukli abecedu na všechny k-tice a navíc každou k-tici pˇridali s indexy od nuly do 2k−1 . Indexy si m˚užeme pˇredstavit v jejich binárním zápisu jako informaci o tom, které hlavy simulovaného stroje M se nachází nad daným políˇckem. Jeden krok stroje M je simulován v O(S(n)) krocích stroje M 0 tak, že hlava projde celou pásku, najde pozice hlav a odsimuluje krok M. Vzhledem k tomu, že pˇri simulaci nám nezáleží na cˇ asové složitosti, lze pro jednoduchost uvažovat výpoˇcet, který má k fází a v každé fázi se odsimuluje práce M na jediné pásce. Na zaˇcátku fáze a po jejím ukonˇcení bude hlava M 0 na zaˇcátku pásky. Jak bude probíhat samotná simulace? Každou 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ým displejem simulované instrukce. 1. Instrukce M oˇcíslujeme a tato cˇ ísla zakódujeme do stav˚u M 0 . Tím zajistíme, že po zaˇcátku 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ásek, to znamená koneˇcný a pevnˇe daný). Výsledný poˇcet stav˚u je tedy také koneˇcný. 2. Instrukci δM (qi , a1 , . . . , ak ) = (q j , 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á políˇcko, ve kterém je oznaˇcena pozice první hlavy. • Když x nekóduje pozici první hlavy, δM0 ((l, qi , a1 , . . . , ak , 1R ), x) = ((l, qi , a1 , . . . , ak , 1R ), x, R). • Když x kóduje pozici první hlavy, rozlišíme následující pˇrípady podle smˇeru, kterým by se první hlava posunula pˇri práci stroje M.

ˇ 3.2 Casová komprese

15

(a) z1 = N Znak x kódující (a1 , a2 , . . . , ak ) se pˇrepíše na znak y kódující (b1 , a2 , . . . , ak ) se stejnou množinou hlav. Zároveˇn se provede aktualizace displeje a 1R se zmˇení na 1L . δM0 ((l, qi , a1 , . . . , ak , 1R ), x) = ((l, q j , b1 , a2 , . . . , ak , 1L ), y, N) (b) z1 = R Znak x kódující (a1 , a2 , . . . , ak ) se pˇrepíše na znak y kódující (b1 , a2 , . . . , ak ) se stejnou množinou hlav, s vyjímkou první hlavy. δM0 ((l, qi , a1 , . . . , ak , 1R ), x) = ((l, q j , b1 , a2 , . . . , ak , 1N ), y, R) δM0 ((l, q j , a1 , . . . , ak , 1N ), z) = ((l, q j , b1 , a2 , . . . , ak , 1L ), z0 , N) Zde z0 kóduje 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ásleduje odjezd hlavy M’ na zaˇcátek pásky a pˇrepnutí do stavu (l, q j , b1 , a2 , . . . , ak , 2R ). • Simulace dále pokraˇcuje další fází. Vˇ eta 3.1.5 — Nedeterministická verze.

Vˇeta 3.1.4 platí ve stejném znˇení i pro nedeterministické Turingovy stroje. Proof. Simulace uvedená v d˚ukazu vˇety 3.1.4 je použitelná beze zmˇen i pro pˇrípad nedeterministického Turingova stroje.

3.2

ˇ Casová komprese Lemma 3.2.1 — O lineárním zrychlení.

Necht’ L je jazyk pˇrijímaný k-páskovým deterministickým Turingovým strojem M s cˇ asovou složitostí T (n). Dále necht’ platí k ≥ 2 a necht’ r je celé cˇ íslo, r > 0. Potom existuje deterministický Turing˚uv stroj M 0 takový, že každý vstup w délky n pˇrijímá právˇe, když jej pˇrijímá M. Pracuje-li M nad w t krok˚u, pracuje M 0 nad w v cˇ ase n + dn/re + 6dt/re. Poznámka: Pˇredpokládáme, že na vstupní pásku je možno zapisovat. Proof. Princip konstrukce spoˇcívá v tom, že nadefinujeme stroj, který bude pracovat nad koneˇcnými kusy vstupní pásky a bloky výpoˇctu tak provede v jednom kroku pomocí pˇrechodové funkce. V první fázi 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, že 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 vˇetší než nula. Po provedení se vrátí na zaˇcátek pásky. Nadále bude tuto pásku použí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ž 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šimnˇete si, že se jedná o 3·r políˇcek stroje M). • V další fázi M 0 zjistí stav tˇechto 3r políˇcek stroje M po r krocích. Uvˇedomte si, že bˇehem r krok˚u stroj M nem˚uže tato políˇcka opustit, nebot’ se jeho hlava nacházela v prostˇrední tˇretinˇe tohoto úseku. Navíc zmˇena stavu tohoto úseku obsahuje jenom koneˇcnou informaci


16

a tedy m˚uže být zakódována 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ýpoˇctu, nebot’ získání potˇrebné informace lze provést již 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é, že stroj M mohl bˇehem tˇechto r krok˚u modifikovat nejvýše 2 z tˇechto úsek˚u (každý má totiž délku r, navíc nemohl modifikovat oba krajní úseky souˇcasnˇe). V pˇrípadˇe, že modifikoval pouze prostˇrední políˇcko, lze jeho nový obsah zapsat bˇehem jednoho kroku (v takovém pˇrípadˇe udˇelá stroj jeden prázdný 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 cˇ i odmítne, jestliže stroj M bˇehem simulovaného úseku pˇrijmul cˇ i odmítnul. Pˇredzpracování vstupní pásky vyžadovalo n + dn/re krok˚u (druhý sˇcítanec odpovídá cˇ asu 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ýpoˇctu M 0 , z nichž každý trvá 6 krok˚u. V souˇctu dostáváme tvrzení lemmatu.

P

M˚uže se vám zdát, že v konstrukci se stavy a pˇrechodová funkce nafukují nad všechny meze, ale jde poˇrád jenom o koneˇcnou množinu. Sice, stejnˇe jako v mnoha obdobných d˚ukazech, pracujeme s exponenciálním nár˚ustem velikosti abecedy a pˇrechodové funkce, jedná se ale o exponenciální nár˚ust vzhledem ke konstantˇe r. Také je dobré si uvˇedomit, že protože je r konstanta, nelze takovýmto zrychlováním opustit asymptotickou tˇrídu složitosti.

Nyní pomocí dokázaného lemma dokážeme samotnou vˇetu o lineárním zrychlení. Vˇ eta 3.2.2 — O lineárním zrychlení.

Necht’ L je jazyk pˇrijímaný k-páskovým deterministickým Turingovým strojem M s cˇ 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˚uv stroj M’ s cˇ asovou složitostí c · t(n) pˇrijímající L. Proof. Necht’ r je celé cˇ íslo takové, že r > 12/c. Sestrojíme M 0 jako v pˇredcházejícím lemmatu. M 0 pracuje nad vstupem délky n v cˇ ase n + dn/re + 6dt(n)/re. Pro r ≥ 2 lze tento výraz zhora omezit jako 2n + 6 + (6/r) · t(n). Z pˇredpokladu 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 cˇ as výpoˇctu je omezen c · t(n). Koneˇcnˇe mnoho pˇrípad˚u, pro které není nerovnost splnˇena, ošetˇríme koneˇcným automatem a stroj M 0 nad nimi bude pracovat v konstantním cˇ ase. Corollary 3.2.3

Pokud t(n) ∈ ω(n), potom ∀ c > 0 : DT IME(t(n)) = DT IME(c · t(n)) Proof. Plyne pˇrímo z vˇety 3.2.2.

ˇ ást 2. Vˇ eta 3.2.4 — O lineárním zrychlení, c

Necht’ L je jazyk pˇrijímaný k-páskovým deterministickým Turingovým strojem M s cˇ 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˚uv stroj M 0 s cˇ asovou složitostí (1 + ε) · n pˇrijímající L.


17

Proof. Budeme požadovat, aby n + dn/re + 6dcn/re ≤ (1 + ε) · n

(3.1)

n + n/r + 6cn/r + 7 ≤ (1 + ε) · n

(3.2)

(1 + 1/r + 6c/r + 7/n) · n ≤ (1 + ε) · n

(3.3)

Vztah (3.1) je požadovaná nerovnost, v (3.2) je na levé stranˇe horní odhad levé strany (3.1), tedy staˇcí ukázat (3.2). Nerovnost (3.3) je prostá úprava (3.2). Ukážeme, že lze volit r a n0 tak, že pro n > n0 platí (1/r + 6c/r + 7/n) < ε. Požadujeme: 1/r ≤ ε/3

dostáváme r ≥ 3/ε

(3.4)

6c/r ≤ ε/3

dostáváme r ≥ 18c/ε

(3.5)

7/n0 ≤ ε/3

dostáváme n0 ≥ 21/ε

(3.6)

Z (3.4) a (3.5) dostáváme r = max{3/ε, 18c/ε} = 18c/ε. Z (3.6) dostáváme n0 = 21/ε. Tvrzení vˇety je dokázáno.

Corollary 3.2.5

Pokud t(n) = cn, kde c > 1, potom ∀ ε > 0 : DT IME(t(n)) = DT IME((1 + ε)n) Proof. Plyne pˇrímo z vˇety 3.2.4.

Vˇ eta 3.2.6 — 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) Proof. Pˇredchozí d˚ukazy lze zobecnit (pomocí odhadu poˇctu dosažitelných konfigurací) i pro nedeterministický pˇrípad. 3.2.1

Redukce poˇ ctu pásek Nyní si stejnˇe jako v pˇrípadˇe prostorové složitosti ukážeme, že i pro cˇ asovou složitost lze poˇcet pásek redukovat. Protože ale obecnˇe platí, že cˇ as je „vzácnˇejší zdroj“ než prostor, nedosáhneme stejnˇe silného výsledku jako v pˇredchozích vˇetách. V tomto pˇrípadˇe se samozˇrejmˇe nejedná primárnˇe o cˇ asovou redukci, nebot’ redukujeme poˇcet pásek, tedy prostor. Vˇeta je zaˇrazena ale zde, protože dokazuje, že cˇ asová penalizace pˇri redukci poˇctu pásek, m˚uže být omezena kvadraticky (pro redukci na jednu pásku) nebo linearitmicky (n log n) (pˇri redukci na jednu pásku). Redukce poˇ ctu pásek ˇ asovou složitost. Vˇ eta 3.2.7 — O redukci poˇ ctu pásek pro c

√ Necht’ L ∈ DT IME(T (n)) a bud’ T (n) ∈ ω(n) nebo T (n) = cn, kde c > 2k, kde k je poˇcet pásek stroje pˇrijímajícího L v cˇ ase T (n). Potom existuje jednopáskový deterministický Turing˚uv stroj M s cˇ asovou složitostí (T (n))2 , který pˇrijímá L.

Proof. Použijeme kombinaci vˇety o zrychlení a vˇety o redukci poˇctu pásek pro prostorovou složitost. Pokud je L pˇrijímán jednopáskovým strojem, není co dokazovat. Necht’ je tedy pˇrijímán k-páskovým strojem, kde k > 1.


18

1. Necht’ T (n) ∈ ω(n). Dle vˇety o lineárním zrychlení existuje deterministický Turing˚uv stroj M 0 pˇrijímající L v cˇ ase √12k · T (n) = T 0 (n) v prostoru S0 (n). Nyní použijeme vˇetu o redukci poˇctu pásek pro prostorovou složitost a z ní odvodíme stroj, který má jednu pásku a který pˇrijímá L v cˇ ase T 00 (n) ≤ 2k · S0 (n) · T 0 (n) ≤ 2k · (T 0 (n))2 = (T (n))2 √ 2. Necht’ T (n) = cn, kde c > 2k. Dle vˇety o lineárním zrychlení zvolíme ε tak, aby platilo c 1 1+ε = √ tedy (1 + ε)n = √ T (n) (3.7) 2k 2k Zbytek stejnˇe jako v bodˇe 1. Corollary 3.2.8

Pokud L ∈ NT IME(T (n)), potom existuje jednopáskový nedeterministický Turing˚uv stroj s cˇ asovou složitostí (T (n))2 pˇrijímající L. Proof. Plyne pˇrímo z vˇety 3.2.7.

Dokázali jsme, že lze „vymˇenit“ poˇcet pásek za kvadratický nár˚ust cˇ asové složitosti. Nyní ukážeme, že když dovolíme alespoˇn dvˇe pásky, m˚užeme nár˚ust cˇ asu snížit na logaritmus místo druhé mocniny. Je pomˇernˇe pˇrirozené, že redukce z libovolnˇe mnoho na dvˇe bude v urˇcitém ohledu snazší a efektivnˇejší, zatímco redukce na jedinou pásku je neefektivní. Situace, kdy pˇrechod od mnoha ke dvˇema je menší než od dvou na jednu, není neobvyklá. Následující vˇeta je zatím nejkomplikovanˇejší a její konstrukce není úplnˇe pˇrímoˇcará. Hlavní myšlenkou je vyhnout se hledání displeje p˚uvodního stroje (jezdit po páskách sem a tam). Proto budeme udržovat displej na jediném políˇcku. Tedy místo pohybu hlav budeme pohybovat obsahem celé pásky. Pˇresuny dat budeme dˇelat tak, aby malé pˇresuny byly cˇ astˇejší a velké (vzdálené) pˇresuny byly vzácné. ˇ asovou složitost, 2. Vˇ eta 3.2.9 — O redukci poˇ ctu pásek pro c

Necht’ je L pˇrijímán k-páskovým deterministickým Turingovým strojem M s cˇ asovou složitostí T (n). Potom existuje 2páskový deterministický Turing˚uv stroj M 0 s cˇ asovou složitostí T (n) log2 T (n) pˇrijímající L. Proof. První páska stroje bude mít 2k stop, tedy každý znak abecedy ΣM0 bude kódovat 2k znak˚u p˚uvodní abecedy (plus speciální prázdný symbol). Jinými slovy, pracujeme na dvou páskách, z nichž jedna je pomocná a druhá pracovní. Ta pracovní kóduje dvˇe sady k stop. Druhá (pomocná) páska bude sloužit k pˇresun˚um dat na pásce první. Obˇe pásky pˇredpokládáme oboustrannˇe nekoneˇcné. První páska stroje bude rozdˇelena do blok˚u . . . , B−2 , B−1 , B0 , B1 , B2 , . . .. Blok B0 se sestává z jediného políˇcka a bude obsahovat displej stroje M. Pro ostatní bloky platí: ∀i, |i| ≥ 1 : |Bi | = 2|i|−1 – tedy velikost každého bloku nar˚ustá exponenciálnˇe v˚ucˇ i jeho vzdálenosti od stˇredu pásky. Bloky jsou oddˇeleny znaˇckami, které jsou umist’ovány pˇri prvním použití bloku. Ukážeme simulaci práce M na první pásce (stroje M). Na zaˇcátku výpoˇctu je obsah první pásky M na spodní sadˇe stop pásky M 0 (pˇripomeˇnme, že pracovní páska má 2k stop). Po celou dobu simulace budou platit následující invarianty: 1. Pro každé i > 0 nastává právˇe jedna ze tˇrí možností. (a) Bi má obˇe sady stop plné a B−i má obˇe sady stop prázdné; (b) B−i má obˇe sady stop plné a Bi má obˇe sady stop prázdné; (c) Bi i B−i mají spodní sadu stop plnou a horní sadu stop prázdnou.


19

Figure 3.1: Pásky nového stroje 2. ∀i Bi obsahuje souvislý interval pásek stroje M. Pro i < 0 obsahuje horní sada stop symboly vpravo od dolní sady stop, pro i > 0 horní sada stop obsahuje symboly vlevo od dolní sady. 3. B0 obsahuje symboly pouze na dolní sadˇe stopˇe, horní sada obsahuje speciální znaˇcku, která slouží pro vyhledání tohoto bloku. 4. ∀i Bi obsahuje interval pásky stroje M bezprostˇrednˇe nalevo od obsahu bloku Bi+1 .

Figure 3.2: Zápis dat na páskách Simulace jednoho kroku M. Displej je v B0 . Krok se skládá ze zmˇeny dat na pásce (zˇrejmé) a simulace posunu hlavy. Ukážeme si pˇrípad posunu hlavy doleva, tedy data budeme posunovat doprava. i) Hlava jede doprava, dokud nenajde blok Bi takový, že má alespoˇn jednu sadu stop volnou. (To znamená, že všechny bloky, které pˇrejel, byly zcela plné!) ii) Hlava jede zpátky a kopíruje obsah blok˚u Bi−1 , Bi−2 , . . . , B0 na pomocnou pásku. Bloky projede každý tˇrikrát, nebot’ musí pˇrekopírovat obsah obou stop a to ve správné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žiku, kdy hlava dojede na konec bloku Bi−1 , zbyde na pracovní pásce pˇresnˇe |Bi | nepˇrekopírovaných políˇcek. (a) V pˇrípadˇe, že byl Bi zcela prázdný, napíše je M 0 do spodní stopy. (b) V pˇrípadˇe, že byl Bi poloprázdný, napíše 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ý 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, že byl B−i zcela plný (tj. Bi byl zcela prádzný) (b) dolní stopy B−i , v pˇrípadˇe, že byl B−i poloplný (tj. Bi byl poloplný) vii) Hlava jede vpravo a do spodní stopy blok˚u B−i+1 , B−i+2 , . . . , B0 kopíruje obsah pomocné pásky. Bloky B−i+1 , B−i+2 , . . . , B0 musely být prázdné, nebot’ Bi byl první blok napravo od B0 , který nebyl plný. Kroky i - vii nazveme Bi operací. Pro Bi operaci platí, že zachovává platnost uvedených invarant˚u a trvá cˇ as O(|Bi |). Jaká je cˇ asová složitost celé simulace? Operace Bi m˚uže být provedena pouze jednou za


20

2i−1 krok˚u stroje M. D˚uvodem je fakt, že po jejím provedení jsou horní stopy blok˚u B1 , . . . , Bi−1 prázdné a tedy je potˇreba posunout pásku alespoˇn 2i−1 -krát, což vyžaduje nejménˇe takový poˇcet krok˚u. Pokud stroj M udˇelá T (n) krok˚u bˇehem výpoˇctu, m˚uže se Bi operace provést nejvýše bT (n)/2i−1 c-krát. Staˇcí uvažovat Bi operace pro i ≤ dlog2 T (n)e ≤ log2 T (n) + 1. Necht’ m je konstanta taková, že každá Bi operace trvá nejvýše m · 2i−1 krok˚u. Stroj M 0 tedy udˇelá maximálnˇe T 0 (n) ≤

log2 T (n)+1

∑

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

i=1

(3.8)

log2 T (n)+1

≤

∑

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

i=1

Pro simulaci práce na všech k páskách je potˇreba k · m · T (n) log2 T (n). Po použití vˇety o zrychlení dostáváme deterministický Turing˚uv stroj M 00 , který pˇrijímá L v cˇ ase T (n) log2 T (n).

P

Pˇredstavte si horní sadu stop na pracovní pásce jako „nárazník“, buffer. Náš nový stroj hýbe páskou doprava a doleva, ale nárazníky mu umožnují udržet pohyby lokální. Protože velikost blok˚u (a tím i nárazník˚u) roste expenenciálnˇe se vzdáleností od stˇredu, jsou pohyby s velkými bloky velmi ˇrídké. Každý takový pohyb je navíc relativnˇe rychlý, vyžaduje jenom lineární cˇ as. A po jeho dokonˇcení jsou zase všechny menší nárazníky vyprázdnˇené a výpoˇcet musí bˇežet exponencielnˇe dlouho v˚ucˇ i velikosti posledního posunovaného bloku, než bude potˇreba znova posun stejné velikosti. Je dobré si u toho d˚ukazu uvˇedomit, že p˚uvodnˇe podivnˇe znˇející pˇrístup „posunovat celou pásku“ se pomocí toho triku mˇení na velmi efektivní zp˚usob simulace.

Definice konstruovatelnosti funkcí Vˇ ety o konstruovatelnosti funkcí

4. Konstruovatelnost funkcí

V této kapitole se budeme zabývat funkcemi a jejich vyˇcíslitelností v cˇ ase nebo prostoru.

4.1

Definice konstruovatelnosti funkcí Definice 4.1.1 Funkce f : N → N je rekurzivní, jestliže existuje deterministický Turing˚uv

stroj M, který pro vstup 1n vydá výstup 1 f (n) . Definice 4.1.2 Funkce f : N → N je vyˇcíslitelná v cˇ ase O( f ), jestliže je rekurzivní a ∃c ≥ 1

takové, že pˇríslušný deterministický Turing˚uv stroj M udˇelá nejvýše c · f (n) krok˚u, než vydá výstup 1 f (n) . Definice 4.1.3 Funkce f : N → N je vyˇcíslitelná v prostoru O( f ), jestliže je rekurzivní a

∃c ≥ 1 takové, že pˇríslušný deterministický Turing˚uv stroj M použije nejvýše c · f (n) prostoru, než vydá výstup 1 f (n) . Definice 4.1.4 Funkce f : N → N je cˇ asovˇe konstruovatelná, pokud existuje deterministický

Turing˚uv stroj M takový, že pro každý vstup délky n zastaví právˇe po f (n) krocích. Definice 4.1.5 Funkce f : N → N je prostorovˇe konstruovatelná, pokud existuje determini-

stický Turing˚uv stroj M takový, že pro každý vstup délky n zastaví s právˇe f (n) páskovými políˇcky neprázdnými a bˇehem výpoˇctu žádný jiný prostor na pracovních páskách nebyl použit.

4.2

Vˇ ety o konstruovatelnosti funkcí Konstruovatelnost jsme si zadefinovali r˚uznými zp˚usoby – nyní si ukážeme, že jsou tyto definice vzájemnˇe ekvivalentní. Nejdˇríve pomocné lemma. Lemma 4.2.1

Necht’ f1 + f2 a f2 jsou cˇ asovˇe konstruovatelné funkce a necht’ ∃ε > 0 ∃n0 ∀n > n0 : f1 (n) ≥ ε f2 (n) + (1 + ε)n. Potom je f1 cˇ asovˇe konstruovatelná. Proof. Metodou podobnou té z d˚ukazu vˇety o lineárním zrychlení zrychlíme výpoˇcet trvající f1 (n) + f2 (n) krok˚u tak, aby trval pˇresnˇe f1 (n) krok˚u.

Chapter 4. Konstruovatelnost funkcí

22

Mˇejme M1 deterministický Turing˚uv stroj pracující v cˇ ase f1 (n) + f2 (n) a M2 deterministický Turing˚uv stroj pracující v cˇ ase f2 (n) (z pˇredpoklad˚u). Zkonstruujeme Mr , který pracuje v cˇ ase f1 (n) pro skoro všechny vstupy. Práce Mr je rozdˇelena do 4 fází. 1. V první fázi pˇrepíše vstup na první pracovní pásku, na kterou jej zapíše r-krát zahuštˇený. Zároveˇn pˇrepíše (r − 6)-krát zahuštˇený vstup také na 2. a 3. pracovní pásku. Na to potˇrebuje n krok˚u. Zároveˇn ˇrídící jednotka poˇcítá modulo (r − 6) a po skonˇcení pˇrepisu provede maximálnˇe r − 5 krok˚u tak, aby celkový poˇcet krok˚u první fáze byl dˇelitelný (r − 6). Tedy dostáváme n T1 = (r − 6) · . (4.1) r−6 2. V druhé fázi Mr soubˇežnˇe simuluje stroj M1 na první pásce a M2 na druhé pásce. Šest 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 d f2 (n)/(r − 6)e sekvencích stroje Mr . Potˇrebujeme zajistit: f1 (n) + f2 (n) f2 (n) > (4.2) r r−6 Pˇribližnˇe: ( f1 (n) + f2 (n)) · (r − 6) > r · f2 (n) f1 (n) · (r − 6) ≥ 6 f2 (n) 6 f2 (n) r−6 ≥ f1 (n) 6 f1 (n) ≥ f2 (n) r−6 6( f1 (n) + f2 (n)) r≥ f1 (n) V okamžiku, 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, že f2 (n) nebylo násobkem (r − 6), provede stroj M 0 pˇresnˇe (r − 6) d f2 (n)/(r − 6)e − f2 (n) prázdných krok˚u, cˇ ímž se trvání druhé fáze doplní na nejbližší vˇetší násobek (r − 6). Z uvedeného dostáváme, že poˇcet krok˚u stroje M 0 potˇrebný pro druhou fázi je

f2 (n) f2 (n) T2 = 6 · + (r − 6) − f2 (n) = r−6 r−6 f2 (n) = r· − f2 (n) r−6

(4.3)

Z pˇredpoklad˚u plyne, že T2 je pro skoro všechna n kladné. Je zˇrejmé, že bˇehem této fáze bylo odsimulováno r · d f2 (n)/(r − 6)e krok˚u stroje M1 , nebot’ bˇehem každé 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ázi pokraˇcuje M 0 simulací M1 stejným 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ž zajistíme tak, že po každé sekvenci pˇreˇcteme jeden symbol z pˇrepsaného komprimovaného vstupu (viz fáze 1). ˇ pro tuto fázi je Cas n T3 = 6 · +1 (4.4) r−6

4.2 Vˇ ety o konstruovatelnosti funkcí

23

a je odsimulováno r · (dn/(r − 6)e + 1) krok˚u stroje M1 . Pˇri srovnání cˇ asu výpoˇctu stroje M1 s dosud odsimulovaným poˇctem je zˇrejmé, že pro dostateˇcnˇe velké hodnoty r tato simulace pro skoro všechna n nedosáhne celého výpoˇctu M1 . 4. Ve cˇ tvrté fázi pokraˇcuje M 0 real-time simulací stroje M1 (jeden krok M 0 odpovídá jednomu kromu M1 ), dokud se M1 nezastaví. Na závˇer provede M 0 r − 6 prázdných krok˚u a zastaví ˇ na tuto fázi je zbývající cˇ as stroje M1 plus r − 6, z toho dostáváme: se. Cas f2 (n) n T4 = f1 (n) + f2 (n) − r · −r· +1 +r−6 (4.5) r−6 r−6 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ˇredpoklad˚u tvrzení. Souˇctem T1 , T2 , T3 , T4 dostáváme, že cˇ as pro bˇeh stroje M 0 je pˇresnˇe f1 (n) pro skoro všechna n. Vˇ eta 4.2.2 — O ekvivalenci definic 4.1.2 a 4.1.4.

Necht’ f : N → N je funkce taková, že ∃ε > 0 ∃n0 ∀n ≥ n0 : f (n) ≥ (1 + ε)n. Potom f je cˇ asovˇe konstruovatelná právˇe, když f je vyˇcíslitelná v cˇ ase O( f ). Proof. Implikace zleva doprava je zˇremá. Stroj dokazující cˇ asovou konstruovatelnost modifikujeme tak, že na novou pásku v každém kroku napíše jeden symbol. Nový stroj vyˇcísluje f v cˇ ase O( f ). Nyní opaˇcná implikace. Necht’ M je deterministický Turing˚uv stroj, který vyˇcísluje f v cˇ ase O( f ). Oznaˇcme g(n) poˇcet krok˚u stroje M nad vstupem 1n (zˇrejmˇe ∃c > 0 : g(n) ≤ c f (n)). 1. g je cˇ asovˇe konstruovatelná (díky existenci stroje M). 2. g + f je cˇ asovˇe konstruovatelná. Modifikuji M tak, aby poˇcítal výstup na zvláštní pásku a po skonˇcení výpoˇctu pˇrejel na zaˇcátek této pásky. Doba výpoˇctu je g(n), délka výstupu je f (n). 3. ∃ε > 0 ∃n0 ∀n > n0 : f (n) ≥ εg(n) + (1 + ε)n Zvolíme: (a) ε1 , jehož existenci nám zajišt’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. Funkce f a g splˇnují pˇredpoklady lemmatu 4.2.1 a tedy f (n) je cˇ asovˇe konstruovatelná.

(4.6)

Vˇ eta 4.2.3 — O ekvivalenci definic 4.1.3 a 4.1.5.

Funkce f : N → N je prostorovˇe kontruovatelná právˇe, když f je vyˇcíslitelná v prostoru O( f ). Proof. Implikace zleva doprava je zˇremá. 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íˇcko na pracovní pásce, napíše jeden symbol. Stroj musí rozlišovat p˚uvodní a nový symbol pro prázdné políˇcko. Nový stroj vyˇcísluje f v protoru O( f ).

Chapter 4. Konstruovatelnost funkcí

24

Necht’ M je k-páskový deterministický Turing˚uv stroj vyˇcíslující f (n) v prostoru c· f (n). Podle vˇety o lineární kompresi zkonstruujeme k-páskový stroj M 0 , který vyˇcísluje f (n) v prostoru pˇresnˇe f (n). Uvˇedomte si, že M 0 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ásek na jednopáskový stroj M 00 , který již dokazuje prostorovou konstruovatelnost funkce f . Corollary 4.2.4

Každá cˇ asovˇe konstruovatelná funkce je prostorovˇe konstruovatelná. Proof. Funkce f je cˇ asovˇe konstruovatelná, tedy f je vyˇcíslitelná v cˇ ase O( f ), tím spíše je f vyˇcíslitelná v protoru O( f ) a tedy dostáváme dle pˇredchozí vˇety, že f je prostorovˇe konstruovatelná. ˇ asovˇ Vˇ eta 4.2.5 — O rychlosti rustu ˚ c e konstruovatelných funkcí.

Necht’ f : N → N je rekurzivní funkce. Potom existuje cˇ asovˇe konstruovatelná funkce g : N → N taková, že ∀n g(n) > f (n). Proof. Víme, že f je rekurzivní, tedy existuje deterministický Turing˚uv stroj M, který pro vstup 1n vydá výstup 1 f (n) . Definujeme g(n) jako poˇcet krok˚u stroje M nad vstupem 1n zvˇetšený o jedna. Je zˇrejmé, že f (n) < g(n) a g(n) je cˇ asovˇe konstruovatelná (samotný M tuto vlastnost pˇrímo dokazuje).

ˇ Casová hierarchie Prostorová hierarchie Vˇ ety o hierarchii Prostorová hierarchie ˇ Casová hierarchie Vztahy mezi tˇrídami složitosti Vˇ eta o vtazích mezi tˇrídami složitosti Savitchova vˇ eta Pokroˇ cilé vˇ ety o tˇrídách složitosti Vˇ eta o mezerách (Borodin) Vˇ eta o zrychlení

5. Hierarchie tˇríd složitosti

5.1

ˇ Casová hierarchie V této kapitole se budeme zabývat tˇrídami složitosti a jejich základními vlastnostmi. Nadefinujeme si, co je to rekurzivní jazyk, a podíváme se, jak se s rostoucími zdroji (ˇcasem nebo prostorem) mˇení množina jazyk˚u, které dovedeme rozpoznat. Definice 5.1.1 Jazyk L je rekurzivní, jestliže existuje deterministický Turing˚uv stroj M, který

se pro každý vstup x zastaví a který pˇrijme právˇe, když x ∈ L. A nyní si ukážeme, že bez ohledu na to, kolik cˇ asu si pro výpoˇcet dovolíme, existuje jazyk, které vyžaduje cˇ asu více. V této cˇ ásti již zaˇcínáme používat Gödelova cˇ ísla, universální Turingovy stroje a velmi cˇ asto také d˚ukazy sporem. Ten první je pomˇernˇe jednoduchý, ale vyplatí se jej poˇrádnˇe pochopit – principy v nˇem obsažené budeme používat v dalších konstrukcích. ˇ asové hierarchie shora. Vˇ eta 5.1.1 — O otevˇrenosti c

Necht’ T : N → N je rekurzivní funkce. Potom existuje rekurzivní jazyk L takový, že L∈ / DT IME(T (n)). Proof. Ukážeme konstrukci takového jazyka. Nejprve oˇcíslujeme všechny deterministické Turingovy stroje Gödelovými cˇ ísly a také oˇcíslujeme všechny ˇretˇezce nad {0, 1}. Oˇcíslování provedeme systematicky, aby bylo možno tyto ˇretˇezce generovat (zde si uvˇedomte, že ˇretˇezec nad {0, 1} sice již pˇredstavuje cˇ íslo, ale naše cˇ íslování musí být odlišné, protože r˚uzné ˇretˇezce budou pˇredstavovat stejné cˇ íslo, a to nechceme). Definujeme L = {xi : Mi nepˇrijímá xi v cˇ ase T (|xi |)}. Zde jsme použili obvyklý diagonální trik – vytvoˇrili jsme jazyk, který se nejménˇe na diagonále liší od všech jazyk˚u pˇrijímaných v cˇ ase T (n). Ukažme nejprve, že 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ždy zastaví). 2. Postupným generováním najdeme i takové, že w = xi . To lze v koneˇcném poˇctu krok˚u. 3. Uvažuji i jako Gödelovo cˇ íslo nˇejakého stroje. 4. Provedu simulaci stroje Mi nad xi po T (n) krok˚u. Slovo xi pˇrijmu v následujících pˇrípadech:

26

Chapter 5. Hierarchie tˇríd složitosti

(a) Mi zastaví po ménˇe než T (|xi |) + 1 krocích a odmítne; (b) Mi bˇeží více jak T (|xi |) + 1 krok˚u. Dovedeme tedy konstruovat stroj, který daný jazyk pˇrijímá, jazyk L je tedy rekurzivní. Zde je dobré si uvˇedomit, že v této cˇ ásti neˇrešíme cˇ asovou složitost takového stroje. Nyní ukažme, že L ∈ / DT IME(T (n)). Pro spor pˇredpokládejme, že uvedené platí, tedy L ∈ DT IME(T (n)). Potom existuje deterministický Turin˚uv stroj M, který rozpozná L v cˇ ase T (n). Necht’ i je jeho Gödelovo cˇ íslo (Mi = M). 1. xi ∈ L, potom Mi pˇrijímá xi v cˇ ase T (|xi |), z cˇ ehož plyne, že xi není pˇrijmuto strojem M, ale M = Mi . Spor. 2. xi ∈ / L, potom Mi nepˇrijímá xi v cˇ ase T (|xi |), z cˇ ehož plyne, že xi je pˇrijmuto strojem M, ale M = Mi . Spor. Nacházíme tedy spor na diagonále (sami jsme si takto jazyk nadefinovali). Tím je vˇeta dokázána. ˇ asová hierarchie. Corollary 5.1.2 — Nekoneˇ cná c

Existuje nekoneˇcná posloupnost funkcí T1 , T2 , . . . taková, že DT IME(T1 (n)) $ DT IME(T2 (n)) $ . . .. Proof. Necht’ je hiearchie vybudována až po DT IME(Ti (n)). Z pˇredchozí vˇety víme, že existuje rekurzivní jazyk L takový, že pro nˇej platí L ∈ / DT IME(Ti (n)). Definujeme funkci Ti+1 takovou, aby majorizovala funkci Ti a zároveˇn i dobu výpoˇctu stroje, který pˇrijímá jazyk L (necht’ je tento výpoˇcet omezen funkcí T 0 ). Tím budeme mít zaruˇceno, že DT IME(Ti (n)) ⊆ DT IME(Ti+1 (n)) a také L ∈ DT IME(Ti+1 (n)). Z faktu, že L ∈ / DT IME(Ti (n)) dostáváme ostrou inkluzi. K tomu staˇcí položit Ti+1 = max{Ti (n), T 0 (n)} a dostaneme funkci Ti+1 , která splˇnuje požadované vlastnosti.

5.2

Prostorová hierarchie Nyní si ukážeme podobná tvrzení i pro prostorové tˇrídy. Vˇ eta 5.2.1 — O otevˇrenosti prostorové hierarchie shora.

Necht’ S : N → N je rekurzivní funkce. Potom existuje rekurzivní jazyk L takový, že L∈ / DSPACE(S(n)). Proof. D˚ukaz je analogický d˚ukazu cˇ asové verze této vˇety. Definujeme L = {xi : Mi nepˇrijímá xi v prostoru S(|xi |)}. Rozdíl oproti cˇ asové verzi je v tom, že stroj Mi nyní m˚uže odmítnout koneˇcným výpoˇ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šetˇrit odhadem poˇctu konfigurací (na omezeném prostoru existuje koneˇcnˇe mnoho konfigurací) a pˇridáním budíku, který stroj zastaví v okamžiku, kdy poˇcet krok˚u bude vyšší než poˇcet konfigurací. Opˇet platí, že taková simulace, která pracuje s odhadem poˇctu konfigurací, bude výraznˇe delší a cˇ asovˇe nároˇcnˇejší. To zde ale v˚ubec nevadí, náš stroj simulující výpoˇcet nemá žádné požadavky na efektivitu. Corollary 5.2.2 — Nekoneˇ cná prostorová hierarchie.

Existuje nekoneˇcná posloupnost funkcí S1 , S2 , . . . taková, že DSPACE(S1 (n)) $ DSPACE(S2 (n)) $ . . .. Proof. Analogicky jako v pˇrípadˇe cˇ asové hierarchie.

5.3 Vˇ ety o hierarchii

5.3 5.3.1

27

Vˇ ety o hierarchii Prostorová hierarchie Jako první vˇetu popisující vztahy v hierarchii tˇríd složitosti si dokážeme, že v pˇrípadˇe, že našemu výpoˇctu dovolíme „ostˇre“ více prostoru, dovede pˇrijmout alespoˇn jeden jazyk, které v menším prostoru rozpoznat nešel. Vˇ eta 5.3.1 — O prostorové hierarchii.

Necht’ S1 : N → N a S2 : N → N jsou funkce takové, že S2 ∈ ω(S1 ) a S2 je prostorovˇe konstruovatelná. Potom existuje jazyk L takový, že L ∈ DSPACE(S2 (n)) \ DSPACE(S1 (n)). Proof. Naším cílem bude zkonstruovat deterministický Turing˚uv stroj pracující v prostoru S2 (n), který se od každého stroje pracujícího v prostoru S1 (n) liší alespoˇn na jednom vstupu. Prefixovˇe si oˇcíslujeme všechny jednopáskové stroje nad abecedou {0, 1}. Pˇripomeˇnme, že prefixové cˇ íslování znamená, že každý stroj má nekoneˇcnˇe Gödelových cˇ ísel, která neomezenˇe rostou. M˚užeme tedy v našem d˚ukazu pracovat s indexem (Gödelovým cˇ íslem) takové velikosti, jakou budeme potˇrebovat. Popíšeme práci M na vstupu w, |w| = n. V první fázi si M oznaˇcí S2 (n) bunˇek na pracovní pásce. Dojde-li v dalších fázích k opuštˇení vymezeného prostoru, stroj se zastaví a odmítne. V druhé fázi M simuluje Mw a pˇrijme, pokud Mw odmítne w a neopustí pˇritom vymezený prostor. Platí L ∈ DSPACE(S2 (n)) a L ∈ / DSPACE(S1 (n)). První vztah je zˇrejmý, ukážeme druhý (sporem). Necht’ pro spor L ∈ DSPACE(S1 (n)), potom existuje deterministický Turing˚uv stroj M 0 takový, že L(M 0 ) = L(M). M 0 má velikost pracovní abecedy t a pracuje v prostoru S1 (n). Bez újmy na obecnosti m˚užeme pˇredpokládat, že M 0 se vždy zastaví a je jednopáskový. P

Kdyby M 0 nemˇel požadované vlastnosti, lze jej modifiovat tak, že bude schopen rozpoznat nekoneˇcný cyklus (pomocí horního odhadu na poˇcet konfigurací). Poˇcet možných konfigurací je s · (n + 1) · S1 (n) · t S1 (n) , kde s je poˇcet stav˚u a t je poˇcet páskových symbol˚u. Tento poˇcet lze odhadnout jako cS1 (n) pro vhodnou konstantu c. Uloží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žných konfigurací, odmítne. Podle vˇety o redukci poˇctu pásek dotáváme jednopáskový stroj s požadovanými vlastnostmi.

K simulaci M 0 potˇrebujeme dlog2 te · S1 (n) prostoru. Vzhledem k volbˇe prefixového cˇ íslování stroj˚u m˚užeme zvolit w tak, že kóduje stejný stroj, ale souˇcasnˇe platí dlog2 te · S1 (|w|) ≤ S2 (|w|). To jistˇe lze, nebot’ S2 roste rychleji než S1 . Pakliže stroj M 0 pˇrijímá w, potom w ∈ L(M 0 ) = L(M), ale dle definice stroje M platí w ∈ / L(M). Jestliže naopak M 0 odmítne w, potom w ∈ / L(M 0 ) = L(M), ale M 0 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∈ / DSPACE(S1 (n)). 5.3.2

ˇ Casová hierarchie Dále si ukážeme, že v pˇrípadˇe, že našemu výpoˇctu dovolíme „ostˇre“ více cˇ asu, dovede pˇrijmout alespoˇn jeden jazyk, které v kratším cˇ ase rozpoznat nešel. ˇ asové hierarchii. Vˇ eta 5.3.2 — O c

Necht’ T1 : N → N a T2 : N → N jsou funkce takové, že T2 ∈ ω(T1 · log T1 ) a T2 je cˇ asovˇe konstruovatelná.


28

Potom existuje jazyk L takový, že L ∈ DT IME(T2 (n)) \ DT IME(T1 (n)). Proof. Naším cílem bude zkonstruovat deterministický Turing˚uv stroj M pracující v cˇ ase T2 (n), který se od každého stroje pracujícího v cˇ ase T1 (n) liší alespoˇn na jednom vstupu. Prefixovˇe si oˇcíslujeme všechny dvoupáskové stroje. Všimnˇete si, že oproti prostorové verzi této vˇety budeme pracovat s dvoupáskovými stroji. Práce M na vstupu w, kde |w| = n. 1. Na dvou páskách simuluje práci stroje Mw . 2. Na dalších páskách stopuje T2 (n) krok˚u. To jistˇe lze, nebot’ T2 je cˇ asovˇe konstruovatelná. 3. M pˇrijme, pokud simulace skonˇcí nejvýše v T2 (n) krocích odmítnutím w. Oznaˇcme L = L(M). Ukážeme, že L ∈ DT IME(T2 (n)) \ DT IME(T1 (n)). Použitím cˇ ítaˇce krok˚u máme zajištˇeno, že L ∈ DT IME(T2 (n)). Ukažme tedy, že L ∈ / DT IME(T1 (n)). D˚ukaz budeme dˇelat sporem. Pˇredpokládejme, že existuje stroj M 0 takový, že M 0 pˇrijímá L v cˇ ase T1 (n). Potom existuje podle vˇety o redukci poˇctu pásek stroj M 00 , který má dvˇe pásky a pˇrijímá L v cˇ ase T1 (n)·log2 T1 (n) Necht’ pásková 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ödelovo 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á M dostatek cˇ asu k simulaci M 00 (trik byl v tom, že jsme právˇe zvˇetšili vstup stroje, pˇrestože stroj bude poˇcítat totéž – pouze na to bude mít více cˇ asu). Rozlišme dva pˇrípady: 1. Mw (což je stroj M 00 ) pˇrijímá w, potom (a) w ∈ L, protože L = L(M) = L(M 00 ), (b) w ∈ / L, protože M odmítne w, když jej Mw pˇrijme. 2. Mw odmítá w, potom (a) w ∈ / L, protože L = L(M) = L(M 00 ), (b) w ∈ L, protože M pˇrijme w, když jej Mw odmítne. Spor s pˇredpokladem, že L ∈ DT IME(T1 (n)). Vˇeta je dokázána. Znova a pomalu... fdsf sdf sdaf sadf asdf sad

5.4 5.4.1

Vztahy mezi tˇrídami složitosti Vˇ eta o vtazích mezi tˇrídami složitosti Vˇ eta 5.4.1 — O vztazích mezi tˇrídami složitosti.

a) DT IME( f (n)) ⊆ NT IME( f (n)) DSPACE( f (n)) ⊆ NSPACE( f (n)) b) DT IME( f (n)) ⊆ DSPACE( f (n)) c) L ∈ DSPACE( f (n)) a f (n) ≥ log2 n, potom ∃cL : L ∈ DT IME(cL f (n) ), kde cL je konstanta závislá na L d) L ∈ NT IME( f (n)), potom ∃cL : L ∈ DT IME(cL f (n) ), kde cL je konstanta závislá na L Proof. a) Triviálnˇe platí. b) Z vˇet o lineární kompresi a o redukci poˇctu pásek.

5.4 Vztahy mezi tˇrídami složitosti

29

c) Zde dokazujeme, že exponenciální cˇ as je dostateˇcný jako náhrada za prostor. Pˇredpoklad, že f (n) > log2 (n) je nutný, protože cˇ asová složitost nem˚uže být nižší než lineární (stroj musí mít cˇ as pˇreˇcíst vstup). Necht’ M je jednopáskový stroj dokazující L ∈ DSPACE( f (n)). Poˇcet jeho konfigurací je omezen s · (n + 1) · ( f (n) + 1) · t f (n) ≤ d f (n) , pro vhodné d (s je poˇcet stav˚u, t je poˇcet páskových symbol˚u). Zkonstruujeme M 0 , který simuluje stroj M a nejvýše po d f (n) krocích se zastaví. (Potˇrebujeme pˇredpoklad cˇ asové konstruovatelnosti funkce f .) d) Zde naopak dokazujeme, že exponenciální cˇ as je dostateˇcný jako náhrada za nedeterminismus. Pˇredpoklad, že f (n) > log2 (n) zde není nutný, protože cˇ asová složitost nem˚uže být nižší než lineární (stroj musí mít cˇ as pˇreˇcíst vstup) již na stranˇe nedeterministického stroje. Necht’ M je nedeterministický k-páskový stroj, který dokazuje, že L ∈ NT IME( f (n)). Poˇcet jeho konfigurací je omezen s · ( f (n) + 1)k · t k· f (n) ≤ d f (n) , pro vhodné d (s je poˇcet stav˚u, t je poˇcet páskových symbol˚u). Zkonstruujeme deterministický M 0 takový, že vygeneruje seznam všech konfigurací dosažitelných z poˇcáteˇcní konfigurace (napˇríklad pr˚uchodem stromu výpoˇctu M). Generování seznamu lze provést v cˇ ase kvadratickém vzhledem k délce výsledného seznamu. Tato délka je omezena souˇcinem poˇctu 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ˇcet krok˚u je omezen c2· f (n) . Vˇ eta 5.4.2 — Rozšíˇrení vˇ ety o vztazích.

b’) NT IME( f (n)) ⊆ NSPACE( f (n)) c’) L ∈ NSPACE( f (n)) a f (n) ≥ log2 n, potom ∃cL : L ∈ DT IME(cL f (n) ), kde cL je konstanta závislá na L Proof. b’) Na pomocné pásce kódujeme aktuální pr˚uchod stromem výpoˇctu. Jednotlivé kódy m˚užeme systematicky generovat, (1, 1, . . . , 1) až (r, r, . . . , r), kde r je maximální stupeˇn vˇetvení. Vlastní simulaci jedné vˇetve výpoˇctu lze provést v prostoru f (n), na uložení 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ž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. |V (G)| ≤ d f (n)

(5.1)

|E(G)| ≤ c · d f (n)

Omezení poˇctu hran plyne z faktu, že zmˇeny v konfiguraci po jednom kroku jsou pouze lokální, tedy každá konfigurace má pouze konstatní poˇcet soused˚u. Na pracovní pásku vygenerujeme seznam všech konfigurací, to zabere cˇ 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ˇení, který z vrchol˚u byl již navštíven, potˇrebuje cˇ as úmˇerný délce dosavadního výpoˇctu. Stroj tedy pracuje v cˇ ase poˇcet vrchol˚u · zkopírování pˇríslušné konfigurace na pracovní pásku. T (n) = |V (G)|q f (n) + |E(G)d f (n) q f (n)| = f (n)

= q f (n)(d f (n) + kd f (n) d f (n) ) ≤ h(d 2 ) f (n) ≤ cL

(5.2)


30

Najde-li stroj pˇri pr˚uchodu grafem pˇrijímající konfiguraci, je tato dosažitelná z iniciální konfigurace a stroj pˇrijme.

5.5

Savitchova vˇ eta Již jsme si ukázali, že na odstranˇení nedeterminismu je v pˇrípadˇe cˇ asové složitosti potˇreba exponenciální cˇ as (jedná se o horní odhad). Nyní si ukážeme, že v pˇrípadˇe prostorové složitosti nám bude staˇcit druhá mocnina. Opˇet se ukazuje, že prostor je „jednodušší“ zdroj. Vˇeta se jmenuje podle Waltera Johna Savitche, který ji dokázal v roce 1970. Vˇ eta 5.5.1 — Savitchova.

Necht’ S : N → N je prostorovˇe konstruovatelná funkce, pro kterou platí S(n) ≥ log2 n. Potom NSPACE(S(n)) ⊆ DSPACE(S2 (n)). Proof. Necht’ M1 je nedeterministický Turing˚uv stroj pˇrijímající jazyk L v prostoru S(n), potom existuje konstanta cL taková, že M1 má nejvýše cL S(n) konfigurací. Pokud M1 pˇrijímá w, pak existuje posloupnost nejvýše 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ž nebo pˇresnˇe 2i krok˚u. Test staˇcí provádˇet pro i ≤ S(n) · log cL = m · S(n). Popišme zp˚usob rozhodování, že 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ásky - c0 · S(n), kde c0 = log2 t, t je poˇcet páskových 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ý pro jednu kopii procedury TEST je O(S(n)). Celá simulace potom probíhá tak, že pro všechny pˇrijímající stavy I j voláme proceduru T EST (I0 , I j , 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žení parametr˚u procedur TEST. V každý okamžik je na zásobníku O(S(n)) záznam˚u. Deterministrický stroj simulující M1 pracuje v prostoru O(S2 (n)) a pˇrijímá jazyk L.

5.6

Pokroˇ cilé vˇ ety o tˇrídách složitosti

5.6 Pokroˇ cilé vˇ ety o tˇrídách složitosti

31

Lemma 5.6.1 — 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 NSPACE(S1 (n)) ⊆ NSPACE(S2 (n)) ⇒ NSPACE(S1 ( f (n))) ⊆ NSPACE(S2 ( f (n))). Proof. Necht’ L1 ∈ NSPACE(S1 ( f (n))) a necht’ M1 je stroj, který to ukazuje. Sestrojíme jazyk L2 , který bude patˇrit do NSPACE(S1 (n)). Necht’ L2 = {x$i |M1 pˇrijímá x v prostoru S1 (|x| + i)}. Zˇrejmˇe pro všechna i taková, že |x| + i ≥ f (|x|), platí x ∈ L1 ⇔ x$i ∈ L2 . Tento argument se nazývá padding argument. Jde o to zvˇetšit délku slova bez pˇridání nové informace, cˇ ímž se stroji, který nad slovem pracuje, poskytne více prostoru (pˇrípadnˇe cˇ asu). 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ále pokraˇcuje M2 simulací stroje M1 a pˇrijme právˇe tehdy, pokud pˇrijme M1 a neopustí pˇritom vyznaˇcený prostor. M2 zˇrejmˇe pracuje v prostoru S1 (n), tedy L ∈ NSPACE(S1 (n)). Navíc platí x ∈ L1 ⇔ ∃i < f (|x|) : x$i ∈ L2 . Jinými slovy, existuje i takové, že stroj M1 bude mít dost prostoru pro pˇrijetí v prostoru S1 (|x| + i). Protože podle pˇredpokladu platí NSPACE(S1 (n)) ⊆ NSPACE(S2 (n)), dostáváme, že existuje nedeterministický Turing˚uv stroj M3 , který pˇrijímá L2 v prostoru S2 (n). Nyní sestrojíme M4 , který pˇrijímá L1 v prostoru S2 ( f (n)). Popis práce M4 nad vstupem x. • Na p˚ulené pracovní pásce 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ž používá horní stopu jako vstup. To lze, nebot’ f i S2 jsou prostorovˇe konstruovatelné. Protože 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, že 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ána na zvláštní pracovní pásce M4 . • Poˇcítadlo nepustí vstupní hlavu M3 za pozici, kdy už by cˇ ítaˇc pˇretekl z prostoru S2 ( f (|x|)), tedy i ≤ 2S2 ( f (|x|)) , nebot’ v prostoru S2 ( f (|x|)) m˚uže poˇcítadlo binárnˇe poˇcítat až do 2S2 ( f (|x|)) . • M4 pˇrijme x právˇe, když M3 pˇrijme. Platí: x ∈ L1 ⇔ ∃i < f (|x|) : x$i ∈ L2 = L(M3 ). Víme ale, že S2 (n) ≥ n, tedy S2 ( f (|x|)) ≥ f (|x|), z cˇ ehož dostáváme 2S2 ( f (|x|)) ≥ f (|x|). Již dˇríve jsme ukázali, že staˇcí i ≤ f (|x|), tedy naše simulace umožˇnuje zkoušet dostateˇcnˇe velká i. Tedy i je dostateˇcnˇe velké. Na závˇer dostáváme x ∈ L(M4 ) ⇔ x$i ∈ L(M3 ) ⇔ x ∈ L1 a tedy L1 ∈ NSPACE(S2 ( f (n))). Vˇ eta 5.6.2 — O nedeterministické prostorové hierarchii.

Necht’ ε > 0 a r ≥ 1, potom NSPACE(nr ) $ NSPACE(nr+ε ). Proof. Díky hustotˇe racionálních cˇ ísel víme, že ∀r ∀ε ∃s,t ∈ N : r ≤

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

(5.3)

Ukážeme, že NSPACE(ns/t ) $ NSPACE(n(s+1)/t ). D˚ukaz provedeme sporem. Necht’ tedy NSPACE(n(s+1)/t ) ⊆ NSPACE(ns/t ). Použijeme (s + 1)-krát translaˇcní lemma, postupnˇe pro


32 funkce f (n) = n(s+i)t pro i = 0, . . . , s.

2

NSPACE(n(s+1)s ) ⊆ NSPACE(ns )

i=0

(s+1)(s+1)

) ⊆ NSPACE(n

s(s+1)

(5.4)

i=1

NSPACE(n

i=2 .. .

NSPACE(n(s+1)(s+2) ) ⊆ NSPACE(ns(s+2) )

i = s−1

)

NSPACE(n(s+1)(2s−1) ) ⊆ NSPACE(ns(2s−1) ) NSPACE(n(s+1)(2s) ) ⊆ NSPACE(ns(2s) )

i=s

Pravá strana každé inkluze je vnoˇrená do levé strany inkluze pro i o jedniˇcku menší. Dostaneme prostým porovnáním exponent˚u u n. Zˇretˇezením dostaneme 2

2

NSPACE(n(s+1)(2s) ) ⊆ NSPACE(ns ) ⊆ DSPACE(n2s ) $ 2s2 +2s

$ DSPACE(n

) ⊆ NSPACE(n(s+1)(2s) ).

(5.5) (5.6)

Uvedené schéma vede ke sporu, nebot’ vpravo i vlevo je stejná tˇrída a uprostˇred je ostrá inkluze. Definice 5.6.1

Tvrzení parametrizované cˇ íslem n je pravdivé skoro všude, platí-li na všech kromˇe koneˇcnˇe mnoha n. Tvrzení parametrizované cˇ íslem n je pravdivé nekoneˇcnˇe cˇ asto, platí-li na nekoneˇcnˇe mnoha n. Lemma 5.6.3

Necht’ L je jazyk pˇrijímaný deterministickým Turingovým strojem s prostorovou složitostí S(n) skoro všude. Potom L je pˇrijímaný jiným strojem M 0 s prostorovou složitostí S(n). Proof. Koneˇcnˇe mnoho výjimek, kde výpoˇcet pˇresáhne S(n) ošetˇríme pomocí tabulky. Takový stroj ale nelze efektivnˇe sestrojit, protože nedokážeme vyjímky identifikovat. Lemma 5.6.4

Necht’ je dán deterministický Turing˚uv stroj M, délka vstupu n a cˇ íslo m. Existuje algoritmus zjišt’ující, zda m je maximální poˇcet použitých bunˇek na pracovních páskách pˇri práci M na vstupech délky n. Algoritmus vždy skonˇcí. Proof. Staˇcí simulovat výpoˇcet M a poˇcítat kroky pro detekci pˇrípadných nekoneˇcných smyˇcek (pˇrekroˇcení poˇctu možných konfigurací). 5.6.1

Vˇ eta o mezerách (Borodin) Už máme dokázané vˇety hierarchii, které nám ˇríkají, že hierarchie je neomezená a že pro libovolnou rekurzivní funkci dovedeme definovat jazyk, na který tato funkce dává málo cˇ asu (vˇeta 5.1.1). Nyní si ukážeme možná trochu ménˇe intuitivní výsledek. Pro libovolnou rekurzivní funkci g(n) rostoucí alespoˇn lineárnˇe existuje rekurzivní funkce S(n), kterou lze „nafouknout“ funkcí g a pˇresto nám to nepˇridá žádnou výpoˇcetní sílu. Vˇeta se jmenuje o mezerách, protože tvrzení vlastnˇe ˇríká, že když bude nepˇrítel požadovat mezeru mezi tˇrídami složitosti o nˇejaké velikosti


33

(a tu velikost bude schopen efektivnˇe vyˇcíslovat), dovedeme najít takovou tˇrídu složitosti, kde rozšíˇrení povoleného cˇ asu o stanovou mezeru nepovede k pˇrijmutí jednoho jediného jazyka navíc. Je dobré si uvˇedomit, že tento výsledek je velmi silný, nebot’ na rychlost r˚ustu g(n) neklademe skoro žádná omezení – m˚užeme dovolit dvojnásobek cˇ asu, šestou mocninu cˇ asu, faktoriál cˇ asu, faktoriál faktoriálu cˇ asu a tak podobnˇe. Jediným, a ve svém d˚usledku velmi silným omezením z˚ustává požadavek rekurzivnosti funkce. Nyní formálnˇe. Vˇ eta 5.6.5 — Borodinova, o mezerách.

Necht’ g(n) ≥ n je rekurzivní funkce. Potom existuje rekurzivní funkce S(n) taková, že DSPACE(S(n)) = DSPACE(g(S(n))) Proof. Necht’ M1 , M2 , . . . je vhodné prefixové oˇcíslování všech deterministických stroj˚u. Oznaˇcme Si (n) = maximum použitých bunˇek stroje Mi na vstupu délky n. Pokud se Mi vždy zastaví, je Si (n) jeho prostorová složitost. Pokud se Mi na nˇejakém vstupu délky n nezastaví, je Si (n) nedefinováno (respektive rovno +∞). P

Zjistit, zda Si (n) = +∞ nelze, ale pro libovolné pevnˇe dané m lze zjistit, zda Si (n) ≤ m (viz lemma 5.6.4).

Zkonstruujeme rekurzivní funkci S(n) takovou, že pro všechna k bud’ Sk (n) ≤ S(n) skoro všude

(5.7)

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

(5.8)

nebo

Uvedené nerovnosti požadujeme, abychom zajistili: ∀k : L(Mk ) ∈ DSPACE(S(n)) ⇔ L(Mk ) ∈ DSPACE(g(S(n)))

(5.9)

Stroj Mk splˇnující 5.7 lze pomocí koneˇcnˇe mnoha výjimek zmˇenit tak, aby nerovnost platila všude podle lemma 5.6.3, a stroj splˇnující 5.8 naopak nelze pomocí koneˇcnˇe mnoha výjimek zmˇenit tak, aby platila opaˇcná nerovnost. Z 5.7 a 5.8 plyne, že neexistuje k takové, že S(n) < Sk (n) ≤ g(S(n)) skoro všude. Stroj Mk by potom pˇrijímal jazyk, který není v DSPACE(S(n)), ale je v DSPACE(g(S(n))). Tomu se chceme v konstrukci vyhnout. Popíšeme nyní konstrukci S(n) pro danou hodnotu n. Vezmeme M1 , . . . , Mn a zvolíme S(n) tak, že ∀i, 1 ≤ i ≤ n : Si (n) ≤ S(n) nebo g(S(n)) < Si (n). V pˇrípadˇe, že jsou všechna Si (n) koneˇcná, staˇcí vzít za S(n) maximum, jak bylo ale již výše uvedeno, nelze o koneˇcnosti Si (n) rozhodnout. Proto budeme problém ˇrešit "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ý, že j < Si (n) ≤ g( j) (to nám umožˇnuje lemma 5.6.4, nebot’ nyní máme horní odhad na Si (n)). Jestliže takové Mi neexistuje, m˚užeme položit S(n) = j, nebot’ žádný stroj Mi nepoˇcítá s protorovou složitostí mezi S(n) a g(S(n)). Jestliže takové Mi naopak existuje, volíme j = Si (n). Pokraˇcujeme spoˇcítáním g( j). Cyklus se zastaví nejvýše po n interacích, nebot’ v každé se jedno Si stane dolní hranicí intervalu. Takto konstruovaná funkce S(n) splˇnuje podmínky 5.7 nebo 5.8, nebot’ pro dané k byl stroj Mk uvažován pro všechna n ≥ k v množinˇe M1 , . . . , Mn pˇri konstrukci S(n). Tedy Sk (n) nebylo


34

v intervalu (S(n), g(S(n))]. Proto muselo být bud’ nekoneˇcnˇe mnohokrát nad tímto intervalem nebo skoro vždy pod. Necht’ L ∈ DSPACE(g(S(n))), potom existuje deterministický Turing˚uv stroj Mk rozpoznávající L v prostoru g(S(n)), tedy ∀n Sk (n) ≤ g(S(n)). Z konstrukce S(n) plyne, že pro n > k platí Sk (n) ≤ S(n) skoro všude. Tedy Mk pracuje v prostoru S(n) skoro všude a podle lemma 5.6.3 existuje jiný stroj, který pˇrijímá L v prostoru S(n) všude, tedy L ∈ DSPACE(S(n)). Máme DSPACE(g(S(n))) ⊆ DSPACE(S(n)). Inkluze na druhou stranu je triviální, tedy dostáváme rovnost a tvrzení vˇety je dokázáno. Znova a pomalu... A jak to, že nám staˇcí ovˇeˇrovat vlastnosti S(n) jenom do n? Vždyt’ tím

ovˇeˇrujeme jenom koneˇcný zaˇcátek, ne nekoneˇcný konec! Ve skuteˇcnosti je to takto správnˇe. Pˇredstavte si na vodorovné ose n a na svislé ose i (indexy funkcí Si (n)). Je pravda, že pro každé n jsme zkontrolovali pouze koneˇcnˇe mnoho funkcí (ve sloupci nad n jsme došli jenom na diagonálu). Jenže naše tvrzení neˇríká nic o n. Naše tvrzení je o funkcích. Tedy ne o sloupeˇccích ale o ˇrádcích. A když jdeme v ˇrádku i doprava od nuly k vyšším n, po koneˇcném úseku narazíme na diagonálu a od ní dál už byla funkce Si (n) uvažována pro všechna n > i. Tedy pro nekoneˇcný úsek. A nad diagonálou máme jenom zaˇcátek té vodorovné linie – což je to, co jsme chtˇeli. Vlastnost má platit pro funkci pˇres všechna n, ne pro jedno konkrétní n pro všechny funkce. A ještˇe jedna vˇec. Používáme trik s prefixovým cˇ íslováním, který se m˚uže zdát jako podvod. Zaˇcneme s nˇejakým strojem, pak ale udˇeláme mentální trik s prefixem a najednou je na všechno dost místa. Zde je potˇreba si uvˇedomit, že nás d˚ukaz není konstruktivní. My nehledáme konkrétní stroj, konkrétní index. My dokazujeme jeho existenci, nemusíme mít algoritmus, jak jej najít. A z prefixového cˇ íslování plyne, že takový stroj m˚uže mít Gödelovo cˇ íslo dostateˇcnˇe dlouhé. Je to naše volba, jak budeme stroje cˇ íslovat – d˚uležité je, že existuje stroj, který má urˇcité vlastnosti a jehož index má urˇcité vlastnosti. Nemusíme znát algoritmus, jak tento stroj nebo jeho index najít a popsat. (To cˇ asto nemusí být možné z d˚uvodu nerešitelnosti problému zastavení.) 5.6.2

Vˇ eta o zrychlení Vˇ eta 5.6.6 — Bloomova, o zrychlení – prostorová verze.

Necht’ r(n) je rekurzivní funkce. Potom existuje rekurzivní jazyk L takový, že pro každý deterministický Turing˚uv stroj Mi rozpoznávající L v prostoru Si (n) existuje deterministický Turing˚uv stroj M j rozpoznávající L v prostoru S j (n), kde r(S j (n)) ≤ Si (n) skoro všude. Než pˇristoupíme k samotnému d˚ukazu vˇety, uvedeme si dvˇe pomocná tvrzení. Lemma 5.6.7

Bez újmy na obecnosti m˚užeme pˇredpokládat, že funkce r je neklesající a prostorovˇe konstruovatelná. Navíc platí r(n) ≥ n2 . Proof. Pokud r(n) nesplˇnuje uvedené požadavky, definujeme r0 (n) = max{poˇcet bunˇek použitých k výpoˇctu r(1), . . . , r(n), n2 }

(5.10)

Je zˇrejmé, že 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).


35

Lemma 5.6.8

Definujeme-li h(n) = r(h(n − 1)), h(1) = 2, platí, že h(n) je prostorovˇe konstruovatelná. Proof. Plyne z prostorové konstruovatelnosti r(n).

Proof. Necht’ M1 , M2 , . . . jsou oˇcíslované deterministické Turingovy stroje s jednoprvkovou vstupní abecedou. Dále budeme pˇredpokládat, že délka zakódování stroje Mi je nejvýše log2 i (bez d˚ukazu). Zkonstruujeme jazyk L takový, že 1) pokud stroj Mi rozpoznává L, pak Si (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(Mi ) = 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 Si (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) 6= j} Pokud je σ (n) definováno, ˇrekneme, že stroj Mσ (n) je zrušen cˇ íslem n. V jednom kroku konstrukce uvažuji pevnˇe dané n a množinu tˇech stroj˚u, které nebyly zrušeny žádným k, k < n. Tato množina je v každém kroku konstrukce koneˇcná. 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ˇcím, aby žádný zrušený stroj nepˇrijímal jazyk L: 0n ∈ L ⇔ σ (n) je definované a Mσ (n) nepˇrijímá On Ukažme, že L splˇnuje obˇe uvedené podmínky. Necht’ i je takové, že L(Mi ) = L a uvažujme stroje M1 , . . . , Mi−1 . Nˇekteré z tˇechto stroj˚u jsou zrušeny, každý je zrušený nˇejakým 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ážeme sporem. Necht’ ∃n > max{n0 , i} : Si (n) < h(n − i), potom je ale splnˇena podmínka pro zrušení Mi a tedy L(Mi ) 6= L. Tedy podmínka 1 je splnˇena. Ukažme dále, že L splˇnuje 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 0n patˇrí do L, potˇrebovat prostor nejvýše h(n − k) skoro všude. Pro vstup On musí M j : 1) zjistit, zda je σ (n) definováno a pokud ano, tak σ (n) spoˇcítat, 2) po zjištˇ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šeny nˇejakým cˇ íslem l < n. Pro pevné i a l staˇcí pracovat v prostoru h(l − i), protože pokud cˇ íslo l zruší stroj Mi , tak Si (l) ≤ h(l − i). Pro vymezení uvedeného množství prostoru potˇrebujeme, aby byla h prostorovˇe konstruovatelná. Zde se ovšem objeví problém v pˇrípadˇe, že l − i > n − k, protože potom se simulace do vymezeného prostoru nevejde. Problém obejdeme drobný trikem. Uvažujme M1 , . . . , Mk a necht’ n1 je nejvˇetší cˇ íslo, kterým je nˇekterý z tˇechto stroj˚u zrušen. Modifikujeme M tak, že ∀l ≤ n1 bude ˇrídící jednotka obsahovat informace o tom, zda Ol ∈ L a cˇ íslo stroje zrušeného cˇ íslem l, pokud takový existuje. Potom ∀n ≤ n1 pracuje M s nulovou prostorovou složitostí, 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že l ≤ n a i ≥ k. Tedy stroj Mi se do uvedeného prostoru vejde, ještˇe je tˇreba ukázat, že se do nˇej vejde i stroj M pˇri simulaci Mi . Pro n > n1 , je-li definováno σ (n), tak σ (n) je alespoˇn k, tedy Mσ (n) na vstupu On pracuje v prostoru h(n − σ (n)), což je nejvýše h(n − k), protože σ (n) > k.

36


M postupnˇe simuluje stroje Mi pro k + 1 ≤ i ≤ n na vstupech 0l pro l ≤ n. Pro každou dvojici (i, l) staˇcí reprezentovat na stroji h(l − i) bunˇek stroje Mi . i ≤ n, Mi je zakódován v nejvýše log2 i ≤ log2 n buˇnkách stroje M, tedy tím spíše libovolný symbol stroje Mi lze zakódovat v log2 n symbolech stroje M. x−2 Protože víme, že r(x) ≥ x2 , platí h(x) ≥ 22 (d˚ukaz lze indukcí). n−k−2 Tedy h(n − k) ≥ 22 ≥ log2 n skoro všude, tedy prostor h(n − k) staˇcí pro simulaci Mi pro skoro všechna n. Kromˇe místa na simulaci potˇrebuje M také prostor na ukládání seznamu zrušených stroj˚u. Zrušených stroj˚u je nejvýše n, tedy je potˇreba nejvýše n · log2 n místa. Platí n · log2 n ≤ n2 ≤ h(n − k) skoro všude. M tedy pracuje v prostoru 2h(n − k) skoro všude, dle lemma 5.6.3 existuje M 0 pracující v prostoru 2h(n − k) všude a podle vˇety o kompresi existuje stroj M 00 , který pracuje v prostoru h(n − k) všude.

Index

Gödelovo cˇ íslo, 8 Nedeterminismus, 11 prefixové cˇ íslování, 9 Prostorová komprese, 13 Redukce poˇctu pásek, 14 Složitost cˇ asová, 11 nedeterministická, 11 prostorová, 11 Tˇrídy složitosti, 11 Turing˚uv stroj, 7 deterministický, 7 indexování, 8 nedeterministický, 11

Složitost a NP-úplnost. Ladislav Strojil podle přednášek RNDr. O. Čepka, Ph.D

Recommend Documents