Složitost II

Z ωικι.matfyz.cz
Verze z 21. 6. 2014, 18:42, kterou vytvořil Ivan Kuckir (diskuse | příspěvky) (Lemma (o lineárním zrychlení))

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

Obsah

Obecné informace o předmětu

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

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.

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

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

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

Znění (1.verze)

Pokud platí $ inf_{n \rightarrow \infty} \frac{T(n)}{n} = \infty $ nebo $ T(n) = cn $ a c > 1. A nechť L je jazyk 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

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

Důsledek

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

Znění (2.verze)

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íma páskama a časovou složitostí $ T(n)log_2T(n) $ přijímajicí L.

Důkaz

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

Příklad uspořádání dat na zaplněné pásce
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 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ůsledek

  • 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 Konstruovatelné funkce v státnicových materiálech
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.

Deterministická prostorová hierarchie

Mějme funkce S1 a S2.

S1o(S2) a S2 je prostorově konstruovatelná.

Potom platí: DSPACE(S1) ⊂ DSPACE(S2)

Nedeterministická prostorová hierarchie (pro polynomy)

∀ r >= 1 ∀ ε > 0:

NSPACE(nr) ⊂ NSPACE(nr + ε)

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ší.

This shows real exeptrsie. Thanks for the answer.

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

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 $
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í.

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

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.

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 Ƥ-ú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. V anglicke terminologii se tomu taky rika (bez tech volnych promennych) TQBF.


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.

JM ta konstrukce je velmi podobna dukazu Savicovy vety jen misto procedury TEST mame FORMULI_TEST. Neni tomu nahodou, TQBF je uplny problem nejen pro PSPACE ale i pro NPSPACE (se stejnou konstrukci) a tedy se takhle da taky dokazat ze NPSPACE = PSPACE. A taky je to celkem dobre vysvetleny na anglicky wiki


Lemma: ∀ L ∈ PSPACE : L lze polynomiálně převést na QBF

Idea: Jestliže L ∈ PSPACE, potom existuje DTS M, který rozhoduje L v nějakém polynomiálním prostoru S(n). Důkaz se provede tak, že ukážeme jak zkonstruovat QBF φ, takovou, že φ = true iff M vrací 1.

Jak se to udělá je popsáno na 1 stránce v knize Arora, Barak: Computational Complexity: A Modern Approach.


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