Složitost II

Z ωικι.matfyz.cz
Verze z 29. 5. 2008, 02:12, kterou vytvořil Che (diskuse | příspěvky) (Poznámky: Viz též státnicový okruh Složitost.)

Přejít na: navigace, hledání
Složitost II
Kód předmětu: NTIN063
Přednáší: Ondřej Čepek

Obecné informace o předmětu

Zápočet

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

Zkouška

  • Písemka - dokázování inkluzí mezi třídami složitosti.
  • Ústní část - teoretická otázka.

Minulé termíny

převzato z http://mff.modry.cz/slozitost/zkousky/zkousky_leto.txt

Letní semestr 2004/2005

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)} $

Třídy složitosti

  • DSPACE(S(n)) - třída jazyků deterministické prostorové složitosti S(n).
  • NSPACE(S(n)) - třída jazyků nedeterministické prostorové složitosti S(n).
  • DTIME(T(n)) - třída jazyků deterministické časové složitosti T(n).
  • NTIME(T(n)) - třída jazyků nedeterministické časové složitosti T(n).

Věta o lineární prostorové kompresi

Znění

Nechť L je jazyk přijímaný k-páskovým DTS M s prostorovou složitostí S(n). Potom $ \forall r \in \mathbb{N}^+ $ existuje k-páskový DTS M' s prostorovou složitostí $ \left \lceil \frac{1}{r} * S(n) \right \rceil $ přijímajicí jazyk L.

Důkaz

Popíšeme konstrukci stroje M'.

Každý symbol z $ \Sigma_{M'} $ kóduje uspořádanou r-tici z $ \Sigma_M $. Jeden krok stroje M je simulován jedním krokem stroje M'. Přičemž stavy řídící jednotky M' si pamatují na kterém symbolu aktuální r-tice je hlava simulovaného stroje.

a) k = 1. Stroj s jednou vstupní (READ ONLY) a jednou výstupní (WRITE ONLY) páskou.

  • Pásková abeceda: uspořádané r-tice páskových symbolu stroje M.
  • Stavy: $ q_i $ převedeme na $ q_i^l; \forall 1 \le l \le r $.
  • Přechodová funkce
    • Bez pohybu hlavy: $ \delta_M(q_i,z,a) \rightarrow (q_j,b,N) $ převedeme na $ \delta_{M'}(q_i^l,z,x^l) \rightarrow (q_j^l,y^l,N) $ $ \forall l; 1 \le l \le r $ a $ \forall (x^l,y^l) $ kde $ x^l $ koduje slovo na jehož l-té pozici je $ a $ a $ y^l $ kóduje slovo na jehož l-té pozici je b.
    • Pohyb hlavy doprava: $ \delta_M(q_i,z,a) \rightarrow (q_j,b,R) $ převedeme na
      • $ \delta_{M'}(q_i^l,z,x^l) \rightarrow (q_j^{l+1},y^l,N) $ $ \forall l; 1 \le l \le r-1 $
      • $ \delta_{M'}(q_i^r,z,x^l) \rightarrow (q_j^1,y^l,R) $
    • Pohyb hlavy doleva: $ \delta_M(q_i,z,a) \rightarrow (q_j,b,L) $ převedeme na
      • $ \delta_{M'}(q_i^l,z,x^l) \rightarrow (q_j^{l-1},y^l,N) $ $ \forall l; 2 \le l \le r $
      • $ \delta_{M'}(q_i^1,z,x^l) \rightarrow (q_j^r,y^l,L) $

b) Pro obecné k.

  • Stejná myšlenka jen složitější zápis.
    • Stavy kódují né pozici v 1 r-tici, ale v k r-ticích: $ q_i^{(l_1,l_2,..,l_k)} $

$ \Box $

Stejný důkaz lze zopakovat i pro NTS.

Důsledky

  • $ \forall r \in \mathbb{N}^+: DSPACE(S(n)) = DSPACE(\left \lceil \frac{1}{r} * S(n) \right \rceil) $

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

Znění

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

Základní myšlenka je, že symboly ze stejné buňky všech pásek se smrsknou do jednoho znaku (k-tice) nové pásky. Ve znaku je také potřeba držet informaci jestli je nad symbolem hlava původního stroje nebo ne. Pak se simulují instrukce původního stroje (postupně pro každou pásku M).

$ \Box $

To samé lze zopakovat pro NTS.

Lemma o lineárním zrychlení

Znění

Nechť L je jazyk 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*\left \lceil \frac{t}{r} \right \rceil $

Důkaz

  • zhustím vstup r krát
  • krok stroje pak bude
    • 4 kroky (vlevo, vpravo, vpravo, vlevo) a získám informaci o 3*r políčkách stroje M.
      • vím i na co se přepíší max. 2 sousední buňky M' (2*r buněk M)
    • 2 kroky na přepsání buněk

Poznámky

  • Lze simulovat nejen r kroků stroje M, ale doknce r+1, protože během nich určitě nepřepíše více než 3*r budněk stroje M.

Věta o lineárním zrychlení

Znění

Část 1: Nechť L je jazyk přijímaný k-páskovým DTS M s časovou složitostí T(n), kde k ≥ 2 a platí $ inf_{n \rightarrow \infty} \frac{T(n)}{n} = \infty $ (resp. $ T(n)\in \omega(n) $). Potom ∀ c > 0 existuje k-páskový DTS M' s časovou složitostí cT(n) přijímajicí L.


Část 2: Nechť L je jazyk přijímaný k-páskovým DTS M s časovou složitostí T(n)=cn, kde k ≥ 2 a c > 1. Potom ∀ ε > 0 existuje k-páskový DTS M' s časovou složitostí (1 + ε)n přijímajicí L.

Důkaz

Popíšeme činnost stroje M'. Z m políček původní pásky udělám jeden znak (m-tici) nového stroje.

  1. přepíše vstup m-krát zahuštěný na pracovní pásku, na to potřebujeme $ n+1 $ kroků.
  2. odjede na začátek nové pracovní pásky, na to potřebujeme $ \left \lceil \frac{n}{m} \right \rceil $ kroků.
  3. simuluje T(n) kroků stroje M pomocí $ 8 * \left \lceil \frac {T(n)}{m} \right \rceil $ kroků.
    • podívám se na okolní m-tice a zapamatuji si jejich konfiguraci. (4 kroky)
    • odsimuluji M dokud nevyleze z těchto m-tic. (zaberu aspoň m kroků původního stroje).
    • protože M je DTS tak jednoznačně vím na co se původní 3 m-tice přepíší. Přepíši je. (4 kroky).


Celkově tedy $ n + \left \lceil \frac{n}{m} \right \rceil + 8 * \left \lceil \frac {T(n)}{m} \right \rceil $ kroků.

  • Část 1: Jak určit m aby $ n + \left \lceil \frac{n}{m} \right \rceil + 8 * \left \lceil \frac {T(n)}{m} \right \rceil \le c * T(n) $?
m>16/c
pro m>=2 omezíme výrazem
2*n+8+8*T(n)/m (*)
jelikož T(n) ∈ ω(n) tak pro skoro všechna n je (*) omezeno výrazem c/2*T(n)+8*T(n)/m
z volby m dostáváme c/2*T(n)+8*T(n)/m<=c/2*T(n)+c/2*T(n)=c*T(n)
  • Část 2: Jak určit m aby $ n + \left \lceil \frac{n}{m} \right \rceil + 8 * \left \lceil \frac {cn}{m} \right \rceil \le (\varepsilon + 1) * n $?
$ n + \left \lceil \frac{n}{m} \right \rceil + 8 * \left \lceil \frac {cn}{m} \right \rceil \le (\varepsilon + 1) * n $
$ n + \frac{n}{m} + 1 + 8 * \frac {cn}{m} + 8 \le (\varepsilon + 1) * n $
$ (1 + \frac{1}{m} + 8 * \frac {c}{m} + \frac{9}{n})*n \le (\varepsilon + 1) * n $
chceme najít ε
$ \frac{1}{m} + 8 * \frac {c}{m} + \frac{9}{n}< \; \varepsilon $
Stačí zvolit m a n0 tak, aby:
1/m ≤ ε/3 ... m≥3/ε
c/m≤ε/3 ... m≥c*3/ε
9/n0≤ε/3 ... n0≥27/ε
m=max{3/ε, c*3/ε} a n0=27/ε

$ \Box $

Stejná věta se dá dokázat i pro NTS.

Věta o redukci počtu pásek pro časovou složitost

Znění

Část 1: Nechť L ∈ DTIME(T(n)) a platí $ inf_{n \rightarrow \infty} \frac{T(n)}{n} = \infty $ nebo T(n) = cn kde $ c >\sqrt{2k} $. Potom existuje jednopáskový DTS s časovou složitostí $ T(n)^2 $ přijímajicí L.


Část 2: Nechť L je jazyk příjímaný k-páskovým DTS M s časovou složitostí T(n). Potom existuje 2-páskový DTS M' s časovou složitostí $ T(n)\log_2T(n) $ přijímajicí L.

Důkaz

Část 1:

Poznámka: Obráceně to dělat nemůžu protože neumíme zrychlovat jednopáskové stroje.


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


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 stop $ B_1,..,B_{i-1} $
    • 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) $.

$ \Box $

Tato část je neúplná a potřebuje rozšířit. Hodil by se obrázek jak se data posouvají po pásce.

Důsledky

  • Část 1: $ L \in NTIME(T(n)) $ pak existuje jednopáskový NTS s časovou složitostí $ (T(n))^2 $ přijímajicí L.
  • Část 2: Nechť je L přijímán k-páskovým NTS M s časovou složitostí T(n). Potom existuje 2-páskový NTS M' s časovou složitostí $ T(n) * log_2(T(n)) $ přijímajicí L.

Konstruovatelnost funkcí

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

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

Funkce $ f:\mathbb{N} \rightarrow \mathbb{N} $ je vyčíslitelná v prostoru O(f) 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.

see also Složitost#Konstruovatelné funkce
Tato část je neúplná a potřebuje rozšířit. Tady toho spousta chybí. Důkazy ekvivalencí a rychlosti růstu časově konstruovatelných fcí.

Hierarche tříd složitsti

Časová hierarchie

Tato část je neúplná a potřebuje rozšířit. Otevřenost shora.

Prostorová hierarchie

Tato část je neúplná a potřebuje rozšířit. Otevřenost shora.

Věty o vzazích a hierarchii tříd

Tato část je neúplná a potřebuje rozšířit. To co se pouzivá v písemce

Pozor ve Strojilovi je preklep u rozsirene vety o vztazich, pise se tam NTIME ⊆ NSPACE. Spravne je to NTIME ⊆ DSPACE. Dukaz je pritom spravne - pouziva DTS. Ten "překlep" platí samozřejmě též. Jen s DSPACE je to tvrzení silnější.

Savičova věta

Nechť $ S:\mathbb{N} \rightarrow \mathbb{N} $ je prostorově konstruovatelná funkce taková, že $ S(n) \geq log_2(n) $. Potom $ NSPACE(S(n)) \subseteq DSPACE(S^2(n)) $

Důkaz

Nejprve ukážeme, že pro uložení konfigurace NTS, který pracuje v prostoru S(n), nám stačí prostor velikosti O(S(n)). Libovolný NTS, který pracuje v prostoru S(n), převedeme na DTS, který pracuje v prostoru $ S^2(n) $. Pro tento převod využijeme jednoduchý algoritmus, který pomocí backtackingu hledá cestu z počáteční do přijímací konfigurace původního NTS. Ukážeme, že tento algoritmus potřebuje prostor nejvýše $ O(S^2(n)) $. Tento prostor je využit jako zásobník (maximální hloubky O(S(n))) pro backtacking.

Tato část je neúplná a potřebuje rozšířit. Doplnit podrobnosti

Poznámky

Tato část je neúplná a potřebuje rozšířit. Užitečné funkce pro řešení vztahů

Kuriozity

Borodinova věta o mezerách

Nechť $ g: \mathbb{N} \rightarrow \mathbb{N}, g(n) \geq n $, g je rekurzivní fce. Potom existuje rekurzivní fce S(n) taková, že DSPACE(S(n)) = DSPACE(g(S(n)))

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í) 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}) $


Č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 $
2log(c)*log(n)=nkonst. ... NS vs. DT
  • $ PSPACE=NPSPACE $
ni vs. n2*i ... Savič
  • $ NP \subseteq PSPACE $
NT vs. DS vs. PSPACE
  • $ PSPACE \subseteq EXPTIME $
2log(c)*ni << 2n(i+1) ... log(c)>n je jen pro konečně mnoho případů
  • $ NLOG \subset PSPACE \subset EXPSPACE $
NLOG ⊂ PSPACE ... Savič + DS(log2(n)) ⊂ DS(n)
PSPACE ⊂ EXPSPACE ... PSPACE ⊆ DSPACE(ni) ⊆ DSPACE(2n) ⊂ DSPACE(22*n) ⊆ EXPSPACE
DSPACE(ni) ⊆ DSPACE(2n) ještě není ostře!
  • $ P \subset DEXT \subset EXPTIME $
∀ i: DT(ni) ⊂ DT(2n) ... 2n ∈ ω(ni*log(ni))
P ⊆ DT(2n) ⊂ DT(22*n) ⊆ DEXT ... 22*n ∈ ω(2n*log(2n))
∀ c: DT(2c*n) ⊂ DT(2n2)
DEXT ⊆ DT(2n2) ⊂ DT(2n3) ⊆ 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í.

Turingovy stroje s oráculem

DTS s oráculem A, kde A je jazyk, se liší od běžného DTS:

  • má navíc dotazovací pásku na kterou může zapisovat (Používá abecedu jazyka A).
  • má navíc stavy: DOTAZ,ANO,NE.
  • pokud stroj dojde do stavu DOTAZ tak v následujicím kroku přejde do stavu:
    • ANO - pokud slovo na dotazovací pásce patří do A.
    • NE - pokud slovo na dotazovací pásce nepatří do A.
  • dotazovací páska je vymazána (To vše v jednom kroku stroje).
  • Jazyk přijímany DTS M s orákulem A značíme L(M,A).


  • DTS bez orákula je možné chápat jako s orákulem A = 0.
  • NTS je slabší než DTS s orákulem.
    • A = {(x,y) | DTS s kódem x se zastaví nad vstupem y} - DTS s orákulem A rozpoznává A ale A je algoritmicky nerozhodnutelny. (A je tzv. "halting problem". Definici algoritmicke nerozhodnutelnosti + dukaz, ze A je alg. nerozhod. viz Vycislitelnost 1)


  • Každý NTS lze simulovat pomocí DTS s orákulem.
    • Zadefinujeme jazyk A = { x | x je kód počátečního úseku nějakého výpočtu stroje M takového, že ho lze prodloužit na přijímajicí výpočet bez opakování konfigurace}.
    • Simulace: pro aktuální konfiguraci postupně zkoušíme jednotlivé přechody a pomocí dotazu zda prodloužený seznam konfigurací patří do A navigujeme výpočet.
    • podle Trckapress poznamek staci rict ze orakulum bude rozpoznavat totez co dany NTS... DTS jen opise vstup na dotaz. pasku, polozi dotaz a skonci :)

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

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


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

Tato část je neúplná a potřebuje rozšířit. Co znamena "nerelatizované" resp. "relatizované"?

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

  • 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


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


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.

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


Obdobné definice lze udělat také pro PSPACE(Ƈ),LOG(Ƈ),..


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

Σ0 = Ƥ a ∀ k ≥ 0 : Σk+1 = NP(Σk).

Čili:

  • Σ1 = ƝƤ
  • Σ2 = NP(ƝƤ)

Potom polynomiální hierarchie je definována: $ PH = \bigcup_{k\ge 0}\Sigma_k $

Poznámka:

  • Pokud Ƥ = ƝƤ tak PH = Ƥ
  • Pokud ƝƤ = NP(ƝƤ) tak PH = ƝƤ
  • Kolabuje někde polynomiální hierarchie? Nikdo neví.

Věta: PH ⊆ PSPACE

Důkaz

Indukcí podle k.

  • k = 0.
    • Ƥ ⊆ PSPACE.
  • nechť ∀ i ≤ k; Σi ⊆ PSPACE.
    • Σk+1 = NP(Σk) ⊆ NP(PSPACE) ⊆ PSPACE(PSPACE) // posledni krok diki Lema 1
    • PSPACE(PSPACE) ⊆ PSPACE protože můžeme oba stroje zřetězit a prostor nam bude stačit.


PSPACE(PSPACE)=$ \left \{ B: \exists \; A \in PSPACE: B \le_{PSPACE} A \right \} $=PSPACE

  • Dotaz na orákulum nahradíme výpočtem DTS
    • Dotazovací páska je naplněna vypočtem stroje probíhajícím v PSPACE
    • Dotazovací stroj běží v PSPACE
    • Polynom z polynomu je polynom (krásná věta ;o)
    • Dotazů může být hodně, ale prostor na jejich řešení lze recyklovat.

Převoditelnost a úplnost

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


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).


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


Template na defnice převoditelnosti

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


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 možného důsledku Ƥ-úplnosti

Víme LOG ⊆ Ƥ

Pokud L je Ƥ-úplný a L ∈ LOG tak ptom Ƥ⊆LOG

Důkaz

L' ∈ Ƥ a ∃ log-space transducer: y∈L<=>x∈L'

log-space transducer M pracuje ale v prostoru LOG(|y|). Jak moc může být LOG(|y|) velké? My potřebujme LOG(|x|).

|y|<=Počet konf. stroje M<=2d*log(n) pro vhodné d. Stroj necyklí.

L∈LOG: Existuje stroj M' přijímající ho v log. prostoru.

log2(2d*log(n))=log(n)*d

To lze zkompresit na log(n)

Pozn. Stroje M a M' nelze jen tak zřetězit, ale lze adresovat po písmenku pro potřebný znak.

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

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

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

QBF-problém

  • vstup: QBF bez volných proměných.
  • výstup: true/false.

QBF - kvantifikované boolovské formule.


Lemma: QBF ∈ PSPACE.

Důkaz:

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, a každý takový záznam je jen polynomiálně velký v n.

Celkový použitý prostor je polynomiální.

To dokazuje ze QBF ∈ PSPACE. Zel tu ale neni dukaz toho, ze kazdy Q ∈ PSPACE je na QBF v pol. case prevoditelny! (Coz by spolu znamenalo, ze QBF je PSAPCE-uplny). Je ale v knihe C. H. Papadimitriou: "Computational Complexity", na stranach 456 - 458, cize trochu drsne, asi to nikdo nikdy na matfyze nebude chciet.


Poznámka: Pokud CNF doplním pouze existenčními kvantifikátory, dostanu QBF kterou když vyřeším, mám i odpověď na SAT (ale máme jen že je NP-těžký, jeho NP-úplnost nevíme).

Odkazy