Složitost II

Složitost II

Kód předmětu: NTIN063 Přednáší: Ondřej Čepek

Zápočet

Kdo složí zkoušku získá automaticky i zápočet.

Poznámky

Toto je zatím neúplná verze poznámek, které jsem psal tak jak jsem se učil na zkoušku. Jak se ale blížil zkouškový termín bylo stále méně času, proto zůstaly nedokončeny. --Maker 19:08, 14 Jun 2005 (CEST)

Doplnil jsem co jsem stihl. Dost toho tu ještě chybí. Přidal jsem osnovu co asi dodělat. --Jirja 20:14, 23 Jun 2005 (CEST)

Viz též státnicový okruh Složitost.

Definice potřebných výpočetních modelů

Turingův stroj

Definice z Wikipedie

• Pro účely přednášky jsme rozuměli turingovým strojem pouze pětici (blank symbol se neuvádí).
• Pokud šlo ale o počítání použitého prostoru, záváděl se spec. blank symbol

Časová a prostorová složitost

• Prostorová složitost - Nechť M je DTS takový, že $ \forall w \in \Sigma^* ; |w| = n $ použije M při výpočtu nad vstupem $ w $ nejvýše S(n) buněk na pracovních páskách. Potom říkámě, že M má prostorovou složitost S(n) a že jazyk L(M) má prostorovou složitost S(n).
• Časová složitost - Nechť M je DTS takový, že $ \forall w \in \Sigma^* ; |w| = n $ udělá M při výpočtu nad vstupem $ w $ nejvýše T(n) kroků než se zastaví. Potom říkámě, že M má časovou složitost T(n) a že jazyk L(M) má časovou složitost T(n).
• Počet konfigurací v prostoru $ S(n) $ je: $ |Q|*(n+1)*(S(n)+1)^k*t^{k*S(n)} $
  • $ |Q| $ ...počet stavů
  • $ (n+1) $ ...počet pozic hlavy na vstupní pásce
  • $ (S(n)+1)^k $ ...k je počet pásek, tedy celkem počet různých pozic
  • $ t^{k*S(n)} $ ...k je počet pásek, t je počet páskových symbolů, tedy celkem počet různých obsahů pásek v prostoru S(n)
  • |Q|, t, k konstanty, a pokud $ S(n)\geq log(n) $, lze celý výraz odhadnout $ c^{S(n)} $

Věty o TS a třídách složitosti

Věta (o lineární prostorové kompresi)

Nechť je jazyk L přijímaný (k+1)-páskovým (1 vstupní, k pracovních) DTS M s prostorovou složitostí S(n). Pak $ \forall r \in \mathbb{N}^+ $ existuje (k+1)-páskový DTS M' přijímající L s prostorovou složitostí $ \lceil S(n)/r \rceil $.

Důkaz:

Zkusme M' postavit. Jeden znak nového stroje kóduje r znaků původního. Jeden krok nového stroje odpovídá jednomu kroku původního. Pozici původního stroje v rámci "multiznaku" nového stroje evidujeme ve stavech.

Nechť k = 1. Každý původní stav nahraďme r novými stavy. $ Q_M = \{q_0, ... q_s \}, Q_{M'} = \{q_0^1, ... q_0^r, ... q_s^1, ... q_s^r \} $.

Přechodová funkce simuluje pohyb původního stroje přechodem ke stavu s jiným horním indexem. Až po "vyjetí" z multiznaku provede skutečný pohyb.

Pravidla stroje M tvaru $ \delta (q_i, a) = (q_j, b, N) $ nahradíme množinou $ \delta (q_i^l, x) = (q_j^l, y, N) $ pro všechna $ l \in [1..r] $ a všechny "multiznaky" x = (.. a ..), y = (.. b ..), které jsou totožné až na l-tý znak (tím je právě a, b).

Pravidla stroje M tvaru $ \delta (q_i, a) = (q_j, b, R) $ nahradíme množinou $ \delta (q_i^l, x) = (q_j^{l+1}, y, N) $ pro l < r, $ \delta (q_i^l, x) = (q_j^{1}, y, R) $ pro l = r.

Pravidla stroje M tvaru $ \delta (q_i, a) = (q_j, b, L) $ nahradíme množinou $ \delta (q_i^l, x) = (q_j^{l-1}, y, N) $ pro l > 1, $ \delta (q_i^l, x) = (q_j^{r}, y, L) $ pro l = 1.

Pro obecné k dostaneme $ Q_{M'} = \{q_i^{(p_1, ... p_k)} | 0 \leq i \leq s, 1 \leq p_j \leq r \} $ (horní index je pozice hlavy uvnitř "multiznaku" na každé pásce). Obdobně zobecníme přechodovou funkci. Při konstrukci M' tedy vzrostla velikost abecedy (exponenciálně vůči r), vzrostl počet stavů a velikost přechodové funkce. Časová složitost se zůstala stejná. Prostorová složitost se však lineárně zmenšila.

Důsledek: $ DSPACE(S(n)) = DSPACE(S(n)/r) $

Poznámka: lze upravit i pro NTS.

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

Nechť L je jazyk přijímaný k-páskovým DTS M s prostorovou složitostí S(n). Potom existuje DTS M' s jednou pracovní páskou a prostorovou složitostí S(n) přijímajicí L.

Důkaz:

i-té políčko nové pásky kóduje obsah i-tých políček původních k pásek. Navíc kóduje, jaká hlava původního stroje se nad ním nachází (na i-té pozici). Nová abeceda je tedy $ \Sigma_{M'} = \{x_0, ..., x_{2^k-1} | x = (a_0, ... a_k), a_i \in \Sigma_{M}\} $, x představuje k-tici znaků na původních páskách, dolní index při binárním zápisu představuje k-tici "příznaků" - které hlavy se zde nachází.

Krok stroje M je simulován až v S(n) krocích M'. Nový stroj projde celou pásku, zjistí pozice hlav a odsimuluje krok M. Jelikož nám nezáleží na čase, můžeme to ještě rozdělit do k fází, v každé fázi se odsimuluje práce na 1 pásce. Na začátku a na konci fáze bude hlava M' na začátku své pásky.

Do nových stavů zakódujeme instrukce M. V každém stavu M' pak bude jasné, jakou instrukci M se snažíme provést. Do nových stavů zakódujeme i číslo aktuální fáze.

TODO.

Poznámka: Důkaz lze upravit i pro NTS.

Lemma (o lineárním zrychlení)

Nechť jazyk L je přijímaný k-páskovým DTS M s časovou složitostí T(n), kde k ≥ 2 a r ≥ 1 je přirozené číslo. Potom existuje k-páskový DTS M' takový, že pro každý vstup w délky n přijímá právě když jej přijímá M. Pracuje-li M nad w t kroků, pracuje M' nad w v čase $ n+ \left \lceil \frac{n}{r} \right \rceil+6 \cdot \left \lceil \frac{t}{r} \right \rceil $.

Důkaz:

Pracovní pásky nového stroje budou "nahuštěné", jedna buňka představuje r buněk původního stroje. V první fázi M' přečte vstupní pásku a "zakóduje" ji do první pracovní pásky, s tou se dále pracuje jako se vstupní. "Jemné" umístění uvnitř nové buňky kódujeme ve stavech.

Při samotné simulaci M' "načte obsah" dvou sousedních buněk (pohyb vlevo, vpravo, vpravo, vlevo, 4 kroky). Nyní chceme zjistit stav těchto políček po r krocích M. Všimněte si, že hlava M nemohla tato 3 políčka opustit. Mohla přepsat nejvýše 2 sousedící. Při posledním ze 4 kroků stroj "zjistil", jaký bude výsledek. Hlava M po r krocích mohla "při nejhorším" přepsat levé či pravé políčko (r-tici) a vrátit se na prostřední. To simulujeme dvěma kroky M'. Toto vše probíhá na více páskách současně, jako to dělá M.

První fáze výpočtu zabere $ n+ \left \lceil \frac{n}{r} \right \rceil $ kroků (přečtení vstupu + návrat na začátek). r kroků M simulujeme jednou "akcí" M', která má 6 kroků.

1. Věta (o lineárním zrychlení)

Nechť je L přijímán k-páskovým (1 vstupní, k-1 pracovních) DTS M s časovou složitostí T(n) a $ \inf_{n \rightarrow \infty} T(n)/n = \infty $ (T je "nadlineární"). Pak $ \forall c > 0 $ existuje DTS M' s k pracovními páskami a časovou složitostí $ \lceil c \cdot T(n) \rceil $, přijímající L.

Důkaz:

Vezměme r > 12/c (např. chceme stroj dvakrát zrychlit, c = 0.5, r = 25). Najdeme M' dle předchozího lemmatu. Ten pracuje nad vstupem délky n v čase $ n+ \left \lceil \frac{n}{r} \right \rceil+6 \cdot \left \lceil \frac{t}{r} \right \rceil $, což lze omezit na $ 2n + 6 + (6/r) * T(n) $.

Jelikož T je "nadlineární", výraz výše "skoro vždy" omezíme $ 2*T(n) + (6/r) * T(n) \leq (c/2)*T(n) + (6/r) * T(n) = (c/2 + 6/r) * T(n) < c * T(n) $. Konečný počet případů, kde nerovnost neplatí, ošetříme konečným automatem na začátku, který přidá konstantní počet kroků.

Důsledek: pro "nadlineární" T: $ DTIME(T(n)) = DTIME(c \cdot T(n)) $.

Poznámka: Důkaz lze upravit i pro NTS.

2. Věta (o lineárním zrychlení)

Nechť je L přijímán k-páskovým (1 vstupní, k-1 pracovních) DTS M s časovou složitostí T(n) = c*n, c>1. Pak $ \forall \epsilon > 0 $ existuje DTS M' s k pracovními páskami a časovou složitostí $ \lceil (1+\epsilon)n \rceil $, přijímající L.

Důkaz:

Chceme najít M' dle lemmatu výše, zajímá nás r. Pokud takové M' najdeme, bude pracovat v čase

• $ n+ \lceil \frac{n}{r} \rceil+6 \cdot \lceil \frac{cn}{r} \rceil $

To omezíme výrazem

• $ n+ n/r + 6cn/r + 7 = (1 + 1/n + 6c/r + 7/n) \cdot n $

který by měl být omezen $ (1+\epsilon) \cdot n $, tedy $ 1/n + 6c/r + 7/n \leq \epsilon $. Požadujeme:

• $ 1/n \leq \epsilon/3 \rightarrow r \geq 3/\epsilon $
• $ 6c/r \leq \epsilon/3 \rightarrow r \geq 18c/\epsilon $
• $ 7/n \leq \epsilon/3 \rightarrow n \geq 21/\epsilon $

Pro r použijeme silnější podmínku, tedy $ r = 18c/\epsilon $. Pro $ n \geq 21/\epsilon $ nerovnost platí, konečný počet menších n vyřešíme konečným automatem.

Důsledek: $ \forall c>1, \forall \epsilon>0 : DTIME(c\cdot n) = DTIME((1+\epsilon)\cdot n) $.

Poznámka: Důkaz lze upravit i pro NTS.

Věta (redukce počtu pásek pro časovou složitost - kvadratická)

Nechť $ inf_{n \rightarrow \infty} \frac{T(n)}{n} = \infty $ nebo $ T(n) = cn $ a c > 1. Nechť je jazyk L přijímaný k-páskovým DTS M s časovou složitostí $ T(n) $. Potom existuje DTS M' s jednou pracovní páskou a časovou složitostí $ T(n)^2 $ přijímajicí L.

Důkaz:

• Pokud platí $ inf_{n \rightarrow \infty} \frac{T(n)}{n} = \infty $, použijme 1. větu o lineárním zrychlení s $ c = \sqrt{\frac{1}{2k}} $, dostaneme M' s prostorovou složitostí S'(n). Teď použijme větu o redukci počtu pásek pro prostorovou složitost. Dostaneme nový stroj M2 s 1 pracovní páskou přijímající L. Pro každý krok M' nový stroj M2 projde svoji pásku k-krát tam a zpět, pro každou z pásek M'. M2 pracuje v čase $ T''(n) \leq 2k \cdot S'(n)\cdot T'(n) \leq 2k \cdot T'(n)^2 = T(n)^2 $.

• Pokud platí T(n) = cn s $ c > \sqrt{2k} $, zvolme $ \epsilon $ tak, že $ 1+\epsilon = \frac{c}{\sqrt{2k}} $. Pak použijme 2. větu o lineárním zrychlení a pak stejně jako v předchozím případě.

Důsledek: $ L \in NTIME(T(n)) $ pak existuje jednopáskový NTS s časovou složitostí $ (T(n))^2 $ přijímajicí L.

Poznámka: Důkaz lze upravit i pro NTS.

Věta (redukce počtu pásek pro časovou složitost - logaritmická)

Nechť L je jazyk přijímaný k-páskovým DTS M s časovou složitostí $ T(n) $. Potom existuje DTS M' se dvěma pracovními páskami a časovou složitostí $ T(n)\log_2T(n) $ přijímající L.

Důkaz:

Idea důkazu: Hlavy držím pod sebou a pohybuji daty.

Příklad uspořádání dat na jedné dvojstopě pracovní pásky. Páska původního stroje je naskládaná jak naznačuje šipka.

Popíšeme konstrukci stroje M':

• 1. Páska ma 2k stop a je rozdělena na bloky $ ..,B_{-2},B_{-1},B_0,B_1,B_2,... $ kde:
  • $ B_0 $ obsahuje jedinou buňku.
  • $ \forall i, |i| \ge 1; |B_i| = 2^{|i|-1} $
• 2. Páska je jednostopá a slouží k přesunu dat.
• Obě pásky předpokládáme oboustraně nekonečné.
• Invarianty, které platí po simulaci každého kroku stroje:
  1. $ \forall i \ge 1 $ nastává jedna z možností:
     • $ B_i $ má obě stopy plné a $ B_{-i} $ má obě stopy prázdné.
     • $ B_i $ má obě stopy prázdné a $ B_{-i} $ má obě stopy plné.
     • $ B_i,B_{-i} $ mají dolní stopu plnou a horní prázdnou.
  2. $ \forall i; B_i $ obsahuje souvislý interval pásky stroje M
     • pokud i < 0 tak horní stopa (HS) obsahuje symboly vpravo od dolní stopy (DS).
     • pokud i > 0 tak HS obsahuje symboly vlevo od DS.
     • pokud i = 0 tak symbol je pouze na DS a na HS je speciální symbol (zarážka).
  3. $ \forall i; B_i $ obsahuje interval pásky M bezprostředné vlevo od $ B_{i+1} $

Simulace jednoho kroku stroje M (na jedné pásce - ostatní jsou stejné):

• Změna symbolu na pásce a změna řídícího stavu jsou zřejmé.
• Pro posun hlavy je třeba posunout data na pásce (BÚNO pohyb doleva):

1. Hlava na 1.pásce M' jede od $ B_0 $ doprava dokud nenajde blok $ B_i $ s alespoň jednou stopou prázdnou.
2. Hlava jede zpět k $ B_0 $ a na pomocnou pásku kopíruje obsah bloků $ B_0,..B_{i-1} $. (Přitom každý blok přejedu 3x).
3. Hlava jede do prava a z pomocné pásky kopíruje data do do dolních stop $ B_1,..,B_{i-1}. V posledním bloku: $
   • do DS pokud $ B_i $ měl obě stopy prázdné.
   • do HS pokud $ B_i $ měl jednu stopu prázdnou.
4. Hlava jede doleva a počíta na pomocnou pásku vzdálenost od pravého kraje $ B_i $ do $ B_0 $.
5. Hlava pokračuje vlevo a pomocí počítadla najde levý okraj bloku $ B_{-i} $.
6. Hlava jede v pravo a kopíruje na pomocnou pásku obsah stopy bloku $ B_{-i} $ (HS pokud je, jinak DS).
7. Hlava pokračuje vpravo a kopíruje data z pomocné pásky do DS bloků $ B_{-i+1},..,B_0 $.

Předchozí body označíme jako $ B_i $ operace.

• Po ukončení $ B_i $ operace platí uvedené invarianty.
• $ B_i $ operace trvá $ m 2^{i-1} $ kroků M', pro konstantu m.
• Po provedení $ B_i $ operace nemůže být další $ B_i $ operace provedena dříve než po $ 2^{i-1} $ krocích stroje M. Tedy každá $ B_i $ operace může být spuštěna maximálně $ \left \lfloor \frac{T(n)}{2^{i-1}}\right\rfloor $ krát.

Stroj M' udělá nejvýše $ T'(n) \le k \sum_{i=1}^{log_2(T(n))+1}(m 2^{i-1} \frac{T(n)}{2^{i-1}}) \le 2mkT(n)\log_2T(n) $. A díky větě o lineárním zrychlení existuje DTS simulujicí M' v čase $ T(n)\log_2T(n) $.

Poznámka: Důkaz lze upravit i pro NTS.

Konstruovatelnost funkcí

Funkce $ f:\mathbb{N} \rightarrow \mathbb{N} $ je rekurzivní pokud existuje DTS M takový, že pro vstup 1ⁿ vydá výstup 1^f(n).

Funkce $ f:\mathbb{N} \rightarrow \mathbb{N} $ je vyčíslitelná v lineárním čase pokud f je rekurzivní a ∃ c ≥ 1 takové, že příslušný DTS udělá nejvýše cf(n) kroků než vydá 1^f(n).

Funkce $ f:\mathbb{N} \rightarrow \mathbb{N} $ je vyčíslitelná v lineárním prostoru pokud f je rekurzivní a ∃ c ≥ 1 takové, že příslušný DTS použije při práci prostor nejvýše cf(n).

Funkce $ f:\mathbb{N} \rightarrow \mathbb{N} $ je časově konstruovatelná pokud existuje DTS M takový, že pro každý vstup délky n zastaví po právě f(n) krocích. (předpokládáme, že f(n) ≥ n + 1).

Funkce $ f:\mathbb{N} \rightarrow \mathbb{N} $ je prostorově konstruovatelná pokud existuje DTS M takový, že pro každý vstup délky n zastaví s právě f(n) páskovými symboly neprázdnými, přičemž žádný jiný prostor na pracovních páskách nebyl v průběhu výpočtu použit.

Lemma

Nechť $ f_1+f_2 $ a $ f_2 $ jsou časově konstruovatelné a nechť $ \forall \epsilon \exists n_0 : \forall n \geq n_0 : f_1(n) \geq \epsilon f_2(n) + (1+\epsilon)n $. Pak je i $ f_1 $ časově konstruovatelná.

Věta

Buď f taková, že $ \forall \epsilon \exists n_0 : \forall n \geq n_0 : f(n) \geq (1+\epsilon)n $. Pak je časově konstruovatelná $ \Leftrightarrow $ je vyčíslitelná v lineárním čase.

Důkaz:

$ \Rightarrow $: zřejmá. Stroj pro čas. konst. upravíme, aby v každém kroku zapsal 1 na výstup, nový stroj vyhovuje požadavkům vpravo, c = 1.

$ \Leftarrow $: f je vyčíslená transducerem M, který nad vstupem délky n udělá g(n) kroků, $ g(n) \leq c\cdot f(n) $.

• g je časově konstruovatelná (existuje M)
• g + f je časově konstruovatelná. Stačí M upravit, aby na novou pásku zapsal výstup - g(n) kroků, a pak na stejné pásce odjel doleva - f(n) kroků, celkem g(n)+f(n) kroků.
• $ \forall \epsilon \exists n_0 : \forall n \geq n_0 : f(n) \geq \epsilon g(n) + (1+\epsilon)n $. Zvolme:
  • $ \epsilon_1 $ z předpokladů věty
  • $ \epsilon_2 $ tak, aby $ (1+\epsilon_1)(1-\epsilon_2)>1 $
  • $ \epsilon_3 = (1+\epsilon_1)(1-\epsilon_2)-1 $
  • $ \epsilon_4 = \min(\epsilon_2/c, \epsilon_3) $
  • dostáváme: $ f(n) = \epsilon_2 f(n) + (1-\epsilon_2)f(n) \geq (\epsilon_2/c)g(n) + (1+\epsilon_1)(1-\epsilon_2) n = (\epsilon_2/c)g(n) + (1+ \epsilon_3) n \geq \epsilon_4 g(n) + (1+\epsilon_4) n $

Jsou splněny předpoklady lemmatu, no a to nam říká, že i f je časově konstruovatelná.

Věta

Buď f funkce. Pak je prostorově konstruovatelná $ \Leftrightarrow $ je vyčíslitelná v lineárním prostoru.

Důkaz:

$ \Rightarrow $: zřejmá. Stroj pro prost. konst. upravíme, aby při návštěvě "čistého" políčka zapsal 1 na výstup, nový stroj vyhovuje požadavkům vpravo, c = 1.

$ \Leftarrow $: Pravá strana nám dává existencí M vyčíslujícího f(n) v prostoru nejvýše cf(n). Stroj upravíme, aby na konci práce zkontroloval, zda použil právě cf(n), případně "zašpinil" pár dalších políček. Z věty o lineární prostorové kompresi najdeme nový stroj, který použije právě f(n) políček, tedy f je prostorově konstruovatelná.

Věta

Každá časově konstruovatelná funkce f, splňující $ \forall \epsilon \exists n_0 : \forall n \geq n_0 : f(n) \geq (1+\epsilon)n $, $ \Rightarrow $ je také prostorově konstruovatelná.

Důkaz:

Když f je vyčíslitelná v lineárním čase, pak je vyč. v lineárním prostoru (když použila max. cf(n) kroků, nemohla zašpinit víc, jak cf(n) políček). Toto tvrzení a 2 věty výše nám udělají "okliku" a dokazují naši větu.

Hierarche tříd složitsti

Lemma (o prostorové složitosti univerzálního TS)

Nechť x je Gödelovo číslo DTS M s 1 vstupní a 1 pracovní páskou, pracujícího v prostoru S(n), s vstupní abecedou {0,1} a pracovní abecedou s t symboly. Pak lze práci M na datech y odsimulovat na univerzálním DTS s 1 prac. a 1 vstupní páskou (na které je x,y) v prostoru $ \max \{ \lceil \log_2(t) \rceil S(|y|), |x| \} $.

Věta (o deterministické prostorové hierarchii)

Buďte $ S_1, S_2 $ funkce takové, že $ S_1 \in o(S_2) $, $ S_1 \geq \log_2(n) $ a $ S_2 $ je prostorově konstruovatelná. Pak existuje L, $ L \in DSPACE(S_2(n))-DSPACE(S_1(n)) $.

Důkaz:

Máme dány $ S_1, S_2 $, chceme najít vyhovující L. Najděme DTS M, přijímající L v prostoru $ S_2 $. Avšak jazyk L nesmí být v $ DSPACE(S_1(n)) $, tedy pro každý stroj jazyka z $ DSPACE(S_1(n)) $ existuje vstup, na který M odpoví jinak, než daný stroj (přijme/nepřijme).

Stroj M si nejdříve označí $ S_2(n) $ buněk na pásce. Pokud v budoucnu tyto buňky opustí, tak zastaví a odmítne vstup.

Na každé slovo w (např. binární) se dívejme jako na w = 11...110 + Gödelovo číslo nějakého DTS ("+" znamená konkatenaci). Také se tomu říká "prefixový kód TS". Třeba "01101" je nula jedniček, nula a stroj "1101". M si "vytáhne" DTS ze vstupu a spustí jeho simulaci na celém vstupu w = 11...11+GČ. M přijme, pokud tento DTS odmítne w, bez opuštění vymezeného prostoru. Zřejmě $ L = L(M) \in DSPACE(S_2(n)) $. Ukažme, že $ L \notin DSPACE(S_1(n)) $.

Pro spor, nechť $ L \in DSPACE(S_1(n)) $. Tedy existuje M', L(M') = L(M) a M' pracuje v prostoru $ S_1(n) $. BÚNO M' je jednopáskový a vždy zastaví (umíme redukovat počet pásek, detekovat zacyklení ve stejném prostoru).

Pokud chceme simulovat stroj M', potřebujeme aspoň $ \lceil log_2t \rceil S_1(n) $ paměti (n je velikost vstupu M', t je velikost abecedy dle věty výše). Určitě existuje w = 11...110 + GČ stroje M' s tolika jedničkami, aby $ \lceil log_2t \rceil S_1(|w|) \leq S_2(|w|) $.

• Pokud M' přijme w, pak $ w \in L(M') = L $. Pokud M' přijme w, pak M odmítne w, $ w \notin L(M) = L $.
• Pokud M' odmítne w, pak $ w \notin L(M') = L $. Pokud M' odmítne w, pak M přijme w, $ w \in L(M) = L $. Spor.

Lemma (o časové složitosti univerzálního TS)

Nechť x je Gödelovo číslo DTS M s 1 vstupní a 2 pracovními páskou, pracujícího v čase T(n), s vstupní abecedou {0,1} a pracovní abecedou s t symboly. Pak lze práci M na datech y odsimulovat na univerzálním DTS se 4 prac. a 1 vstupní páskou (na které je x,y) v čase $ 5 \cdot |x| \cdot T(y) $.

Věta (o deterministické časové hierarchii)

Buďte $ T_1, T_2 $ funkce takové, že $ T_1 \cdot \log_2 T_1\in o(T_2) $, $ T_2 $ je časově konstruovatelná. Pak existuje L, $ L \in DTIME(T_2(n))- DTIME(T_1(n)) $.

Důkaz:

Stejný princip, jako v případě času. Hledáme DTS M, pracující v čase $ T_2(n) $, který se od každého DTS s časem $ T_1(n) $ liší aspoň na jednom slově.

M dostane vstup v podobě w = 11..110 + GČ nějakého DTS. Ten začne na dvou páskách simulovat nad vstupem w, na dalších páskách "stopuje" $ T_2(n) $ kroků. M přijme, pokud tento DTS odmítne w, bez překročení vymezeného času. Zřejmě $ L = L(M) \in DTIME(T_2(n)) $. Ukažme, že $ L \notin DTIME(T_1(n)) $.

Pro spor, nechť $ L \in DTIME(T_1(n)) $. Tedy existuje Mi, L(Mi) = L(M) a Mi pracuje v čase $ T_1(n) $. Pak existuje dvoupáskový M' přijímající L v čase $ T_1(n)\cdot \log_2 T_1(n) $. Určitě existuje w = 11...110 + GČ stroje M' s tolika jedničkami, že $ c \cdot T_1(|w|) \cdot \log_2 T_1(|w|) \leq T_2(|w|) $.

• Pokud M' přijme w, pak $ w \in L(M') = L $. Pokud M' přijme w, pak M odmítne w, $ w \notin L(M) = L $.
• Pokud M' odmítne w, pak $ w \notin L(M') = L $. Pokud M' odmítne w, pak M přijme w, $ w \in L(M) = L $. Spor.

Věta (o vztazích mezi třídami časové a prostorové složitosti)

a) $ NTIME(f(n)) \subseteq DSPACE(f(n)) $

Důkaz:

Simulujeme jednotlivé větve výpočtu NTS na DTS. Generujeme "certifikáty" (1,1,...,1) až (r,r,...,r) (r je max. faktor větvení). Simulaci jedné větve provedeme v prostoru f(n) (kdyby šla dále, "uřízneme", jelikož víme, že NTS to musí přijmout v prostoru f(n)). "Certifikát" zabere prostor log(r) * f(n) (log(r) bitů pro číslo 1 až r). Dle věty o lineární kompresi prostoru najdeme DTS přijímající jazyk v prostoru f(n).

b) $ L \in NSPACE(f(n)), f(n) \geq \log_2(n) \Rightarrow \exists c_L : L \in DTIME(c_L^{f(n)}) $

Důkaz:

Počet všech konfigurací NTS do délky f(n) je $ d^{f(n)} $ pro konstantu d. Uvažujme graf G, vrcholy jsou konfigurace NTS, mezi dvěma vrcholy je hrana, když mezi nimi lze přejít jedním krokem NTS. Krok provádí "lokální úpravy" konfigurace, vrchol má konečně mnoho sousedů, tedy $ |E(G)| \leq c \cdot d^{f(n)} $.

Nabízí se simulovat práci NTS na DTS. Avšak známe pouze omezení prostoru - f(n), je třeba detekovat zacyklení.

Náš DTS bude simulovat NTS (průchodem do hloubky) a na pomocnou pásku postupně generovat všechny navštívené konfigurace. Začne s poč. konfigurací, při provedení kroku projde pomocnou pásku a zkontroluje zda danou konfiguraci už nenavštívil. Při vstupu do přijímací konfigurace skončí. Na pásce tedy není DFS cesta od vrcholu, ale všechny vrcholy navštívené při DFS. Jak dlouho to potrvá? Každý vrchol grafu (konfigurace) a každá hrana (přechod mezi konf.) se navštíví max. jednou.

$ T(n) = |V(G)|q f(n) + |E(G)| d^{f(n)} q f(n) $ - čas zapsání všech konfigurací + počet odsimulovaných kroků * počet dosud navštívených konfigurací (nutné projít pro detekci cyklu) * délka jedné konfigurace.

$ = q f(n) \cdot (d^{f(n)} + k d^{f(n)} d^{f(n)} ) \leq c_L^{f(n)} $

Věta (Savičová)

Nechť S(n) je prostorově konstruovatelná funkce, $ S(n) \geq \log_2(n) $. Pak $ NSPACE(S(n)) \subseteq DSPACE(S^2(n)) $.

Lemma (translační)

Mějme $ S_1, S_2, f $ prostorově konstruovatelné funkce. $ S_2(n) \geq n, f(n) \geq n $. Pak $ NSPACE(S_1(n)) \subseteq NSPACE(S_2(n)) \Rightarrow NSPACE(S_1(f(n))) \subseteq NSPACE(S_2(f(n))) $.

Důkaz:

Mějme libovolný $ L_1 \in NSPACE(S_1(f(n)) $. Chceme ukázat, že $ L_1 \in NSPACE(S_2(f(n)) $. $ L_1 $ je přijímán strojem $ M_1 $.

Položme $ L_2 = \{ x$^i | M_1 \text{ prijima } x \text{ v prostoru } S_1(|x|+i) \} $. $ je zvláštní symbol, který jsme přidali do jazyka, nevyskytuje se ve slově x (uvědomme si, že třídy jazyků obsahují jazyky z různých abeced). Vidíme, že pokud $ |x|+i \geq f(|x|) $, pak $ x \in L_1 \Leftrightarrow x \in L_2 $.

Zkonstruujme stroj $ M_2 $ přijímající $ L_2 $. Stroj dostane vstup $ x$^i $. Nejprve si označí $ S_1(|x|+i) $ políček na pásce (funkce je prostorově konstr., žádný problém). Dále stroj simuluje $ M_1 $ a přijměme slovo $ x$^i $, když $ M_1 $ přijme x bez opuštění vyznačeného prostoru. $ M_2 $ přijímá $ L_2 $ v prostoru $ S_1(n) $, tedy $ L_2 \in NSPACE(S_1(n)) $. Z předpokladu "před implikací" plyne, že $ L_2 \in NSPACE(S_2(n)) $. Tedy existuje stroj $ M_3 $ přijímající $ L_2 $ v čase $ S_2(n) $.

A už jedeme z kopce. Stačí sestrojit $ M_4 $ přijímající $ L_1 $ v čase $ S_2(f(n)) $.

• $ M_4 $ má "dvoustopou" pásku. Na horní stopě si označí f(n) buněk, pak na dolní $ S_2(f(n)) $ (použije "vstup" z horní pásky) a snaží se sem "vejít".

• $ M_4 $ dostane x a simuluje $ M_3 $ nad vstupem $ x$^i $. Když chce $ M_3 $ odjet mimo x na dolary, $ M_4 $ si to eviduje na vedlejší pásce (stačí číslo, na kolikátem dolaru se $ M_3 $ nachází).

• $ M_4 $ eviduje "vstupní dolar" binárně na prostoru $ S_2(f(n)) $, tedy poradí si až s $ 2^{S_2(f(n))} $ dolary.

• $ M_4 $ přijme x, když $ M_3 $ přijme.

Stačí, že si poradíme jen s $ 2^{S_2(f(n))} $ dolary? $ S_2(n) \geq n, f(n) \geq n $, tedy $ 2^{S_2(f(n))} \geq f(n) \geq i $ = počet dolarů. Zkonstruovali jsme $ M_4 $ přijímající $ L_1 $ v prostoru $ S_2(f(n)) $, $ L_1 \in NSPACE(S_2(f(n))) $.

Poznámka: Platí pro DSPACE, NTIME i DTIME.

Věta (o nedeterministické prostorové hierarchií pro polynomy)

Pro všechna $ r \geq 1, \epsilon >0 $ existuje L takový, že $ L \in NSPACE(n^{r+\epsilon}) - NSPACE(n^r) $.

Důkaz:

Víme, že existují $ s, t \in \mathbb{N} $ taková, že $ r \leq \frac{s}{t} < \frac{s+1}{t} \leq r+\epsilon $. Stačí nám ukázat, že $ NSPACE(n^{s/t}) \subsetneq NSPACE(n^{(s+1)/t}) $.

Pro spor, nechť $ NSPACE(n^{(s+1)/t}) \subseteq NSPACE(n^{s/t}) $. Z translačního lemmatu plyne, že $ \forall i : NSPACE((n^{(s+i)t})^{(s+1)/t}) \subseteq NSPACE((n^{(s+i)t})^{s/t}) $. Přepišme na $ \forall i : NSPACE(n^{(s+i)(s+1)}) \subseteq NSPACE(n^{(s+i)s}) $. Dostaneme:

• i=0: $ NSPACE( n^{(s+1)s} ) \subseteq NSPACE( n^{ss} ) $
• i=1: $ NSPACE( n^{(s+1)(s+1)} ) \subseteq NSPACE( n^{(s+1)s} ) $ ...
• i=s: $ NSPACE( n^{(s+1)2s} ) \subseteq NSPACE( n^{(2s)s} ) $

Dále vidíme, že každá pravá strana je podmnožinou levé strany o řádek výše (stačí porovnat exponenty). Sestrojme řetězec:

• $ NSPACE(n^{(s+1)2s}) \subseteq NSPACE(n^{ss}) \subseteq DSPACE(n^{2ss}) \subsetneq DSPACE(n^{2ss + 2s}) \subseteq NSPACE(n^{(s+1)2s}) $

Odůvodnění: Tranzitivně "odskáčeme" v seznamu výše | Savičova věta | Věta o DPH | triviální (stejný exponent)

Začátek a konec řetězce jsou stejné množiny, uvnitř je ostrá podmnožina, je to tedy spor, předpoklad neplatí, tedy platí věta.

Kuriozity

Borodinova věta o mezerách

Nechť $ g(n) \geq n $, g je rekurzivní funkce. Potom existuje rekurzivní rostoucí funkce S(n) taková, že DSPACE(S(n)) = DSPACE(g(S(n))).

Důkaz:

Nechť $ M_1, M_2, ... $ je očíslování všech DTS. $ S_i(n) $ je max. počet použitých buněk při práci i-tého stroje nad vstupem délky n (pokud zastaví). Pro dané i, n, m lze ověřit, zda $ S_i(n)\leq m $.

Zkonstruujme S(n) takovou, že pro každý (k-tý) stroj platí jedna z podmínek:

• $ S_k(n) < S(n) $ skoro vždy
• $ g(S(n)) \leq S_k(n) $ nekonečně často

Pro takové S neexistuje stroj $ M_k $ takový, aby pro všechna n: $ S(n) < S_k(n) \leq g(S(n)) $. Tedy každý DTS buď leží "před S(n)" (v obou třídách, "skoro vždy" ošetříme automatem, jazyk se zachová), nebo "za g(S(n))" (v ani jedné ze tříd, "nekonečně často" nelze ošetřit, nelze nacpat před g(S(n)) ).

Zkonstruujme funkci S. Jak spočteme S(n) pro dané n?

Položme j=1, spočítejme g(j). Zkontrolujme pro $ i \in (1 ... n) $, zda pro nějaký stroj $ M_i $: $ j < S_i(n) \leq g(j) $. Pokud takový stroj neexistuje (všechny stroje pracují v prostoru mimo interval), položme S(n) = j. Jinak položme $ j = S_i(n) $ a proces zopakujme. Spodní hranice j se posouvá nahoru, po nejvýše n iteracích budou všechny stroje $ M_1 ... M_n $ pod j, nebo nad g(j). Co dělají ostatní stroje nás nezajímá.

Podívejme se na stejnou věc z hlediska libovolného stroje $ M_k $. Pro i>k je $ S_i(n) $ vždy mimo "kritický interval". Pokud není skoro vždy pod ním, musí být nekonečně často nad ním.

Poznámka: Platí pro NSPACE, NTIME i DTIME.

Blumova věta o zrychlení

Nechť $ r: \mathbb{N} \rightarrow \mathbb{N} $ je rekurzivní fce. Pak existuje rekurzivní jazyk L takový, že pro každý DTS A, přijímající L v prostoru $ S_A(n) $ existuje DTS B přijímající L v prostoru $ S_B(n) $ a $ r(S_B(n)) \leq S_A(n) $ skoro všude.

Existuje i ve verzi pro časovou složitost.

Poznámky

Pokud uvažujeme o složitosti (tj třídách DTIME, DSPACE, atd.) tak je rozumné brát jen konstruovatelné funkce. Pokud vezmeme v úvahu obecné (rekurzivní a tedy potenciálně nekonstruovatelné) funkce tak můžeme dostat prapodivné "výsledky" a toto je jeden z nich.

---

Blumova věta vlastně říká, že pro danou rekurzivní funkci (například r(n)=n^2) existuje rekurzivní jazyk L takový, že pro každý algoritmus (=TS), který L rozpozná v daném čase t(n), existuje jiný TS který L rozpozná v čase p(n) a r((p(n))<=t(n).

TEDY, tento problém (L) nemá nic jako optimální algoritmus – vždy jde urychlit. (a to je jaksi kontra-intuitivní, to nechceme :-)

---

Podobně patologický případ je i Borodinova věta: ta říká něco ve smyslu že můžeme udělat libovolně velkou mezeru - jak je ve znění – pro každou g(n)>n rekurzivní existuje rekurzivní s(n) tak že DSPACE[s(n)]= DSPACE[g(s(n))].

Tohle je jaksi proti větám o hierarchiím – ty říkají, že když přidáme trošku výpočetní síly (v prostorovém případě stačí řádově víc, v časovém o logaritmicky faktor) tak dostaneme nové jazyky. Zde máme k dipozici libovolné zvětšení prostoru resp. času (s(n) či g(s(n))) a dokážeme spočítat stále to samé.

Například nechť g(n)=2^n, pak mluvíme o intervalu [s(n), 2^(s(n))].

Zkrátka případy, kde funkce, jež bereme v úvahu, nejsou konstruovatelné, jsou patologické.

Základní třídy složitosti

Prostor

$ LOG=DSPACE(log(n)) $

$ NLOG=NSPACE(log(n)) $

$ POLYLOG=\bigcup_{i\ge \;0}DSPACE(log^{i}(n)) $

$ PSPACE=\bigcup_{i\ge \;0}DSPACE(n^{i}) $

$ NPSPACE=\bigcup_{i\ge \;0}NSPACE(n^{i}) $

$ EXPSPACE=\bigcup_{c\ge \;0}DSPACE(2^{c*n}) $

Tato část je neúplná a potřebuje rozšířit. overit EXPSPACE, na wen:EXPSPACE definovano jako $ EXPSPACE=\bigcup_{c\ge \;0}DSPACE(2^{n^{c}}) $

Čas

$ P=\bigcup_{i\ge \;0}DTIME(n^{i}) $

$ NP=\bigcup_{i\ge \;0}NTIME(n^{i}) $

$ DEXT=\bigcup_{c\ge \;0}DTIME(2^{c*n}) $

$ NEXT=\bigcup_{c\ge \;0}NTIME(2^{c*n}) $

$ DEXPTIME=\bigcup_{c\ge \;0}DTIME(2^{n^c}) $

$ NEXPTIME=\bigcup_{c\ge \;0}NTIME(2^{n^c}) $

Vztahy základních třídy složitosti

• $ NLOG \subseteq P $

2^{log(c)*log(n)}=n^konst. ... NS vs. DT

• $ PSPACE=NPSPACE $

nⁱ vs. n^2*i ... Savič

• $ NP \subseteq PSPACE $

NT vs. DS vs. PSPACE

• $ PSPACE \subseteq EXPTIME $

2^log(c)*ni << 2ⁿ⁽ⁱ⁺¹⁾ ... log(c)>n je jen pro konečně mnoho případů

• $ NLOG \subset PSPACE \subset EXPSPACE $

NLOG ⊂ PSPACE ... Savič + DS(log²(n)) ⊂ DS(n)

PSPACE ⊂ EXPSPACE ... PSPACE ⊆ DSPACE(nⁱ) ⊆ DSPACE(2ⁿ) ⊂ DSPACE(2^2*n) ⊆ EXPSPACE

DSPACE(nⁱ) ⊆ DSPACE(2ⁿ) ještě není ostře!

• $ P \subset DEXT \subset EXPTIME $

∀ i: DT(nⁱ) ⊂ DT(2ⁿ) ... 2ⁿ ∈ ω(nⁱ*log(nⁱ))

P ⊆ DT(2ⁿ) ⊂ DT(2^2*n) ⊆ DEXT ... 2^2*n ∈ ω(2ⁿ*log(2ⁿ))

∀ c: DT(2^c*n) ⊂ DT(2ⁿ²)

DEXT ⊆ DT(2ⁿ²) ⊂ DT(2ⁿ³) ⊆ EXPTIME

Poznámy:

• Spočené sjednocení se odhaduje neostře, pak ale jeho horní odhad snadno umíme omezit ostře.
• NLOG ⊆ P ⊆ NP ⊆ PSPACE ale NLOG ⊂ PSPACE, kde se to "zlomí" nikdo zatím neví.

Wowza, problem solved like it never hpaepend.

Turingovská převoditelnost a relatizované třídy

Motivace: Představte si, že máme za úkol rozpoznávat jazyk A. No a někdo přijde s tím, že vymyslel skvělý turingáč M, který A rozpoznává v polynomiálním čase, ale potřebuje k tomu orákulum, které rozpoznává jazyk B. Ten člověk se asi pochvaly nedočká, ale my už nemusíme řešit rozpoznávání A pokud se nám podaří rozpoznávat místo toho B. K tomu se zavádí pojem T-převoditelnosti jazyků.

Definice: deterministická turingovská převoditelnost

Nechť L₁ a L₂ jsou jazyky. Řekneme, že L₁ je deterministicky turingovsky převoditelný na L₂ v polynomiálním čase pokud existuje DTS M s orákulem L₂ pracujicí v polynomiálním čase a přijímajicí L₁. Tedy, že L₁ = L(M,L₂). Značení: L₁ ⊆_T L₂.

V dalším textu budou znaky Ƥ a ƝƤ značit nerelativizované třídy P a NP. Značení P a NP se bude nadále využívat pro relativizované třídy.

Pre viac informácií o relativizovaní a všeobecnejšej turingovskej prevoditeľnosti pozri T-prevoditeľnosť

Příklad: A ∈ Ƥ => A ⊂_T 0.

Definice: deterministicky turingovsky relativizované jazyky a třídy

• Nechť A je jazyk. Potom P(A) = { B | B ⊂_T A}.
• Nechť Ƈ je třída jazyků. Potom P(Ƈ) = { B | ∃ A ∈ Ƈ : B ⊂_T A}.

Příklad: P(Ƥ) = Ƥ

Lze složit stroje a emulovat DOTAZ pomocí výpočtu DTS (inymi slovami: cely vypocet problemu B lze previest na orakulum B :) )

Pozn. Zavorka v predchozi vete mi nedava smysl... jde o to ze vnejsi DTS bezi v pol. case, takze na dotaz. pasku napise maximalne polynomialni mnozstvi dat, a vnitrni DTS ktere nahradilo orakulum bezi v polynomialnim case nad polynomialnimi daty, tedy polynomialne, a tedy to cele bezi polynomialne

Definice: nedeterministická turingovská převoditelnost

Nechť L₁ a L₂ jsou jazyky. Řekneme, že L₁ je nedeterministicky turingovsky převoditelný na L₂ v polynomiálním čase pokud existuje NTS M s orákulem L₂ pracujicí v polynomiálním čase a přijímajicí L₁. Tedy, že L₁ = L(M,L₂). Značení: L₁ ⊆^NP L₂.

Příklad: ? NP(ƝƤ)=ƝƤ ? Nevime.

Nelze simulovat DOTAZ pomocí NTS, protože krom ANO větve může zároveň existovat řada slepých NE větví.

(IMHO podle Trckapress zapisku) Takze muzu udelat NTS ktery polozi DOTAZ a na odpoved ANO slovo odmitne, na odpoved NE prijme. Predpokladejme ze pro dane slovo orakulum rekne ANO. Nahradim orakulum vnitrnim NTS ("vnitrni" stroj je ten, co se pta orakula, "vnejsi" stroj realizuje orakulum). Takze ANO na orakulu ted znamena, ze existuje prijimaci vypocet vnitrniho NTS, tzn. muzou existovat neprijimajici vypocty. Pro takove neprijimajici vypocty "vnitrniho" NTS pak "vnejsi" NTS slovo prijme - tedy existuje prijimajici vypocet vnejsiho NTS a slovo tedy NTS prijima. Ale s orakulem by ho neprijal.

Gaebtan dit :Bonjour,Le plus simple est de trvuoer une image et de la redimensionner e0 la taille de votre header avec un logiciel de retouche photo.Il existe des sites pour re9cupe9rer des images libres de droits.Faites une Exemple sur pour une recherche bien eatre

Poznámka

Lze zavést nejrůznější definice - turingův stroj, který zajišťuje převoditelnost nemusí pracovat jen v polynomiálním čase. Například (pro množiny jazyků):

• PSPACE(B) = { A | B ⊂_PSPACE A} - třída všech jazyků, které lze rozpoznat pomocí DTS s orákulem B v polynomiálním prostoru
• LOG(B) = { A | B ⊂_LOG A} - třída všech jazyků, které lze rozpoznat pomocí DTS s orákulem B v logaritmickém čase
• NEXT(B) = { A | B ⊂_NEXT A} - třída všech jazyků, které lze rozpoznat pomocí NTS s orákulem B v exponenciálním čase

Nebo pro třídu jazyků 𝒞:

• PSPACE(𝒞) = { B | ∃ A ∈ 𝒞 : B ⊂_PSPACE A} - třída všech jazyků, které jsou v polynomiálním prostoru převoditelné na libovolný jazyk z 𝒞 (pomocí DTS)
• LOG(𝒞) = { B | ∃ A ∈ 𝒞 : B ⊂_LOG A} - třída všech jazyků, které jsou převoditelné v logaritmickém čase na libovolný jazyk z 𝒞 (pomocí DTS)
• NEXT(𝒞) = { B | ∃ A ∈ 𝒞 : B ⊂_NEXT A} - třída všech jazyků, které jsou převoditelné v exponenciálním čase na libovolný jazyk z 𝒞 (pomocí NTS)

Lema 1: Platí: ∀ A : P(A) ⊆ NP(A) ⊆ PSPACE(A).

důkaz jako v nerelativizováné verzi a P ⊆ NP je zřejmé

Polynomiální hierarchie

Pekne a jednoduche vysvetleni - souvislost s TQBF a PSPACE, alternujici kvantifikatory.

Jedna z možných motivací třídy NP je otázka, zda je (řádově) stejně těžké vytvořit nějaké řešení problému a následně jej ověřit. Tedy se v případě NP ptáme, zda existuje certifikát odpovídající řešení daného zadání (v této otázce je skrytý právě ten nedeterminismus). Naopak u třídy co-NP se ptáme, zda pro každý "NP certifikát" můžeme říci, že řešení neodpovídá. (Intuitivně se tedy zdá, že zatímco v případě NP je certifikát krátký - odpovídající přímočarému ověřovacímu postupu - v případě co-NP certifikát musí pokrývat všechna možná řešení a přesvědčit nás, že ani jedno není správně, což by "mělo" být mnohem složitější. Ve skutečnosti je NP != co-NP otevřený problém odpovídající P != NP, nyní však tiše předpokládejme, že tyto nerovnosti platí. Pozor, NP = co-NP ještě neimplikuje P = NP)

Polynomiální hierarchie je zobecnění tříd NP a co-NP na složitější problémy. Všimněme si, že NP problémy odpovídají existenčnímu kvantifikátoru, zatímco co-NP problémy odpovídají univerzálnímu kvantifikátoru. Uvažme například problém nezávislé množiny: zatímco dotaz "existuje v daném grafu nezávislá množina velikosti x?" je NP-úplný, dotaz "_neexistuje_ v daném grafu nezávislá množina velikosti x?" (tedy "má každá nezávislá množina vrcholů v daném grafu velikost menší než x?") je v co-NP.

Je ale přirozené položit i další dotaz - "je x velikost největší nezávislé množiny v daném grafu?", jinak řečeno "existuje v daném grafu nezávislá množina velikosti x a každá nezávislá množina vrcholů v daném grafu má velikost menší či rovnu x?". Takový dotaz kombinuje existenční i univerzální kvantifikátor a není tedy ve třídě NP ani co-NP (s tak těžkými problémy se nesetkáváme v rámci přednášek často, je však spousta dalších); kam ho tedy zařadit?

Polynomiální hierarchie nám poskytuje právě infrastrukturu pro škatulkování problémů obsahujících kombinace univerzálních a existenčních kvantifikátorů. Máme-li za sebou více kvantifikátorů stejného druhu, třídu složitosti to nemění (můžeme použít jeden kvantifikátor přes k-tici), střídáme-li však kvantifikátory, stoupáme úrovněmi polynomiální hierarchie.

Existuje několik různých definic polynomiální hierarchie; kromě výše uvedené pracující s kvantifikátory se často (i na naší přednášce) používá definice pomocí strojů s orákuly řešícími nižší úroveň hierarchie. V orákulu jsou vlastně zavřeny všechny kvantifikátory kromě prvního, ten je počítán "vnějším" strojem.

Věta o vztahu PH a PSPACE

$ PH \subseteq PSPACE $.

Důkaz:

Chceme dokázat, že $ \forall k: \Sigma_k \subseteq PSPACE $. Indukcí:

1) $ \Sigma_0 = P \subseteq PSPACE $.

2) Nechť $ \Sigma_k \subseteq PSPACE $. Pak $ \Sigma_{k+1} = NP(\Sigma_k) \subseteq NP(PSPACE) \subseteq PSPACE(PSPACE) $. První inkluze plyne z indukčního předpokladu, druhá z toho, že orákulový NTS v poly čase se vejde do poly prostoru.

Teď stačí ukázat, že PSPACE(PSPACE) = PSPACE. Buď A z PSPACE(PSPACE). Tedy existuje B z PSPACE a DTS M, A = L(M, B). Existuje taky DTS M' pro B, pracující v poly prostoru.

Udělejme DTS M2, pracující v poly prostoru, přijímající A. M2 simuluje M a ve stavu DOTAZ spustí M' nad dotazovací páskou. Obě "úrovně" simulace se vejdou do poly prostoru, tedy A je z PSPACE.

Převoditelnost a úplnost

L₁ je v polynomiálním čase převoditelný na L₂ pokud existuje DTS pracujicí v polynomiálním čase takový, že pro vstup x zkonstruje výstup y takový, že x ∈ L₁ <=> y ∈ L₂.

M je log-space transducer pokud M je offline DTS, který vždy zastaví, má log(n) prostoru na pracovních páskách a výstupní pásku (pouze zápis a pohyb hlavy do prava).

L₁ je v logaritmickém prostoru převoditelný na L₂ pokud existuje log-space transducer M který pro vstup x zkonstruje výstup y takový, že x ∈ L₁ <=> y ∈ L₂.

Template na defnice převoditelnosti

L₁ je T-převoditelný na L₂ pokud existuje sroj M∈T, který pro vstup x zkonstruje výstup y takový, že x ∈ L₁ <=> y ∈ L₂.

Nechť Ƈ je třída jazyků. Říkame, že jazyk L je úplný pro třídu Ƈ vzhledem k převoditelnosti (v polynomiálním čase, logaritmickém prostoru,..) pokud:

• L ∈ Ƈ
• ∀L' ∈ Ƈ platí L' je převoditelný na L.

• L je ƝƤ-úplný pokud L je úplný pro třídu ƝƤ vzhledem k převoditelnosti v polynomiálním čase.
• L je Ƥ-úplný pokud L je úplný pro třídu Ƥ vzhledem k převoditelnosti v logaritmickém prostoru.
• L je PSPACE-úplný pokud L je úplný pro třídu PSPACE vzhledem k převoditelnosti v polynomiálním čase.

Poznámka: Definovat Ƥ-úplnost přes převoditelnost v polynomiálním čase nemá smysl (každý P by byl Ƥ-úplný)

Příklad Ƥ-úplného problému

Jazyk kódů prázdných bezkontextových gramatik.

Věta (QBF je PSPACE-úplný)

QBF (bez volných proměnných) je PSPACE-úplný.

Důkaz:

1) Ukažme, že QBF ∈ PSPACE. Procedura eval rekurzivně počítá QBF.

• QBF je konstanta <=> eval vrátí konstantu
• QBF je konjunkce, disjunkce, negace <=> eval rekurzivně puštěn na podformule a výsledek spočten podle příslušného operátoru.

pro ∀ resp. ∃:

(∃ x) E(x) vrací eval hodnotu výrazu E(0) ∨ E(1)

(∀ x) E(x) vrací eval hodnotu výrazu E(0) ∧ E(1) //domena pro x je len {true, false}, tj. {0,1}

V QBF je nejvýš n operátorů a kvantifikátorů, hloubka rekurze eval je tedy nejvýš n. Pracovní páska DTS slouží jako zásobník aktivačních záznamů procedury eval, každý takový záznam je jen polynomiálně velký v n. Celkový použitý prostor je polynomiální.

2) Ukažme, že QBF je "PSPACE-těžký", tedy že ∀ L ∈ PSPACE : L lze polynomiálně převést na QBF.

L je z PSPACE, tedy existuje DTS M přijímající L v poly prostoru S(n). Pro každé slovo w chceme umět zkonstruovat QBF f, která bude TRUE, právě když w je v L. Nechť c1, c2 jsou dvě konfigurace M, t přirozené číslo. Nechť QBF $ \phi_{c1,c2,t} $ má hodnotu TRUE, když M se může dostat z c1 do c2 po nejvýše t krocích. Konkatenace konfigurací c1, c2 je zároveň ohodnocení proměnných. Pak našim cílem je $ f = \phi_{c_{start},c_{accept},T} $, $ c_{start} $ je počáteční konfigurace, c_{accept} koncová a T je maximální počet kroků, který M může potřebovat. Víme, že $ T = d^n $ pro konstantu d (tj. počet konfigurací v prostoru S(n) je "exponenciální").

Naše QBF f má hodnotu TRUE, právě když w patří do L. Při znalosti M a slova w, potřebujeme zkonstruovat f v poly čase.

• t = 1, $ \phi_{c1,c2,t} $ - formule je jasná, buď DTS se po 1 kroku dostane do c2, nebo nedostane.
• t > 1, $ \phi_{c1,c2,t} $ - formuli rekurzivně složíme ze dvou, a to: $ \exists m_1(\phi_{c1,m_1,\lceil t/2 \rceil} \wedge \phi_{m_1,c2,\lceil t/2 \rceil}) $

Jelikož T je exponenciálně velké, naše formule f bude exponenciálně dlouhá. Všimněte si, že jsme vůbec nepoužili všeobecný kvantifikátor. Zkusme to definovat jinak.

• t > 1, $ \phi_{c1,c2,t} $ jako $ \exists m_1 \forall c3 \forall c4 ((c3,c4)=(c1,m_1) \vee (c3,c4)=(m_1,c2)) \Rightarrow \phi_{c3,c4,\lceil t/2 \rceil}) $

Výraz před konjunkcí lze přepsat do CNF velikosti c*S(n). Máme však pouze jedno "rekurzivní volání". Velikost celé f tedy bude cca $ S(n)^2 $. Stejnou velikost má i prostor a čas naší konstrukce f (půlením T se z exp. času vrátíme do poly času).

Poznámka

V důkazu výše vůbec není zřejmé, jak se staví formule. Popisuje se rekurzivní vlastnost, avšak kvantifikují se konfigurace. QBF musí obsahovat booleovské proměnné.

Jak by šel důkaz výše interpretovat: Navrhuji následující konstrukci QBF. Pro reprezentaci konfigurace potřebujeme cca S(n) znaků. Konfiguraci tedy můžeme reprezentovat pomocí cca S(n) booleovských proměnných. Kvantifikaci konfigurace $ \exists C $ přepíšeme na kvantifikaci bool. proměnných $ \exists c_1 \exists c_2 ... \exists c_{S(n)} $. Rovnost konfigurací přepíšeme na rovnost prvních, druhých ... bool. proměnných: $ (C = D) ---> (c_1=d_1 \wedge c_2=d_2 \wedge ... \wedge c_{S(n)}=d_{S(n)}) $, kde rovnost bool. proměnných přepíšeme takto: $ (c=d) ---> (c \wedge d) \vee (\neg c \wedge \neg d) $. Pokud je jedna konfigurace konstantní, lze to ještě víc zjednodušit.

Jakmile se dostaneme na nejnižší úroveň (t=1), máme dvě konfigurace C,D (tedy S(n)+S(n) proměmnných) a stavíme QBF pravdivou právě tehdy, když lze z C přejít do D jedním krokem. Do dané QBF musíme zakódovat celou přechodovou funkci stroje M. Když přechodová funkce má K "řádků", QBF bude mít tvar $ F_1 \vee F_2 \vee ... \vee F_K $, kde $ F_i $ říká, že konfigurace C splňuje levou stranu i-tého přechodu (displej, stav, ...) a konfigurace D splňuje pravou stranu i-tého přechodu (nový displej, posuny hlav ...).

Délka celé QBF má být polynomiální, stejně tak čas její konstrukce (z definice převoditelnosti). Rekurzivní algoritmus se zanoří až S(n)-krát, na každé úrovni kvantifikuje 3 nové konfigurace = 3*S(n) nových bool. proměnných. Délka této části je kvadratická. Na nejnižší úrovni (t=1) se "přilepí" QBF o velikosti přechodové funkce M.

Zde nastává problém, když velikost M není omezená polynomem daného vstupu (stejný problém např. u Kachlíkování, kdy se vyrábí víc kachlíků, než je polynom vstupu). Fígl je ten, že polynomiální převoditelnost je definovaná mezi dvěma jazyky, nikoli mezi třídou a jazykem. Celý postup výše nepopisuje algoritmus převodu DTS na QBF, ale jen schéma spousty různých algoritmů, každý z nich převádí slovo na QBF pro jeden konkrétní DTS v poly-čase. Krátkých vstupů (jejichž polynom nepřekročí velikost stroje) je jen konečně mnoho a můžeme pro ně vyrobit konečný automat, který pro dané vstupy vrátí "konstantní True QBF", např. $ \forall x (x \vee \neg x) $ (nebo konstantní false QBF, pokud dané krátké slovo automat nepřijímá).