Latest revision as of 16:10, 1 December 2012

[edit] Obecné informace o předmětu

[edit] Zápočet

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

Learning a ton from these neat artlcies.

[edit] 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.

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

[edit] 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

[edit] Č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!

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

[edit] 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.

Informacje na zakładkach są z zeszłego roku!!Jeśli chcecie mieć inajrmfcoe jakim jesteście super zastępem wyślijcie mi inajrmfcoe na webmaster.jaworzyna@vp.pl w e-mailu zamieście:-informacje,+ o was+ i nazwie zastępu np.: Świstaki są słodkie ,a w razie niebezpieczeństwa wydają z siebie śśśśwwwiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiissssssssssssssssssssttttttttttttt -nazwę zastępuczekam na wasze e-maile WEBmasTERka

[edit] Lemma o lineárním zrychlení

[edit] 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.

[edit] 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.

This wsebite makes things hella easy.

[edit] 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

[edit] Důkaz

Část 1:

• Pokud platí $ inf_{n \rightarrow \infty} \frac{T(n)}{n} = \infty $ použiji větu o lineárním zrychlení (část 1) s $ c = \sqrt{\frac{1}{2k}} $ a poté redukuji počet pásek stejným způsobem jako v důkazu věty o redukci počtu pásek pro prostorovou složitost.
• Pokud platí T(n) = cn s $ c > \sqrt{2k} $ použiji větu o lineárním zrychlení (část 2) a pak stějně jako v předchozím případě.

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

[edit] 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.

[edit] 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 č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á 1^f(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

[edit] Hierarche tříd složitsti

[edit] Časová hierarchie

[edit] Prostorová hierarchie

[edit] Deterministická prostorová hierarchie

Mějme funkce S₁ a S₂.

S₁ ∈ o(S₂) a S₂ je prostorově konstruovatelná.

Potom platí: DSPACE(S₁) ⊂ DSPACE(S₂)

[edit] Nedeterministická prostorová hierarchie (pro polynomy)

∀ r >= 1 ∀ ε > 0:

NSPACE(n^r) ⊂ NSPACE(n^{r + ε})

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

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.

[edit] Poznámky

[edit] Kuriozity

[edit] 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)))

[edit] 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.

[edit] 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é.

[edit] 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}) $

[edit] 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.

[edit] 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ů.

[edit] 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.

[edit] 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

[edit] 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

[edit] 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é

[edit] 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.

The accident of finindg this post has brightened my day

Quick question. Would I be able to use this theme with a bbPress iliatlnatson as well? I have been putting off creating a theme for bbPress and would love to use your light version as a starting point.

[edit] 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ý).

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

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

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

[edit] 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).RA0oFV , [url=http://dazegxkrtnlu.com/]dazegxkrtnlu[/url], [link=http://gqsssfszvffh.com/]gqsssfszvffh[/link], http://xhngavmttrdc.com/1d3uKL <a href="http://vmxzljqrwkhb.com/">vmxzljqrwkhb</a>