Složitost II: Porovnání verzí

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
(zUQZsVmTkT)
(Revert spam.)
Řádka 512: Řádka 512:
  
 
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).
 
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).
 
xBEKG0  <a href="http://tagmxpwbghmk.com/">tagmxpwbghmk</a>
 
 
NJUsHU , [url=http://hrolnuyrwuwt.com/]hrolnuyrwuwt[/url], [link=http://opvdrobctocj.com/]opvdrobctocj[/link], http://vdqoicbiexbg.com/MxigUb , [url=http://zpacwvdppeai.com/]zpacwvdppeai[/url], [link=http://aqibivjhsjih.com/]aqibivjhsjih[/link], http://amaxtpzbdnmx.com/
 

Verze z 24. 10. 2012, 15:06

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.

Learning a ton from these neat artlcies.

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

Hi all,I have put my adsense pub and chnael ID on the config.php files and the adsense does not seem to show up. I am not even getting any page impressions (I know that I am having visitors). Can you please help and tell me what could possibly be wrong. I'd really appriciate your answer. Thank you in advanceArian

Home run! Great slugging with that asnwer!

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 $

Articles like this are an example of quick, helufpl answers.

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í $ lim_{n \rightarrow \infty} \frac{T(n)}{n} = \infty $ (tedy $ T(n)\in \omega(n) $). Potom ∀ c > 0 existuje (k+1)-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+1)-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

Nabedzedme nebankovned půjčky se ze1stavou neitvmtosoi. Půjčky se jisted vlastned nemovitosted nebo nemovitosted jine9 osoby: dům, byt v OV, nebo DB po cele9 ČR. Dlouhodobe9 půjčky do 5 dnů. Rychle9 kre1tkodobe9 půjčky a favěry s nebankovnedch sektoru do 2 dnů. Nabedzedme podnikatelske9 favěry, konsolidace, oddlužened a refinance. Vyple1cedme nevfdhodne9 ze1stavy, dražby a exekuce. Nebankovned půjčky bez potvrzened předjmu ani registru. Bez poplatků!Tel. 608192902

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.

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


Č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 Halting problem)


  • Každý NTS lze simulovat pomocí DTS s orákulem.
    • Podle Trckapress poznamek staci rict ze orakulum bude rozpoznavat totez co dany NTS... DTS jen opise vstup na dotaz. pasku, polozi dotaz a skonci :)
    • Druha moznost: 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.

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.

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

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

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

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.

Definice pomocí orákul

FIXME: Σ jsou třídy NP strojů s orákuly, tedy problémů "začínajících" existenčním kvantifikátorem. Podobně Π popisuje třídy co-NP strojů s orákuly, tedy problémů začínajících univerzálním kvantifikátorem, a Δ popisuje třídy P strojů s orákuly, tedy TODO intuice.

Σ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í. Speciálně kolaps na první úrovni by znamenal P=NP.

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

Got it! Thanks a lot again for helipng me out!

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.

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