Státnice - Informatika - Složitost: Porovnání verzí

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
(FifLiGCzSHYALd)
 
(Není zobrazeno 71 mezilehlých verzí od 35 dalších uživatelů.)
Řádka 1: Řádka 1:
Fraklny I think that's absolutely good stuff.
+
''Tento souhrn slouží pro přípravu k magisterským [[Státnice|státnicím]] pro obory [[Státnice - Informatika - I1: Teoretická informatika|Teoretická informatika]] a [[Státnice - Informatika - I4: Diskrétní modely a algoritmy|Diskrétní modely a algoritmy]]. Detailní informace o předmětu hledej na stránkách [[Složitost I]] a [[Složitost II]].''
 +
 
 +
== Rozsah látky ==
 +
Seznam [http://www.mff.cuni.cz/studium/bcmgr/ok/i3b4.htm oficiálních] státnicových otázek pro studijní obory [[Státnice - Informatika - I1: Teoretická informatika|Teoretická informatika]] a [[Státnice - Informatika - I4: Diskrétní modely a algoritmy|Diskrétní modely a algoritmy]] (aktualizováno 2013):
 +
: Věty o hierarchii tříd složitosti, konstruovatelné funkce, vztahy mezi časovými a prostorovými mírami a determinismem a nedeterminismem, Savitchova věta. Úplné problémy pro různé třídy (NP, PSPACE, P, #P). Polynomiální hierarchie, pseudopolynomiální algoritmy, silná NP-úplnost, třída #P a #P-úplnost. Aproximační algoritmy a schémata. Metody tvorby algoritmů: dynamické programování, hladový algoritmus na matroidu. Základy pravděpodobnostních algoritmů.
 +
 
 +
Studijní obory [[Státnice - Informatika - I2: Softwarové systémy|Softwarové systémy]] a [[Státnice - Informatika - I3: Matematická lingvistika|Matematická lingvistika]] mají okruhy [[Státnice - Informatika - Složitost (obory Matematická lingvistika a Softwarové systémy)|Složitost]] a [[Státnice - Informatika - Vyčíslitelnost|Vyčíslitelnost]] do spojeny do jednoho a rozsah otázek pro složitost se liší.
 +
 
 +
== Zdroje obecně ==
 +
 
 +
Většina je pokryta přednáškami Složitost I a II, některá témata je však třeba dohledat jinde (klidně po internetu, na wikipedii, [http://ktiml.mff.cuni.cz/teaching/files/materials/VladanMajerech_UvodDoSlozitostiANPuplnosti.pdf v Majerechovi], v zahraničních skriptech...). Pozor, Čepkovy slajdy jsou více než stručné.
 +
 
 +
Vřele doporučuji strávit jedno odpoledne v knihovně s knížkou od [http://www.cs.duke.edu/~reif/courses/complectures/books/AB/ABbook.pdf Arory a Baraka Computational Complexity: A Modern Approach]. Velmi názorně pomůže získat dobrou intuici u téměř všech okruhů a rigorózní důkazy se tam člověk venkoncem také dočte.
 +
 
 +
[http://popelka.ms.mff.cuni.cz/cerno/index.php?menu=notes&lang=en Poznámky od Peter Černo]
 +
 
 +
== Věty o zrychlení a o mezerách ==
 +
=== Věta o lineárním zrychlení ===
 +
:''see [[Složitost II#Věta o lineárním zrychlení]] (asi i [[wen:Linear speedup theorem]])''
 +
 
 +
* DTS s alespoň dvěma páskami se na vstupu délky n dá zrychlit z t kroků na <math>n + \lceil n/r \rceil + 6 \lceil t/r \rceil</math> (<math>r \in \mathbb{N}</math>)
 +
** postup: nový stroj stlačí ''r'' políček původní pásky na jedno -- nejdřív okopíruje a přejede na začátek (<math>n + \lceil n/r \rceil</math> kroků), pak simuluje v šesti krocích ''r'' kroků původního stroje: nejdřív načte tři svoje políčka (3r políček původního stroje; trvá 4 kroky nového [vlevo,vpravo,vpravo,vlevo]), pak zjistí, jak budou vypadat po ''r'' krocích (jen ve vnitřním stavu), a nakonec to zapíše (další max 2 kroky, za ''r'' kroků starého se stihnou změnit nejvýše dvě políčka nového stroje)
 +
* Je-li L jazyk přijímaný k-páskovým DTS M (k>=2) a s časovou složitostí <math>t(n) \in \omega(n)</math>. Potom pro každé kladné c existuje k-páskový M' s časovou složitostí c*t(n) přijímající L.
 +
** Vezmeme r > 12/c, uděláme M' jako výše, doba jeho běhu nad vstupem délky n se dá pro r>2 shora odhadnout výrazem (c/2)*t(n)+(6/r)*t(n) (z <math>t(n) \in \omega(n)</math>), což z r>12/c dává omezení doby běhu c*t(n) pro skoro všechna n. Konečný počet výjimek se ošetří konečným automatem.
 +
* Nechť je L jazyk přijímaný k-páskovým DTS M s časovou složitostí t(n) = c*n. Dále ať k>=2 a c>1. Pak <math>\forall \epsilon > 0</math> existuje k-páskový DTS M' s časovou složitostí <math>(1+\epsilon)\cdot n</math> přijímající L.
 +
 
 +
If time is money you've made me a wealtiehr woman.
 +
 
 +
== Věty o hierarchii tříd složitosti ==
 +
:''see [[Složitost II#Základní třídy složitosti]], [[wen:Complexity class]], [[http://blog.computationalcomplexity.org/2004/07/time-and-space-hierarchies.html]]''
 +
 
 +
=== Otevřenost časové hierarchie shora ===
 +
Nechť T je rekurzivní funkce (tj. existuje TS, který ji vyčísluje). Potom existuje rekurzivní jazyk L takový, že <math>L \notin DTIME(T(n))</math>.
 +
 
 +
Důkaz přes jazyk <math>L = \{ x_i : M_i \mbox{ nepřijímá } x_i \mbox{ v čase } T(|x_i|) \} \ </math>, (máme očíslované řetězce i Turingovy stroje). Přítomnost v L se dá otestovat pomocí TS co si odsimuluje T(|x|) kroků příslušného stroje, L je tedy rekurzivní.
 +
 
 +
Pokud by platilo <math>L \in DTIME(T(n))</math>, tak by existoval TS M, který rozpozná L v čase T(n). Ten stroj má nějaké číslo i. (Tj. <math>M=M_i</math>.). Pak platí jedno z:
 +
# <math>x_i \in L</math>, tj. stroj M přijme <math>x_i</math> v čase <math>T(|x_i|)</math> (protože ho poznává). Zároveň ale z stroj <math>M_i</math> <math>x_i</math> v čase <math>T(|x_i|)</math> nepřijímá (z definice L). Máme spor, protože M a <math>M_i</math> je ten samý.
 +
# <math>x_i \notin L</math>, takže ho M (rozpoznávač L) v daném čase nepřijme, ale <math>M_i</math> (ten z definice L) ho v daném čase přijmout musí, tj. taky spor.
 +
:(tj. vyzkoušíme, co řekne <math>M_i</math> na jemu příslušející řetězec <math>x_i</math>)
 +
 
 +
Proto <math>L \notin DTIME(T(n))</math>.
 +
 
 +
=== Otevřenost prostorové hierarchie shora ===
 +
Nechť S je rekurzivní funkce. Potom existuje rekurzivní jazyk L takový, že <math>L \notin DSPACE(S(n))</math>.
 +
 
 +
Důkaz je analogický jako u časové hierarchie, vyrobí se jazyk <math>L = \{ x_i : M_i \mbox{ nepřijímá } x_i \mbox { v prostoru } S(|x_i|) \}</math>. Rozdíl je jen v simulaci <math>M_i</math>, který se navíc může na svém omezeném prostoru zacyklit, což se ale dá detekovat, neb tam má omezený počet konfigurací.
 +
 
 +
=== Věty o časové a prostorové hierarchii ===
 +
==== O prostorové hierarchii ====
 +
Nechť <math>S_1: \mathbb N \to \mathbb N</math> a <math>S_2: \mathbb N \to \mathbb N</math> jsou funkce takové, že <math>S_2 \in \omega(S_1)</math>, <math>S_2</math> je prostorově konstruovatelná a <math>S_1(n) \ge log_2(n)</math>. Potom existuje jazyk L takový, že <math>L \in DSPACE(S_2) \setminus DSPACE(S_1)</math>.
 +
 
 +
To s omegou znamená že <math>S_2</math> není omezená <math>S_1</math> (ani když se přenásobí libovolnou konstantou), celá pointa věty je, že v takto větším prostoru se dají poznat nějaké další jazyky.
 +
 
 +
===== Důkaz =====
 +
We show the existence of a language L such that <math>L \in DSPACE(S_2)</math> but <math>L \notin DSPACE(S_1)</math>.
 +
We define L by describing a Turing machine ML, using space <math>O(S_2(n))</math>, that decides it. ML does
 +
the following on input w = (M, y) of length <math>|w| = n</math>:
 +
 
 +
# Run M(w) with at most <math>S_2(n)</math> space and for at most <math>2^{2S_2(n)}</math> steps (these bounds are imposed on M), using space at most <math>3·S_2(n)</math>.
 +
# If M(w) accepts within the given time and space bounds, then reject. Otherwise, accept.
 +
 
 +
In step 1, we can use the fact that <math>S_2</math> is space constructible to mark off exactly <math>S_2(n)</math> tape cells for M to use.
 +
We can similarly mark off an additional <math>2S_2(n)</math> cells to use as a counter for checking the
 +
number of steps M makes, and one last set of <math>S_2(n)</math> cells to use for any remaining computation. By
 +
construction, ML uses space <math>\hat S_2(n) = 4 · S_2(n)</math>.
 +
 
 +
We need to show that no machine using space <math>O(S_1(n))</math> can decide L. Assume the contrary.
 +
Then there exists a machine <math>M^{\prime}_L</math> deciding L and using space <math>\hat S_1(n) = O(S_1(n))</math>.
 +
 
 +
Choose k large enough so that <math>\hat S_1(k) < S_2(k)</math>, so that <math>M^{\prime}_L</math> makes fewer than <math>2S_2(k)</math> steps on inputs of length k, and
 +
so that the simulation of <math>M^{\prime}_L</math> on inputs of length k can be performed in <math>S_2(k)</math> space.
 +
Consider the input <math>w = (M^{\prime}_L, 1^k)</math>.
 +
If we run <math>M_L(w)</math> then (1) <math>M_L</math> has enough time and space to simulate the entire execution of <math>M^{\prime}_L(w)</math>, and thus (2) <math>M_L(w)</math> outputs the opposite of whatever <math>M^{\prime}_L(w)</math> outputs.
 +
We conclude that <math>M_L</math> and <math>M^{\prime}_L</math> do not decide the same language.
 +
 
 +
==== O časové hierarchii ====
 +
 
 +
Nechť <math>T_1: \mathbb N \to \mathbb N</math> a <math>T_2: \mathbb N \to \mathbb N</math> jsou funkce takové, že <math>T_2 \in \omega(T_1 \cdot \log T_1)</math> a <math>T_2</math> je časově konstruovatelná. Potom existuje jazyk L takový, že <math>L \in DTIME(T_2) \setminus DTIME(T_1)</math>.
 +
 
 +
== Konstruovatelné funkce ==
 +
:''see also [[Složitost II#Konstruovatelnost funkcí|Složitost II]]''
 +
 
 +
* Funkce <math>f:\mathbb{N} \rightarrow \mathbb{N}</math> je ''rekurzivní'' pokud existuje DTS M takový, že pro vstup 1<sup>n</sup> vydá výstup 1<sup>f(n)</sup>.
 +
* Funkce <math>f:\mathbb{N} \rightarrow \mathbb{N}</math> je ''vyčíslitelná v čase O(f)'' pokud f je rekurzivní a &exist; c &ge; 1 takové, že příslušný DTS udělá nejvýše cf(n) kroků než vydá 1<sup>f(n)</sup>.
 +
* Funkce <math>f:\mathbb{N} \rightarrow \mathbb{N}</math> je ''vyčíslitelná v prostoru O(f)'' pokud f je rekurzivní a &exist; c &ge; 1 takové, že příslušný DTS použije při práci prostor nejvýše cf(n).
 +
* Funkce <math>f:\mathbb{N} \rightarrow \mathbb{N}</math> 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) &ge; n + 1<ref>Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach [draft January 2007]. Remark 1.5, page 1.7 (17).</ref>).
 +
* Funkce <math>f:\mathbb{N} \rightarrow \mathbb{N}</math> je ''prostorově konstruovatelná'' pokud existuje DTS M takový, že pro každý vstup délky n zastaví s právě f(n) páskovými symboly neprázdnými, přičemž žádný jiný prostor na pracovních páskách nebyl v průběhu výpočtu použit.
 +
 
 +
'''Lemma:''' Nechť <math>f_1+f_2</math> a <math>f_2</math> jsou časově konstruovatelné funkce, dále nechť <math>\exists \varepsilon>0, \exists n_0</math> takové, že <math>\forall n>n_0 : f_1(n) \geq \varepsilon \cdot f_2(n) + (1+\varepsilon)n</math>. Pak <math>f_1</math> je časově konstruovatelná.
 +
: Podobně jako v důkazu věty o lineárním zrychlení zrychlíme výpočet trvající <math>f_1(n)+f_2(n)</math> kroků, aby trval přesně <math>f_1(n)</math> kroků...
 +
 
 +
'''Věta:''' Nechť <math>f:\mathbb N \to \mathbb N</math>, taková, že existuje <math>\varepsilon > 0</math> a <math>n_0</math>, že <math>\forall n \geq n_0: f(n) \geq (1+\varepsilon)n</math>. Pak je f časově konstruovatelná právě tehdy, když je vyčíslitelná v čase O(f).
 +
:Je-li f časově konstruovatelná, pak máme stroj který běží v čase f(n). Můžeme mu přidat pásku, na kterou bude psát po dobu svého běhu jedničky, čímž f vyčíslí.
 +
:Naopak, označíme-li g(n) přesný čas stroje M, který funkci f počítá v čase O(f(n)). (Tedy g(n) < c*f(n) pro skoro všechna n a nějaké c.) Potom g je časem TS M, f + g je časem TS, který "po dopočítání M ještě spočítá počet jedniček na pásce". Funkce g je časově konstruovatelná díky stroji M. Z toho (a z lemmatu výše) plyne časová konstruovatelnost f.
 +
 
 +
'''Věta:''' Funkce f je prostorově konstruovatelná právě tehdy, když je vyčíslitelná v prostoru O(f).
 +
:Doprava nám stačí upravit stroj který f prostorově konstruuje tak, aby při zabrání nového políčka zapsal na novou pásku jedničku.
 +
:Nechť M je k-páskový deterministický Turingův stroj vyčíslující f(n) v prostoru c*f(n). Podle věty o lineární kompresi zkonstruujeme k-páskový stroj M', který vyčísluje f(n) v prostoru přesně f(n). Uvědomte si, že M' vyčísluje f(n), tedy musí pracovat v prostoru alespoň f(n). Stroj M' dále převedeme podle věty o redukci počtu pásek na jednopáskový stroj M'', který již dokazuje prostorovou konstruovatelnost funkce f.
 +
 
 +
;Věta o lineární prostorové kompresi
 +
:Je-li L jazyk přijímaný k-páskovým DTS M v prostoru S(n), pak pro každé přirozené číslo r existuje k-páskový DTS M', který přijímá L v prostoru <math>\lceil S(n)/r \rceil</math>
 +
 
 +
;Věta o redukci počtu pásek pro prostorovou složitost
 +
:Je-li L jazyk příjímaný k-páskovým DTS M v prostoru S(n), pak existuje jednopáskový DTS M', který přijímá L v prostoru S(n).
 +
 
 +
'''Důsledek:''' Každá časově konstruovatelná funkce je také prostorově konstruovatelná.
 +
: Funkce f je časově konstruovatelná, tedy je vyčíslitelná v čase O(f), tím spíše je vyčíslitelná v prostoru O(f) a z věty výše je tedy i prostorově konstruovatelná.
 +
 
 +
== Vztahy mezi časovými a prostorovými mírami a determinismem a nedeterminismem ==
 +
DSPACE(S(n)), DTIME(T(n)), NSPACE(S(n)), NTIME(S(n)) -- třídy jazyků (ne)deterministické časové/prostorové složitosti T(n)/S(n).
 +
 
 +
Triviální vztahy
 +
* <math>\forall F_1(n) \leq F_2(n) \Rightarrow XXX(F_1(n)) \subseteq XXX(F2(n))</math>, kde XXX je něco z [DN](SPACE|TIME)
 +
 
 +
=== Věta o vztazích mezi třídami složitosti ===
 +
# <math>DTIME (f(n)) \subseteq NTIME(f(n))</math><br/><math>DSPACE (f(n)) \subseteq NSPACE(f(n))</math>
 +
#* triviálně platí
 +
# <math>DTIME(f(n)) \subseteq DSPACE(f(n))</math>
 +
#* z vět o lineární kompresi a redukci počtu pásek
 +
#* (IMHO si stačí uvědomit, že prostor je vždy omezen spotřebovaným časem)
 +
# <math>NTIME(f(n)) \subseteq DSPACE(f(n))</math>
 +
#* postupně generujeme f(n)-tice možných průchodů (v každém kroku max r možností, r=max|{přechodová funkce}|) jako graf průchodu výpočtem a výpočet simulujeme DTS podle toho -- simulace potřebuje DSPACE(f(n)) (třeba podle předchozího bodu), uloženi f(n)-tice potřebuje <math>log_2(r) * f(n)</math> místa, tj. taky DSPACE(f(n)), a tenhle prostor se dá použivat pro jednotlivé simulace stejný. Celkem tedy <math>DSPACE(f(n))</math>.
 +
# <math>L \in DSPACE(f(n))</math> a <math>f(n) \geq log_2(n)</math>, pak <math>L \in DTIME(C_L^{f(n)})</math>, kde C<sub>L</sub> je konstanta závislá na jazyku L
 +
#* Nechť M je jednopáskový stroj poznávající L v prostoru f(n). Počet jeho konfigurací je omezen <math>s \cdot (n+1) \cdot (f(n)+1) \cdot t^{f(n)} \leq d^{f(n)}</math>, pro vhodné <math>d</math> (<math>s</math> je počet stavů, <math>t</math> je počet páskových symbolů, člen (n+1) asi? pro pozici hlavy na vstupní pásce).
 +
#*Zkonstruujeme M', který simuluje M a nejvýše po <math>d^{f(n)}</math> krocích se zastaví. (Potřebujeme předpoklad časové konstruovatelnosti funkce f.)
 +
# <math>L \in NSPACE(f(n))</math> a <math>f(n) \geq log_2(n)</math>, pak <math>L \in DTIME(C_L^{f(n)})</math>, kde C<sub>L</sub> je konstanta závislá na jazyku L
 +
#* Počet konfigurací opět omezen nějakým <math>d^{f(n)}</math>. Vygenerujeme graf, vrcholy=stavy (tj. omezené), hrana=přechod jedním krokem (konstanta*|stavy|, protože přechodová funkce je konečná). Pak se graf projde a zjistí, jestli tam je přijímací výpočet.
 +
# <math>L \in NTIME(f(n))</math>, pak <math>L \in DTIME(C_L^{f(n)})</math>, kde C<sub>L</sub> je konstanta závislá na jazyku L
 +
#* Nechť M je k-páskový NTS, který poznává L v čase f(n). Počet jeho konfigurací je omezen <math>s \cdot (f(n)+1)^k \cdot t^{k \cdot f(n)} \leq d^{f(n)}</math> pro vhodné <math>d</math> (<math>s</math> je počet stavů, <math>t</math> páskových symbolů).
 +
#* Zkontruujeme DTS M', který vygeneruje seznam všech konfigurací dosažitelných z počáteční konfigurace, což lze provést v kradratickém čase vzhledem k délce výsledného seznamu. Tato délka je omezena součinem počtu konfigurací a délky zápisu jedné konfigurace. Tedy <math>l \leq d^{f(n)} \cdot (k \cdot f(n) + 1 + k \cdot \log f(n)) \leq c^{f(n)}</math>. M' je pak schopný poznat jestli je dosažitelná nějaká přijímající konfigurace, počet jeho kroků je omezen <math>c^{2 f(n)}</math>.
 +
 
 +
== Savitchova věta ==
 +
:''see [[wen:Savitch's theorem]]''
 +
 
 +
Nechť <math>S:\mathbb{N} \rightarrow \mathbb{N}</math> je prostorově konstruovatelná funkce taková, že <math>S(n) \geq log_2(n)</math>. Potom <math>NSPACE(S(n)) \subseteq DSPACE(S^2(n))</math>.
 +
 
 +
:Pokud NTS M přijímá jazyk L v prostoru S(n), pak existuje konstanta <math>C_L</math> taková, že M má nejvýše <math>C_L^{S(n)}</math> konfigurací. Počet kroků přijímajícího výpočtu pak bude nanejvýš <math>C_L^{S(n)} = 2^{S(n) \log C_L}</math>.
 +
:Pak definujeme proceduru <math>TEST(I_1, I_2, i)</math>, která zkoumá, jestli se ze stavu <math>I_1</math> dá přejít do stavu <math>I_2</math> za maximálně <math>2^i</math> kroků. (Dělá to rekurzivně -- pro i=0 ověří jestli jsou stavy shodné nebo existují přímý přechod a vrátí výsledek, jinak pro každý stav <math>I_x</math> pouští <math>TEST(I_1, I_x, i-1)</math> a <math>TEST(I_x, I_2, i-1)</math> a zkoumá jejich výsledek.)
 +
:Jedna kopie procedury TEST si musí pamatovat tři konfigurace (jedna konfigurace potřebuje stav, pozici vstupní a výstupní hlavy, a obsah pracovní pásky, to vše O(S(n)) a parametr i (ten se taky vejde do O(S(n)), viz max počet kroků výpočtu).
 +
:Simulace probíhá tak, že pro všechny přijímací stavy <math>I_j</math> voláme proceduru <math>TEST(I_0, I_j, mS(n))</math> (<math>I_0</math> je počáteční konfigurace) a pokud aspoň jednou odpoví ''true'', vstup přijmeme.
 +
:Pracovní páska pak funguje jako zásobník parametrů procedury TEST, která se zahloubí nanejvýš O(S(n)), takže se celý výpočet vejde do prostoru <math>O(S^2(n))</math>
 +
 
 +
== Úplné problémy pro třídy NP, PSPACE ==
 +
:''see [[wen:NP-complete]], [[wen:PSPACE-complete]]''
 +
 
 +
'''Def:''' Problém A je T-těžký, kde T je třída, vzhledem k k-převoditelnosti, pokud <math>\forall B\in T: B\leq_k A</math>.
 +
 
 +
'''Def:''' Problém A je T-úplný, kde T je třída, vzhledem k k-převoditelnosti, pokud je T-těžký a navíc <math>A\in T</math>.
 +
 
 +
'''Převoditelnosti pro různé třídy:'''
 +
* NP - poly time převoditelnost
 +
* P - log space převoditelnost
 +
* PSPACE - poly time převoditelnost
 +
 
 +
'''Úplné problémy pro různé třídy:'''
 +
* NP: Kachličky, SAT; 3-SAT, 3-Color, Klika, NM, VP; VP, HK, TSP; VP, SP
 +
* P: SAT na Hornovských klauzulích, Vyhodnocení obvodu booleovských hradel (CVP)
 +
* PSPACE: SAT na kvantifikovaných klauzulích (QBF-SAT) - splnitelnost SAT kde proměnné můžou být kvantifikované i univerzálním kvantifikátorem (důkaz podobný důkazu Savichovy věty)
 +
* dále typicky hry (zoběcněný [[wen: Hex (board game)]])
 +
 
 +
=== Důkazy různých NP-C===
 +
Pochopitelnější důkazy jsou uvedené v Majerechových skriptách (ke stažení ve [[Studnice vědomostí|studnici]]).
 +
 
 +
Lidsky vysvětlený důkaz Cook-Levinovy věty ("Existuje NP-úplný problém") je [[KACHL|zde]]. Původně je věta formulována pro problém SAT, ale snazší důkaz je pro KACHL a potom ukázat, že KACHL < SAT.
 +
 
 +
Důkaz KACHL < SAT je také v Majerechových skriptách.
 +
 
 +
* SAT < 3-SAT
 +
: Za každou klauzuli s jiným počtem literálů než 3 dáme množinu klauzulí, která dává ekvivalentní podformuli. Vezměme klauzuli c<sub>i</sub>:
 +
:# <math> c_i = (x) </math>, pak <math>
 +
  c_i' := (x \vee y_1 \vee y_2)
 +
  \wedge (x \vee y_1 \vee \bar y_2)
 +
  \wedge (x \vee \bar y_1 \vee y_2)
 +
  \wedge (x \vee \bar y_1 \vee \bar y_2)
 +
</math>
 +
:# <math> c_i = (x_1 \vee x_2) </math>, pak <math>
 +
  c_i' := (x_1 \vee x_2 \vee y)
 +
  \wedge (x_1 \vee x_2 \vee \bar y)
 +
</math>
 +
:# <math> c_i = (x_1 \vee \dotsb \vee x_k) </math> pro <math>k>3</math>, pak <math>
 +
  c_i' :=  (x_1 \vee x_2 \vee y_1)
 +
  \wedge (\bar y_1 \vee x_3 \vee y_2) \wedge \dotsb
 +
  \wedge (\bar y_{i-2} \vee x_i \vee y_{i-1}) \wedge \dotsb
 +
  \wedge (\bar y_{k-3} \vee x_{k-1} \vee x_k)
 +
</math>
 +
 
 +
 
 +
* SAT < Klika
 +
: Graf nad všemi literály formule (opakované literály se budou opakovat i v grafu), hrana mezi každými dvěma literály z různých klauzulí, pokud s nejedná o vzájemnou negaci (x a -x). Hledáme kliku o velikosti jako je počet klauzulí, ta pak pro každou klauzuli určuje splňující literál.
 +
 
 +
* Klika < NM
 +
: Nezávislé množiny odpovídají právě klikám v komplementárním grafu.
 +
 
 +
* NM < VP
 +
: Doplňky vrcholových pokrytí odpovídají právě nezávislým množinám. Důkaz snadno sporem, hrana porušující nezávislost není v doplňku pokryta a naopak.
 +
 
 +
== Početní úlohy, #P a #P-úplnost ==
 +
 
 +
'''Def:''' Funkce f patří do třídy #P pokud existuje binární relace v NPF a platí <math>f(x)=|\{y|(x,y)\in R\}|</math>. f je početní úloha asociovaná s problémem R, píšeme taky #R (např #SAT).
 +
 
 +
'''Věta:''' Každý problém <math>A\in NP</math> má relaci <math>R_A\in NPF</math>, pro kterou platí, že <math>x\in A\Leftrightarrow \#R_A(x)>0</math> - Relace (x,y) y jsou polynomiálně velké certifikáty pro <math>x\in A</math>.
 +
 
 +
Tohle nám dává souvislost #P s NP. Intuitivně bude platit, že NP-úplné problémy budou #P-úplné. Na druhou stranu v #P musí intuitivně být těžké problémy, jejichž rozhodovací problém těžký není. Počítat řešení musí být jistě alespoň tak těžké, jako najít libovolné.
 +
 
 +
Další věty/vlastnosti:
 +
* <math>f\in\#P</math> lze spočítat polynomiálním počtem dotazů na relaci - certifikát je polynomiálně omezený vstupem, tak generuju certifikáty a ptám se relace
 +
* f(x) je v polynomiálním prostoru vzhledem k |x| - počet certifikátů je omezený <math>2^{p(|x|)}</math> takže k binárnímu zápisu nám max stačí p(|x|) bitů
 +
 
 +
'''Def:''' Převoditelnost v #P: Trochu složitější než klasická, protože nepřevádíme jen vstup, ale i výsledek. <math>f(x)\leq_{\#P}g(x)</math> když existují <math>\alpha(x,y), \beta(x)</math> v P takové, že <math>f(x)=\alpha(x,g(\beta(x)))</math>.
 +
 
 +
Pak #P-těžkost téhle převoditelnosti. P-úplnost můžeme definovat ale i pomocí polynomiální převoditelnosti relace A z definice # problému. A tohle je docela důležité pro důkazy převoditelnosti, protože nám to dává souvislost s převody uvnitř NP.
 +
 
 +
'''Věta:''' Pokud máme relaci A v NPF-těžkou (každá relace v NPF lze na A převést), tak problém #A je #P-úplný.
 +
Pozn. NPF-převoditelnost je polynomiální převoditelnost se zachováním řešení: <math>A,B\in NPF</math>, existuje <math>\beta</math> v P tak, že <math>|\{y|(x,y)\in A\}|=|\{y|(\beta(x),y)\in B\}|</math>
 +
 
 +
'''#P-úplný problém:''' #SAT je #P-úplný - jasné, když dostaneme nějaký problém v #P, tak relaci s ním asociovanou umíme převést na SAT (protože SAT je NP-úplný).
 +
 
 +
Zajímavější problém je: #DNF-SAT je #P-úplný - to nám ukazuje to, že <math>NP\neq \#P</math>
 +
 
 +
'''Důkaz:''' DNF-SAT je v PF, takže #DNF-SAT určitě v #P. Když převedeme #SAT na #DNF-SAT tak budeme hotovi (protože #SAT je #P-úplný). Zjevně pro vstup na n proměnných platí: <math>\#KNF-SAT(\phi)=2^n-\#DNF-SAT(\neg \phi)</math> a negaci umíme spočítat polynomiálně pomocí de-morganových pravidel. Funkce <math>\beta(\phi)=\neg\phi</math> a funkce <math>\alpha(\phi,c)=2^n-c</math>.
 +
 
 +
== Polynomiální hierarchie ==
 +
 
 +
:''see [[Složitost II#Polynomiální hierarchie|polynomiální hierarchie]], [[wen:Polynomial hierarchy]], [http://www.cs.umd.edu/~jkatz/complexity/f11/lecture8.pdf Pekne a jednoduche vysvetleni] - souvislost s TQBF a PSPACE, alternujici kvantifikatory.''
 +
:''Dobre je si vygooglit v obrazcich heslo polynomial time hierarchy.''
 +
 
 +
'''Def:''' TS s orákulem A (jazyk) je TS co má navíc pásku, pomocí které může 'zavolat' orákulum pro <math>w\in A</math>. Jazyk slov pro TS M s orákulem A je L(M,A).
 +
 
 +
'''Def:''' Turingovská převoditelnost (pomocí orákula): A je det. turingovsky převoditelný na B pokud existuje DTS M s orákulem B pro nějž A=L(M,B). Značíme <math>A\leq_T B</math>. Obdobně nedet. turingovská převoditelnost <math>A\leq_{NP} B</math>. Například, každý jazyk A v P je tur. převoditelný na prázdný jazyk (na to, jestli je <math>w\in A</math> nepotřebujeme nic než klasický TS z P).
 +
 
 +
'''Def:''' Teď můžeme definovat tzv. Relativizované třídy:
 +
* <math>P(A)=\{B|B\leq_T A\}</math> - všechny jazyky, které můžeme deterministicky rozpoznávat s pomocí orákula jazyka A, např <math>P(\emptyset)=P</math>
 +
* <math>P(C)=\{B|\exists A\in C: B\leq_T A\}</math> - všechny jazyky, které můžeme deterministicky rozpoznávat s pomocí nějakého orákula z třídy C, např <math>P(P)=P</math>
 +
* <math>NP(A)=\{B|B\leq_{NP} A\}</math> - všechny jazyky, které můžeme nedeterministicky rozpoznávat s pomocí orákula jazyka A, např <math>NP(\emptyset)=NP</math>
 +
* <math>NP(C)=\{B|\exists A\in C: B\leq_{NP} A\}</math> - všechny jazyky, které můžeme nedeterministicky rozpoznávat s pomocí nějakého orákula z třídy C, např <math>NP(P)=NP</math>
 +
 
 +
* Pozn: zjevně tyhle třídy můžeme rekurzivně volat samy na sebe P(NP(P)), NP(NP(NP)) apod
 +
 
 +
* Pozn: NP(NP)=? ... nevime! (nemuzem pouzit postup jako u P(P), vypocet simulace nema jednu vetev).
 +
 
 +
Pro každou množinu jazyků platí <math>P(C) \subseteq NP(C) \subseteq PSPACE(C)</math>.
 +
 
 +
'''Def:'''Polynomiální hierarchie - Třídy <math>\Sigma_k, \Pi_k, \Delta_k</math> definované následovně:
 +
# <math>\Sigma_0 = \Pi_0 = \Delta_0 = P</math>
 +
# <math>\Sigma_{i+1} = NP(\Sigma_i)</math>
 +
# <math>\Delta_{i+1} = P(\Sigma_i)</math>
 +
# <math>\Pi_{i+1} = coNP(\Sigma_i)</math> kde coNP je definované klasicky množinově na jazycích <math>coNP(B)=\{A'|A\in NP(B)\}</math>
 +
# <math>PH=\bigcup_{i\geq 0}\Sigma_i</math>
 +
 
 +
Zde je dobré vědět nějaké vztahy mezi jednotlivými třídami. Viz obrázek na anglické wikipedii.
 +
 
 +
Věta: <math>PH = \bigcup_{k\geq 0}\Pi_k = \bigcup_{k\geq 0}\Delta_k</math>.
 +
 
 +
=== PH je v PSPACE ===
 +
;Věta: <math>PH \subseteq PSPACE</math>
 +
 
 +
Dokazuje se indukcí podle i
 +
# i = 0; <math>\Sigma_0 = P \subseteq PSPACE</math>
 +
# předpokládáme, že tvrzení platí pro i (IP), chceme ukázat, že <math>\Sigma_{i+1} \subseteq PSPACE</math>
 +
#: <math>\Sigma_{i+1} = NP(\Sigma_i) \subseteq^{IP} NP(PSPACE) \subseteq^* PSPACE(PSPACE)</math>
 +
#: * -- co poznám v NP, poznám v i PSPACE, a orákulum mám stejné
 +
#: <math>PSPACE(PSPACE) \subseteq PSPACE</math>
 +
#: místo orákula může stroj kolikrát chce pouštět DTS, co si bude vedle psát ve svém polynomiálním prostoru
 +
 
 +
'''Věta:''' O kolapsu PH - Pokud P=NP, tak PH=P
 +
 
 +
{{TODO|Další vzájemné vztahy, alternující kvatifikátory, kolaps PH}}
 +
 
 +
== Pseudopolynomiální algoritmy ==
 +
:''see [[wen:Pseudo-polynomial time]]''
 +
* Nechť je dán rozhodovací problém (úloha, jejímž výstupem je ANO/NE) &pi; a jeho instance ''I''. Def:
 +
**kód(I) .. délka zápisu ''I'' v nějakém kódování (např. binárním)
 +
**max(I) .. velikost největšího čísla v ''I'' (ne jeho kódu)
 +
 
 +
* Alg. řešící &pi; se nazývá ''pseudopolynomiální'', pokud je jeho čas. slož. omezena polynomem v proměnných kód(I) a max(I).
 +
* Pokud je &pi; tž. forall ''I'': max(I)&le;p(kód(I)) potom ''pseudopolynomiální''=''polynomiální''
 +
* Problémy, pro které obě skupiny nesplývají se nazývají ''číselné''. tj. neexistuje polynom ''p'' tž. viz výš
 +
* '''Ne''' však každý ''číselný'' problém lze řešit ''pseudopolynomiálně'' (tzv. ''silně NP-uplné problémy'')
 +
** &pi;<sub>p</sub> omezení na podproblém &pi; tž. platí max(I)&le;p(kód(I)). Pokud &pi;<sub>p</sub> NPÚ, tak &pi; S-NPÚ
 +
** Klika, TSP je S-NPÚ
 +
 
 +
{{TODO|S-NPÚ patří do tohoto požadavku taky!}}
 +
 
 +
== Dolní odhady pro uspořádání (rozhodovací stromy) ==
 +
:''podle http://ksvi.mff.cuni.cz/~topfer/ppt/Progr-11.pdf''
 +
 
 +
popsano v otazkach k Datovym strukturam: [[St%C3%A1tnice_-_Informatika_-_Datov%C3%A9_struktury#Doln.C3.AD_odhady_pro_uspo.C5.99.C3.A1d.C3.A1n.C3.AD_.28rozhodovac.C3.AD_stromy.29]]
 +
 
 +
== Aproximační algoritmy a schémata ==
 +
 
 +
Pozri tiež [[Státnice - Aproximační algoritmy a schémata]]
 +
 
 +
:''see [[wen:Approximation algorithm]], kus na straně 12 z [http://urtax.ms.mff.cuni.cz/~novap2am/poznamky/slozitost.sxw]''
 +
 
 +
*'''Předpoklady''': Každé řešení má nezápornou hodnotu.
 +
 
 +
*'''Značení''': <math>n</math> velikost zadání, C* hodnota ''optimálního'' řešení, C hodnota ''aproximovaného'' řešení
 +
 
 +
=== Definice ===
 +
*'''Poměrová chyba''': <math>\rho(n) \geq max\left\{ \frac{C^*}{C}, \frac{C}{C^*} \right\}</math>
 +
*'''Relativní chyba''': <math>\epsilon(n) \geq \frac{|C-C^*|}{C^*}</math>
 +
**Pozn.: Pokud jsou <math>\rho(n),\epsilon(n)</math> konstanty, tak se obyčejně parametr <math>n</math> vynechává.
 +
 
 +
*'''Aproximační schéma (AS)''' pro optimalizační úlohu je aproximační alg., který pro vstup délky <math>n</math> a číslo <math>\epsilon>0</math> najde řešení s ''relativní chybou'' <math>\epsilon</math>. Může být exponenciální vzhledem k <math>n</math> i <math>1/\epsilon</math>.
 +
 
 +
*'''Polynomiální AS''': AS, které je polynomiální vzhledem k <math>n</math>.
 +
 
 +
*'''Úplně Polynomiální AS (ÚPAS)''': PAS, které je polynomiální i k <math>1/\epsilon</math>.
 +
 
 +
Well done article that. I'll make sure to use it wisley.
 +
 
 +
===Příklady===
 +
 
 +
====Vrcholové pokrytí====
 +
*&rho;=2.
 +
* Stačí v cyklu: Vždy vzít ze ''zbylých'' hran jednu. Oba její vrcholy přidat do pokrytí a odstranit ostatní incidentní hrany.
 +
:'''DK'''<nowiki>:</nowiki> Ať je F množina všech hran vybraných během algoritmu a C nalezené pokrytí. Platí: |C|=2*|F| (každá hrana má 2 vrcholy) a navíc |F|&le;|C*| (optimální řešení musí pokrýt i hrany z F).
 +
:|C|=2*|F| a |F|&le;|C*| potom |C|&le;2*|C*|
 +
 
 +
 
 +
==== ÚPAS pro součet podmnožiny ====
 +
*Je dána konečná podmnožina množ. přirozených čísel A s prvky x<sub>i</sub>, hodnota součtu ''t'' a aproximační parametr 0<&epsilon;<1.
 +
*Součet L+x označuje seznam vzniklý ze seznamu L přičtením hodnoty ''x'' ke všem jeho položkám. Zachovává uspořádání.
 +
*''Prořezat'' seznam L s parametrem &delta; znamená, že pro každý odstraněný prvek ''y'' existuje v prořezaném seznamu L<nowiki>'</nowiki> prvek ''z'' splňující<nowiki>:</nowiki> (1-&delta;)y &le; z &le; y. Zachovává uspořádání.
 +
*Algoritmus řešení:
 +
'''APPROX_SP(A,t,&epsilon;)''':<br>
 +
L<sub>0</sub>=(0)
 +
'''for''' i = 1 '''to''' n '''do'''
 +
  L<sub>i</sub>=MERGE(L<sub>i-1</sub>, L<sub>i-1</sub>+x<sub>i</sub>) //vytvoří nový a slitím původního a součtu původního
 +
  L<sub>i</sub>=PRUNE(L<sub>i</sub>, &epsilon;/''n'') //prořeže
 +
  L<sub>i</sub>=CROP(L<sub>i</sub>, ''t'') //odstraní prvky větší než ''t''
 +
'''end'''
 +
'''return''' L<sub>n</sub> //vrátí řešení
 +
*Prořezávání s parametrem &epsilon;/''n'' zajišťuje nepřekročení výsledné meze chyby &epsilon;, která se může kumulativně zvětšovat v každé iteraci. 
 +
*Časová složitost algoritmu je <math>O\left(\frac{n^2\cdot log~t}{\epsilon}\right)</math> (v nejhorsim pripade se kazdy prvek od predchoziho lisi o 1-e/n, tedy budou prvky tvorit geometrickou posloupnost (1-e/n)^i a t=(1-e/n)^|L_i| a tedy |L_i|=log_{1-e/n}t).
 +
 
 +
'''Obchodní cestující''':
 +
*Pro TSP na úplném grafu s troj. nerovností (&Delta;TSP) ex. aprox. algoritmus s poměrovou chybou &rho;=2.
 +
**Pro &Delta;TSP platí: <math>\forall u,v,w\in V: c(u,v)\leq c(u,w)+c(w,v)</math>. Je to vůbec NP-těžké? ANO: Lze řešit HK pomocí &Delta;TSP následujícím způsobem: Graf se doplní na K<sub>|V|</sub> a váhy se definují <math>c(e)=1\mbox{ pokud }e\in E</math>, <math>c(e)=2\mbox{ pokud }e\notin E</math>. Potom řešení hledá &Delta;TSP pro k=|V|.
 +
**Řešení problému &Delta;TSP:
 +
#Nalezení min. kostry (např. Primův alg. - staví se na jedna komponenta postupným připojováním vrcholů) &rarr; kostra T
 +
#Zvolí se vrchol ''u'' a ''preorder'' (pořadí prvního navštívení vrcholu) se očíslují vrcholy pomocí DFS(T,u) &rarr; pořadí vrcholů dané očíslováním.
 +
#Výsledná HK je určena očíslováním z kroku 2.
 +
:'''DK'''<nowiki>:</nowiki> Ať H* je opt. HK a T je minimální kostra, potom c(T)&le;c(H*).
 +
:W je úplná procházka po T (viz krok 2.), potom c(W)=2*c(T)&le;c(H*).
 +
:Z W se vyrobí H nahrazováním cest délek &ge;2 jednou hranou (vracení se v DFS průchodu a první dopředný krok). Jelikož zde platí trojúhelníková nerovnost, platí také: c(H)&le;c(W).
 +
:Platí c(H)&le;c(W)=2*c(T)&le;c(H*) potom &rho;&le;2.
 +
*Ať &rho;&ge;1 je konstanta. Pokud P&ne;NP, potom neexistuje polynomiální aproximační algoritmus řešící obecný TSP s poměrovou chybou &rho;.
 +
** Pokud by existoval, umí řešit HK (ten je NPÚ). Graf se doplní na K<sub>|V|</sub> a váhy hran se definují:
 +
:<math>
 +
c(e) =
 +
\begin{cases}
 +
  1,  & \mbox{pokud }e\in E \\
 +
  \rho\cdot n+1, & \mbox{pokud }e\notin E
 +
\end{cases}
 +
</math>
 +
:Nyní algoritmus buď vydá HK délky ''n'' (&rarr;Odpověď na HK v původním grafu je ANO), nebo vydá HK délky >&rho;&middot;''n'' (&rarr;Odpověď na HK v původním grafu je NE).
 +
 
 +
== Metody tvorby algoritmů ==
 +
 
 +
=== Dynamické programování ===
 +
Viz [[wen:Dynamic programming]], [http://kam.mff.cuni.cz/~kuba/vyuka/textiky/matrix_mul.ps Násobení matic] od Jakuba Černého nebo dynamické programování podle [http://ksp.mff.cuni.cz/tasks/19/cook5.html kuchařky KSP].
 +
 
 +
Věta o dynamickém programování: papír ''Dynamické programování'' od Jiřího Vyskočila na [http://ladislav.strojil.cz/school.php?sub=3 strojilovych stránkách].
 +
 
 +
Využití:
 +
# <nowiki>"překrývání podproblému"</nowiki> (problém lze rozdělit na podproblémy, jejichž řešení se využívá opakovaně).
 +
# <nowiki>"optimální podstruktury"</nowiki> (optimální řešení lze zkonstruovat z optimálních řešení podproblémů).
 +
 
 +
Příklady použití:
 +
* Násobení matic
 +
* Problém batohu
 +
* [[wcs:Problém_obchodního_cestujícího|Problém obchodního cestujícího]]
 +
* Floyd-Warshallův algoritmus nejkratší cesty
 +
* &hellip;
 +
 
 +
=== Hladový algoritmus ===
 +
[[wen:Greedy algorithm]]
 +
 
 +
Matroid je usp. dvojice M=(S,I) splňující podmínky:
 +
# ''S'' je konečná neprázdná množ. prvků.
 +
# ''I'' je neprázdná množina podmnožin množiny ''S'' (''nezávislých podmnožin'' - význam podle kontextu konkrétního matroidu) taková, že má ''dědičnou vlastnost'' (''B'' in ''I'' &amp; ''A'' subset ''B'' potom ''A'' in ''I'').
 +
# ''I'' má ''výměnnou vlastnost'' (pokud ''A'',''B'' in ''I'' tž. |''A''|&lt;|''B''| potom existuje ''x'' in ''B''-''A'': ''A''+{''x''} in ''I'').
 +
 
 +
(Pozn. Pro ''vážený matroid'' se doplňuje funkce ''w: S->R<sub>0</sub><sup>+</sup>'' pro podmnožiny ''S'' suma přes prvky.)
 +
 
 +
Všechny max. ''nezávislých množiny'' mají stejnou velikost.
 +
 
 +
Greedy(''M'',''w''):
 +
0. ''A''={}
 +
1. Setřiď ''S'' sestupně
 +
2. '''foreach''' ''x'' '''in''' ''S'' '''do''' //seřazené podle vah
 +
      '''if''' ''A''+{''x''} '''in''' ''I'' '''then''' //test na nezávislost!
 +
        ''A''=''A''+{''x''} //rozšíření
 +
3. '''return''' ''A''
 +
 
 +
Složitost:
 +
 
 +
# &Theta;(n*log(n))
 +
# n*test na nezávislost (zde jsme ignorovali složitost rozšiřování ''A'', asi snazší než test na nezávislost)
 +
#* Lemma 1: ''x'' in ''S'' tž. {''x''} not in ''I'', potom neex. ''A'' in ''I'' tž. ''x'' in ''A''.
 +
#* Lemma 2: ''S'' setříděný dle vah do nerost. posl. a ''x'' je první v ''S'' tž {''x''} in ''I''. Potom existuje optimální ''A'' sub ''S'' tž. ''x'' in ''A''.
 +
#* Lemma 3: ''x'' z lemma 2. pak pro matroid M je nalezení optima ekvivalentní hledání optima pro M' tž. <math> S'=\{y \in S; \{x,y\} \in I\}</math> a <math>I'=\{B \subseteq S-\{x\}; B+\{x\} \in I\}</math> (''kontrakce'' prvkem ''x'').
 +
 
 +
Pozn.: Lemma 1&ndash;3 -> Greedy(M,w) vrací optimální množinu.
 +
 
 +
Pr.: Minimalní kostra grafu
 +
 
 +
== Základy pravděpodobnostních algoritmů ==
 +
:''Viz kapitola 7 knihy Computational Complexity:A Modern Approach - Arora S., Barak B.''
 +
:''[http://ktiml.mff.cuni.cz/teaching/files/materials/KoubekVaclav_Prime.pdf Testovani prvociselnosti, Koubek]''
 +
:''Základ (lidštěji) shrnut na 5 stranách:''
 +
:''[http://www.ti.inf.ethz.ch/ew/Lehre/TI04/crashcourse.pdf Crash course on complexity theory with emphasis to Randomized computation, Mark Bläser]''
 +
=== Zmatení pojmů ===
 +
: Pri studiu clovek narazi na dve deleni v souvislosti s použitím náhodnosti ve výpočtech:
 +
* Deleni dle typu algoritmu: [en.wikipedia.org/wiki/Las_Vegas_algorithm, Las Vegas] , [en.wikipedia.org/wiki/Monte_Carlo_algorithm, Monte Carlo], Atlantic City [pouziva prof. Koubek na zaklade S.Ulama/N.Metropolise - tvurcu pojmenovani MonteCarlo]
 +
* Deleni dle slozitostnich trid - BPP, BTIME, ZPP, coRP, RP,PP, ... [pouziva prof.Sgall, Arora Barak a "složitostníci"]
 +
Dělení dle algoritmů se dá namapovat na složitostní třídy (a je dobře popsáno na anglické Wikipedii).
 +
=== Pravdepodobnostní Turingův stroj (PTS) - definice ===
 +
Rozsirime Turinguv stroj o moznost pouzivat ve vypoctech náhodnost.
 +
Pravdepodobnostní Turingův stroj (PTM) je Turingův stroj se dvěma přechodovýma funkcema <math>\delta_0, \delta_1</math>.
 +
 
 +
Výpočet PTS M na vstupu x probíhá tak, že v každém kroku se s pravděpodobností <math>\tfrac{1}{2}</math> použije <math>\delta_0</math> a s pravděpodobností <math>\tfrac{1}{2}</math> použije <math>\delta_1</math>. Toto rozhodnutí je nezávislé na předchozích rozhodnutích.
 +
 
 +
Výstupem stroje je buď 1(přijetí) nebo 0(odmítnutí). M(x) označíme náhodnou proměnnou, jejíž hodnota je hodnota výstupu stroje M nad vstupem x.
 +
 
 +
Stroj M běží v čase T(n), kde <math>T: N \rarr N </math>, pokud se zastaví maximálně po <math>T( \left | x \right | )</math> krocích nezávisle na náhodných rozhodnutích.
 +
 
 +
:Strom možných výpočtů PTS po <math>t</math> krocích je tedy úplný binární strom, existuje tedy <math>2^t</math> různých větví výpočtu. Každá větev má pravdepodobnost <math>\frac{1}{2^t}</math>. Tedy pravděpodobnost, že stroj M přijme vstup x, tj. <math>P[M(x) = 1] </math> je počet přijímajících větví z celkového počtu větví.
 +
----
 +
Pozor! Zde vznikaji jemné rozdíly mezi nedeterministickym Turingovym strojem (NDTM) a PTM.
 +
U NTDM řekneme, že přijímá slovo, pokud existuje ve stromu možných výpočtů větev, která končí v přijímacím stavu.
 +
U PTM uvažujeme celou množinu výpočetních větví, ve kterých končí výpočet v přijímacím stavu.
 +
Další rozdíl je na urovni konceptu kde jsou PTM blizke TM, protoze narozdil od NDTM maji modelovat skutecne vypocetni stroje.
 +
 
 +
=== RP, co-RP ===
 +
 
 +
Jazyk L patří do třídy RP, když pro něj existuje PTS M pracující v polynom. čase. Slovo z L storj přijme s pstí aspoň 0.5, slovo mimo jazyk vždy odmítne: <math>x\in L \implies p(acc) \geq 0.5; x \notin L \implies p(acc) = 0</math>. Tedy, pokud stroj slovo přijal, je určitě z jazyka. Pokud slovo odmítl, nic nevíme.
 +
 
 +
P je podmnožina RP - daný TS převedeme na PTS tak, že obě přechodové funkce zvolíme totožné. PTS přijme slovo z jazyka pravděpodobností 1, 1 >= 0.5.
 +
RP je podmnožina NP - PTS převedeme na NTS tak, že z každého displeje zvolíme dvě možná pokračování podle dvou přech. fcí. NTS vždy přijme slovo z jazyka, jelikož v PTS existovala přijímající větev.
 +
 
 +
Když zauvažujeme nad podobou co-RP, odvodíme, že pro L z co-RP existuje PTS M, který vždy přijme slovo z L, slovo mimo L odmítne s pstí >= 0.5. <math>ZPP = RP \cap co-RP</math>. Pro jazyk ze ZPP tedy existují dva stroje A (RP) a B (co-RP). Nový stroj může pustit slovo do A: když přijme, vracím ANO. Pak pustí slovo do B: když odmítne, vracím NE. Jinak můžu vrátit třetí hodnotu NEVÍM (třetí hodnota (vědomí si své chyby) nebyla možná u RP ani u co-RP, jen u ZPP). Algoritmy ze ZPP se označují '''Las Vegas''' (vrací ANO, NE, NEVÍM v poly-čase, vždy jim lze věřit).
 +
 
 +
=== BPP ===
 +
Jazyk L patří do třídy BPP, když pro něj existuje PTS M pracující v polynom. čase. Slovo z L stroj přijme s pstí aspoň 2/3, slovo mimo L stroj odmítne s pstí aspoň 2/3: <math>x\in L \implies p(acc) \geq 2/3; x \notin L \implies p(acc) < 1/3</math>. Jinými slovy, pravděpodobnost chybné odpovědi je menší než 1/3.
 +
 
 +
RP je podmnožina BPP. Stroj M pro jazyk z RP vždy odmítne slovo mimo jazyk, 0 < 1/3. Stroj M přijme slovo z L s pstí 1/2, pro třídu BPP ale potřebujeme 2/3 ... Spustíme M dvakrát! Pokud aspoň jednou vrátí ANO, vracíme ANO, jinak NE. Pro slovo z jazyka, pst(NE) < 1/2, pst(NE, NE) < 1/4, po dvou spuštěních je pravděpodobnost přijetí aspoň 3/4, 3/4 > 2/3 (a čas zůstal polynomiální). Tento trik (opakování) je velmi častý v této oblasti, říká se mu "amplifikace pravděpodobnosti".
 +
 
 +
Je zvykem se domnívat, že P není rovno NP. Podobně je zvykem se domnívat, že P = BPP.
 +
 
 +
<math>P \subseteq ZPP \subseteq (RP, co-RP) \subseteq BPP \subseteq PSPACE</math>
 +
 
 +
Algoritmy z BPP se označují '''Monte Carlo''' (vrací ANO, NE v poly-čase, ale nelze jim vždy věřit). Odpověď ANO může být chybná i NE může být chybná (oboustranná chyba). Někdy odpověď ANO je vždy správná a NE může být chybná (jednostranná chyba) - pak algoritmus vyhovuje dokonce třídě RP. Chybu lze zmenšovat opakováním.
 +
 
 +
=== BPP a BPTIME ===
 +
* BPP znamená 'bounded-error probabilistic polynomial-time'
 +
* BPP prijima i odmita s psti 2/3.
 +
** Coz muze vest k otazce: ''2/3 + 2/3 je vice nez jedna (coz se nam u pravdepodobnosti nelibi)''. Zde je nutne uvedomit si, co veta rika. Pokud slovo do jazyka patri, pak s psti 2/3 je prijato (a s psti 1/3 odmitnuto). Pokud slovo do jazyka nepatri je s psti 2/3 odmitnuto (a psti 1/3 prijato).
 +
 
 +
[[File:complexity_BPP_class_definition.jpg]]
 +
{{TODO | definice }}
 +
<math></math>
 +
 
 +
Pracovni text:
 +
BPP prijima i odmita s psti 2/3.
 +
 
 +
Alternativni definice: podobne jako u NTS - spolu se vstupem dame DTS polynomialni certifikat(sekvence rozhodnuti pro kazdy krok)
 +
 
 +
Vi se, ze BPP je nekde mezi P a EXP.
 +
 
 +
Ale nevi se ani jestli BPP je ostre v NEXP.
 +
 
 +
Hlavni otevreny problem je jestli BPP = P. (Hodne teoretiku veri, ze ano!)
 +
 
 +
Priklady: pocitani medianu, testovani prvociselnosti,
 +
 
 +
=== RP, coRP, ZPP ===
 +
 
 +
 
 +
{{TODO | chtelo by to sem prepsat nejaky vycuc}}
 +
 
 +
== Materiály ==
 +
* [[TIN063_Skripta_Ladislava_Strojila|Skripta Ladislava Strojila]]
 +
* Slajdy z přednášek a další materiály na [http://mff.modry.cz/slozitost/ mff.modry.cz]
 +
* [http://www.cs.berkeley.edu/~vazirani/algorithms.html Algorithms] &ndash; Dasgupta S., Papadimitriou C.H., Vazirani U.V., Berkeley
 +
* [http://www.cs.princeton.edu/theory/complexity/ Complexity Theory: A Modern Approach (draft)] &ndash; Arora S., Barak B., Princeton
 +
 
 +
[[Category: Státnice Informatika Mgr.]]

Aktuální verze z 25. 8. 2016, 17:07

Tento souhrn slouží pro přípravu k magisterským státnicím pro obory Teoretická informatika a Diskrétní modely a algoritmy. Detailní informace o předmětu hledej na stránkách Složitost I a Složitost II.

Rozsah látky[editovat | editovat zdroj]

Seznam oficiálních státnicových otázek pro studijní obory Teoretická informatika a Diskrétní modely a algoritmy (aktualizováno 2013):

Věty o hierarchii tříd složitosti, konstruovatelné funkce, vztahy mezi časovými a prostorovými mírami a determinismem a nedeterminismem, Savitchova věta. Úplné problémy pro různé třídy (NP, PSPACE, P, #P). Polynomiální hierarchie, pseudopolynomiální algoritmy, silná NP-úplnost, třída #P a #P-úplnost. Aproximační algoritmy a schémata. Metody tvorby algoritmů: dynamické programování, hladový algoritmus na matroidu. Základy pravděpodobnostních algoritmů.

Studijní obory Softwarové systémy a Matematická lingvistika mají okruhy Složitost a Vyčíslitelnost do spojeny do jednoho a rozsah otázek pro složitost se liší.

Zdroje obecně[editovat | editovat zdroj]

Většina je pokryta přednáškami Složitost I a II, některá témata je však třeba dohledat jinde (klidně po internetu, na wikipedii, v Majerechovi, v zahraničních skriptech...). Pozor, Čepkovy slajdy jsou více než stručné.

Vřele doporučuji strávit jedno odpoledne v knihovně s knížkou od Arory a Baraka Computational Complexity: A Modern Approach. Velmi názorně pomůže získat dobrou intuici u téměř všech okruhů a rigorózní důkazy se tam člověk venkoncem také dočte.

Poznámky od Peter Černo

Věty o zrychlení a o mezerách[editovat | editovat zdroj]

Věta o lineárním zrychlení[editovat | editovat zdroj]

see Složitost II#Věta o lineárním zrychlení (asi i wen:Linear speedup theorem)
  • DTS s alespoň dvěma páskami se na vstupu délky n dá zrychlit z t kroků na $ n + \lceil n/r \rceil + 6 \lceil t/r \rceil $ ($ r \in \mathbb{N} $)
    • postup: nový stroj stlačí r políček původní pásky na jedno -- nejdřív okopíruje a přejede na začátek ($ n + \lceil n/r \rceil $ kroků), pak simuluje v šesti krocích r kroků původního stroje: nejdřív načte tři svoje políčka (3r políček původního stroje; trvá 4 kroky nového [vlevo,vpravo,vpravo,vlevo]), pak zjistí, jak budou vypadat po r krocích (jen ve vnitřním stavu), a nakonec to zapíše (další max 2 kroky, za r kroků starého se stihnou změnit nejvýše dvě políčka nového stroje)
  • Je-li L jazyk přijímaný k-páskovým DTS M (k>=2) a s časovou složitostí $ t(n) \in \omega(n) $. Potom pro každé kladné c existuje k-páskový M' s časovou složitostí c*t(n) přijímající L.
    • Vezmeme r > 12/c, uděláme M' jako výše, doba jeho běhu nad vstupem délky n se dá pro r>2 shora odhadnout výrazem (c/2)*t(n)+(6/r)*t(n) (z $ t(n) \in \omega(n) $), což z r>12/c dává omezení doby běhu c*t(n) pro skoro všechna n. Konečný počet výjimek se ošetří konečným automatem.
  • Nechť je L jazyk přijímaný k-páskovým DTS M s časovou složitostí t(n) = c*n. Dále ať k>=2 a c>1. Pak $ \forall \epsilon > 0 $ existuje k-páskový DTS M' s časovou složitostí $ (1+\epsilon)\cdot n $ přijímající L.

If time is money you've made me a wealtiehr woman.

Věty o hierarchii tříd složitosti[editovat | editovat zdroj]

see Složitost II#Základní třídy složitosti, wen:Complexity class, [[1]]

Otevřenost časové hierarchie shora[editovat | editovat zdroj]

Nechť T je rekurzivní funkce (tj. existuje TS, který ji vyčísluje). Potom existuje rekurzivní jazyk L takový, že $ L \notin DTIME(T(n)) $.

Důkaz přes jazyk $ L = \{ x_i : M_i \mbox{ nepřijímá } x_i \mbox{ v čase } T(|x_i|) \} \ $, (máme očíslované řetězce i Turingovy stroje). Přítomnost v L se dá otestovat pomocí TS co si odsimuluje T(|x|) kroků příslušného stroje, L je tedy rekurzivní.

Pokud by platilo $ L \in DTIME(T(n)) $, tak by existoval TS M, který rozpozná L v čase T(n). Ten stroj má nějaké číslo i. (Tj. $ M=M_i $.). Pak platí jedno z:

  1. $ x_i \in L $, tj. stroj M přijme $ x_i $ v čase $ T(|x_i|) $ (protože ho poznává). Zároveň ale z stroj $ M_i $ $ x_i $ v čase $ T(|x_i|) $ nepřijímá (z definice L). Máme spor, protože M a $ M_i $ je ten samý.
  2. $ x_i \notin L $, takže ho M (rozpoznávač L) v daném čase nepřijme, ale $ M_i $ (ten z definice L) ho v daném čase přijmout musí, tj. taky spor.
(tj. vyzkoušíme, co řekne $ M_i $ na jemu příslušející řetězec $ x_i $)

Proto $ L \notin DTIME(T(n)) $.

Otevřenost prostorové hierarchie shora[editovat | editovat zdroj]

Nechť S je rekurzivní funkce. Potom existuje rekurzivní jazyk L takový, že $ L \notin DSPACE(S(n)) $.

Důkaz je analogický jako u časové hierarchie, vyrobí se jazyk $ L = \{ x_i : M_i \mbox{ nepřijímá } x_i \mbox { v prostoru } S(|x_i|) \} $. Rozdíl je jen v simulaci $ M_i $, který se navíc může na svém omezeném prostoru zacyklit, což se ale dá detekovat, neb tam má omezený počet konfigurací.

Věty o časové a prostorové hierarchii[editovat | editovat zdroj]

O prostorové hierarchii[editovat | editovat zdroj]

Nechť $ S_1: \mathbb N \to \mathbb N $ a $ S_2: \mathbb N \to \mathbb N $ jsou funkce takové, že $ S_2 \in \omega(S_1) $, $ S_2 $ je prostorově konstruovatelná a $ S_1(n) \ge log_2(n) $. Potom existuje jazyk L takový, že $ L \in DSPACE(S_2) \setminus DSPACE(S_1) $.

To s omegou znamená že $ S_2 $ není omezená $ S_1 $ (ani když se přenásobí libovolnou konstantou), celá pointa věty je, že v takto větším prostoru se dají poznat nějaké další jazyky.

Důkaz[editovat | editovat zdroj]

We show the existence of a language L such that $ L \in DSPACE(S_2) $ but $ L \notin DSPACE(S_1) $. We define L by describing a Turing machine ML, using space $ O(S_2(n)) $, that decides it. ML does the following on input w = (M, y) of length $ |w| = n $:

  1. Run M(w) with at most $ S_2(n) $ space and for at most $ 2^{2S_2(n)} $ steps (these bounds are imposed on M), using space at most $ 3·S_2(n) $.
  2. If M(w) accepts within the given time and space bounds, then reject. Otherwise, accept.

In step 1, we can use the fact that $ S_2 $ is space constructible to mark off exactly $ S_2(n) $ tape cells for M to use. We can similarly mark off an additional $ 2S_2(n) $ cells to use as a counter for checking the number of steps M makes, and one last set of $ S_2(n) $ cells to use for any remaining computation. By construction, ML uses space $ \hat S_2(n) = 4 · S_2(n) $.

We need to show that no machine using space $ O(S_1(n)) $ can decide L. Assume the contrary. Then there exists a machine $ M^{\prime}_L $ deciding L and using space $ \hat S_1(n) = O(S_1(n)) $.

Choose k large enough so that $ \hat S_1(k) < S_2(k) $, so that $ M^{\prime}_L $ makes fewer than $ 2S_2(k) $ steps on inputs of length k, and so that the simulation of $ M^{\prime}_L $ on inputs of length k can be performed in $ S_2(k) $ space. Consider the input $ w = (M^{\prime}_L, 1^k) $. If we run $ M_L(w) $ then (1) $ M_L $ has enough time and space to simulate the entire execution of $ M^{\prime}_L(w) $, and thus (2) $ M_L(w) $ outputs the opposite of whatever $ M^{\prime}_L(w) $ outputs. We conclude that $ M_L $ and $ M^{\prime}_L $ do not decide the same language.

O časové hierarchii[editovat | editovat zdroj]

Nechť $ T_1: \mathbb N \to \mathbb N $ a $ T_2: \mathbb N \to \mathbb N $ jsou funkce takové, že $ T_2 \in \omega(T_1 \cdot \log T_1) $ a $ T_2 $ je časově konstruovatelná. Potom existuje jazyk L takový, že $ L \in DTIME(T_2) \setminus DTIME(T_1) $.

Konstruovatelné funkce[editovat | editovat zdroj]

see also Složitost II
  • 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[1]).
  • Funkce $ f:\mathbb{N} \rightarrow \mathbb{N} $ je prostorově konstruovatelná pokud existuje DTS M takový, že pro každý vstup délky n zastaví s právě f(n) páskovými symboly neprázdnými, přičemž žádný jiný prostor na pracovních páskách nebyl v průběhu výpočtu použit.

Lemma: Nechť $ f_1+f_2 $ a $ f_2 $ jsou časově konstruovatelné funkce, dále nechť $ \exists \varepsilon>0, \exists n_0 $ takové, že $ \forall n>n_0 : f_1(n) \geq \varepsilon \cdot f_2(n) + (1+\varepsilon)n $. Pak $ f_1 $ je časově konstruovatelná.

Podobně jako v důkazu věty o lineárním zrychlení zrychlíme výpočet trvající $ f_1(n)+f_2(n) $ kroků, aby trval přesně $ f_1(n) $ kroků...

Věta: Nechť $ f:\mathbb N \to \mathbb N $, taková, že existuje $ \varepsilon > 0 $ a $ n_0 $, že $ \forall n \geq n_0: f(n) \geq (1+\varepsilon)n $. Pak je f časově konstruovatelná právě tehdy, když je vyčíslitelná v čase O(f).

Je-li f časově konstruovatelná, pak máme stroj který běží v čase f(n). Můžeme mu přidat pásku, na kterou bude psát po dobu svého běhu jedničky, čímž f vyčíslí.
Naopak, označíme-li g(n) přesný čas stroje M, který funkci f počítá v čase O(f(n)). (Tedy g(n) < c*f(n) pro skoro všechna n a nějaké c.) Potom g je časem TS M, f + g je časem TS, který "po dopočítání M ještě spočítá počet jedniček na pásce". Funkce g je časově konstruovatelná díky stroji M. Z toho (a z lemmatu výše) plyne časová konstruovatelnost f.

Věta: Funkce f je prostorově konstruovatelná právě tehdy, když je vyčíslitelná v prostoru O(f).

Doprava nám stačí upravit stroj který f prostorově konstruuje tak, aby při zabrání nového políčka zapsal na novou pásku jedničku.
Nechť M je k-páskový deterministický Turingův stroj vyčíslující f(n) v prostoru c*f(n). Podle věty o lineární kompresi zkonstruujeme k-páskový stroj M', který vyčísluje f(n) v prostoru přesně f(n). Uvědomte si, že M' vyčísluje f(n), tedy musí pracovat v prostoru alespoň f(n). Stroj M' dále převedeme podle věty o redukci počtu pásek na jednopáskový stroj M, který již dokazuje prostorovou konstruovatelnost funkce f.
Věta o lineární prostorové kompresi
Je-li L jazyk přijímaný k-páskovým DTS M v prostoru S(n), pak pro každé přirozené číslo r existuje k-páskový DTS M', který přijímá L v prostoru $ \lceil S(n)/r \rceil $
Věta o redukci počtu pásek pro prostorovou složitost
Je-li L jazyk příjímaný k-páskovým DTS M v prostoru S(n), pak existuje jednopáskový DTS M', který přijímá L v prostoru S(n).

Důsledek: Každá časově konstruovatelná funkce je také prostorově konstruovatelná.

Funkce f je časově konstruovatelná, tedy je vyčíslitelná v čase O(f), tím spíše je vyčíslitelná v prostoru O(f) a z věty výše je tedy i prostorově konstruovatelná.

Vztahy mezi časovými a prostorovými mírami a determinismem a nedeterminismem[editovat | editovat zdroj]

DSPACE(S(n)), DTIME(T(n)), NSPACE(S(n)), NTIME(S(n)) -- třídy jazyků (ne)deterministické časové/prostorové složitosti T(n)/S(n).

Triviální vztahy

  • $ \forall F_1(n) \leq F_2(n) \Rightarrow XXX(F_1(n)) \subseteq XXX(F2(n)) $, kde XXX je něco z [DN](SPACE|TIME)

Věta o vztazích mezi třídami složitosti[editovat | editovat zdroj]

  1. $ DTIME (f(n)) \subseteq NTIME(f(n)) $
    $ DSPACE (f(n)) \subseteq NSPACE(f(n)) $
    • triviálně platí
  2. $ DTIME(f(n)) \subseteq DSPACE(f(n)) $
    • z vět o lineární kompresi a redukci počtu pásek
    • (IMHO si stačí uvědomit, že prostor je vždy omezen spotřebovaným časem)
  3. $ NTIME(f(n)) \subseteq DSPACE(f(n)) $
    • postupně generujeme f(n)-tice možných průchodů (v každém kroku max r možností, r=max|{přechodová funkce}|) jako graf průchodu výpočtem a výpočet simulujeme DTS podle toho -- simulace potřebuje DSPACE(f(n)) (třeba podle předchozího bodu), uloženi f(n)-tice potřebuje $ log_2(r) * f(n) $ místa, tj. taky DSPACE(f(n)), a tenhle prostor se dá použivat pro jednotlivé simulace stejný. Celkem tedy $ DSPACE(f(n)) $.
  4. $ L \in DSPACE(f(n)) $ a $ f(n) \geq log_2(n) $, pak $ L \in DTIME(C_L^{f(n)}) $, kde CL je konstanta závislá na jazyku L
    • Nechť M je jednopáskový stroj poznávající L v prostoru f(n). Počet jeho konfigurací je omezen $ s \cdot (n+1) \cdot (f(n)+1) \cdot t^{f(n)} \leq d^{f(n)} $, pro vhodné $ d $ ($ s $ je počet stavů, $ t $ je počet páskových symbolů, člen (n+1) asi? pro pozici hlavy na vstupní pásce).
    • Zkonstruujeme M', který simuluje M a nejvýše po $ d^{f(n)} $ krocích se zastaví. (Potřebujeme předpoklad časové konstruovatelnosti funkce f.)
  5. $ L \in NSPACE(f(n)) $ a $ f(n) \geq log_2(n) $, pak $ L \in DTIME(C_L^{f(n)}) $, kde CL je konstanta závislá na jazyku L
    • Počet konfigurací opět omezen nějakým $ d^{f(n)} $. Vygenerujeme graf, vrcholy=stavy (tj. omezené), hrana=přechod jedním krokem (konstanta*|stavy|, protože přechodová funkce je konečná). Pak se graf projde a zjistí, jestli tam je přijímací výpočet.
  6. $ L \in NTIME(f(n)) $, pak $ L \in DTIME(C_L^{f(n)}) $, kde CL je konstanta závislá na jazyku L
    • Nechť M je k-páskový NTS, který poznává L v čase f(n). Počet jeho konfigurací je omezen $ s \cdot (f(n)+1)^k \cdot t^{k \cdot f(n)} \leq d^{f(n)} $ pro vhodné $ d $ ($ s $ je počet stavů, $ t $ páskových symbolů).
    • Zkontruujeme DTS M', který vygeneruje seznam všech konfigurací dosažitelných z počáteční konfigurace, což lze provést v kradratickém čase vzhledem k délce výsledného seznamu. Tato délka je omezena součinem počtu konfigurací a délky zápisu jedné konfigurace. Tedy $ l \leq d^{f(n)} \cdot (k \cdot f(n) + 1 + k \cdot \log f(n)) \leq c^{f(n)} $. M' je pak schopný poznat jestli je dosažitelná nějaká přijímající konfigurace, počet jeho kroků je omezen $ c^{2 f(n)} $.

Savitchova věta[editovat | editovat zdroj]

see wen:Savitch's theorem

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

Pokud NTS M přijímá jazyk L v prostoru S(n), pak existuje konstanta $ C_L $ taková, že M má nejvýše $ C_L^{S(n)} $ konfigurací. Počet kroků přijímajícího výpočtu pak bude nanejvýš $ C_L^{S(n)} = 2^{S(n) \log C_L} $.
Pak definujeme proceduru $ TEST(I_1, I_2, i) $, která zkoumá, jestli se ze stavu $ I_1 $ dá přejít do stavu $ I_2 $ za maximálně $ 2^i $ kroků. (Dělá to rekurzivně -- pro i=0 ověří jestli jsou stavy shodné nebo existují přímý přechod a vrátí výsledek, jinak pro každý stav $ I_x $ pouští $ TEST(I_1, I_x, i-1) $ a $ TEST(I_x, I_2, i-1) $ a zkoumá jejich výsledek.)
Jedna kopie procedury TEST si musí pamatovat tři konfigurace (jedna konfigurace potřebuje stav, pozici vstupní a výstupní hlavy, a obsah pracovní pásky, to vše O(S(n)) a parametr i (ten se taky vejde do O(S(n)), viz max počet kroků výpočtu).
Simulace probíhá tak, že pro všechny přijímací stavy $ I_j $ voláme proceduru $ TEST(I_0, I_j, mS(n)) $ ($ I_0 $ je počáteční konfigurace) a pokud aspoň jednou odpoví true, vstup přijmeme.
Pracovní páska pak funguje jako zásobník parametrů procedury TEST, která se zahloubí nanejvýš O(S(n)), takže se celý výpočet vejde do prostoru $ O(S^2(n)) $

Úplné problémy pro třídy NP, PSPACE[editovat | editovat zdroj]

see wen:NP-complete, wen:PSPACE-complete

Def: Problém A je T-těžký, kde T je třída, vzhledem k k-převoditelnosti, pokud $ \forall B\in T: B\leq_k A $.

Def: Problém A je T-úplný, kde T je třída, vzhledem k k-převoditelnosti, pokud je T-těžký a navíc $ A\in T $.

Převoditelnosti pro různé třídy:

  • NP - poly time převoditelnost
  • P - log space převoditelnost
  • PSPACE - poly time převoditelnost

Úplné problémy pro různé třídy:

  • NP: Kachličky, SAT; 3-SAT, 3-Color, Klika, NM, VP; VP, HK, TSP; VP, SP
  • P: SAT na Hornovských klauzulích, Vyhodnocení obvodu booleovských hradel (CVP)
  • PSPACE: SAT na kvantifikovaných klauzulích (QBF-SAT) - splnitelnost SAT kde proměnné můžou být kvantifikované i univerzálním kvantifikátorem (důkaz podobný důkazu Savichovy věty)
  • dále typicky hry (zoběcněný wen: Hex (board game))

Důkazy různých NP-C[editovat | editovat zdroj]

Pochopitelnější důkazy jsou uvedené v Majerechových skriptách (ke stažení ve studnici).

Lidsky vysvětlený důkaz Cook-Levinovy věty ("Existuje NP-úplný problém") je zde. Původně je věta formulována pro problém SAT, ale snazší důkaz je pro KACHL a potom ukázat, že KACHL < SAT.

Důkaz KACHL < SAT je také v Majerechových skriptách.

  • SAT < 3-SAT
Za každou klauzuli s jiným počtem literálů než 3 dáme množinu klauzulí, která dává ekvivalentní podformuli. Vezměme klauzuli ci:
  1. $ c_i = (x) $, pak $ c_i' := (x \vee y_1 \vee y_2) \wedge (x \vee y_1 \vee \bar y_2) \wedge (x \vee \bar y_1 \vee y_2) \wedge (x \vee \bar y_1 \vee \bar y_2) $
  2. $ c_i = (x_1 \vee x_2) $, pak $ c_i' := (x_1 \vee x_2 \vee y) \wedge (x_1 \vee x_2 \vee \bar y) $
  3. $ c_i = (x_1 \vee \dotsb \vee x_k) $ pro $ k>3 $, pak $ c_i' := (x_1 \vee x_2 \vee y_1) \wedge (\bar y_1 \vee x_3 \vee y_2) \wedge \dotsb \wedge (\bar y_{i-2} \vee x_i \vee y_{i-1}) \wedge \dotsb \wedge (\bar y_{k-3} \vee x_{k-1} \vee x_k) $


  • SAT < Klika
Graf nad všemi literály formule (opakované literály se budou opakovat i v grafu), hrana mezi každými dvěma literály z různých klauzulí, pokud s nejedná o vzájemnou negaci (x a -x). Hledáme kliku o velikosti jako je počet klauzulí, ta pak pro každou klauzuli určuje splňující literál.
  • Klika < NM
Nezávislé množiny odpovídají právě klikám v komplementárním grafu.
  • NM < VP
Doplňky vrcholových pokrytí odpovídají právě nezávislým množinám. Důkaz snadno sporem, hrana porušující nezávislost není v doplňku pokryta a naopak.

Početní úlohy, #P a #P-úplnost[editovat | editovat zdroj]

Def: Funkce f patří do třídy #P pokud existuje binární relace v NPF a platí $ f(x)=|\{y|(x,y)\in R\}| $. f je početní úloha asociovaná s problémem R, píšeme taky #R (např #SAT).

Věta: Každý problém $ A\in NP $ má relaci $ R_A\in NPF $, pro kterou platí, že $ x\in A\Leftrightarrow \#R_A(x)>0 $ - Relace (x,y) y jsou polynomiálně velké certifikáty pro $ x\in A $.

Tohle nám dává souvislost #P s NP. Intuitivně bude platit, že NP-úplné problémy budou #P-úplné. Na druhou stranu v #P musí intuitivně být těžké problémy, jejichž rozhodovací problém těžký není. Počítat řešení musí být jistě alespoň tak těžké, jako najít libovolné.

Další věty/vlastnosti:

  • $ f\in\#P $ lze spočítat polynomiálním počtem dotazů na relaci - certifikát je polynomiálně omezený vstupem, tak generuju certifikáty a ptám se relace
  • f(x) je v polynomiálním prostoru vzhledem k |x| - počet certifikátů je omezený $ 2^{p(|x|)} $ takže k binárnímu zápisu nám max stačí p(|x|) bitů

Def: Převoditelnost v #P: Trochu složitější než klasická, protože nepřevádíme jen vstup, ale i výsledek. $ f(x)\leq_{\#P}g(x) $ když existují $ \alpha(x,y), \beta(x) $ v P takové, že $ f(x)=\alpha(x,g(\beta(x))) $.

Pak #P-těžkost téhle převoditelnosti. P-úplnost můžeme definovat ale i pomocí polynomiální převoditelnosti relace A z definice # problému. A tohle je docela důležité pro důkazy převoditelnosti, protože nám to dává souvislost s převody uvnitř NP.

Věta: Pokud máme relaci A v NPF-těžkou (každá relace v NPF lze na A převést), tak problém #A je #P-úplný. Pozn. NPF-převoditelnost je polynomiální převoditelnost se zachováním řešení: $ A,B\in NPF $, existuje $ \beta $ v P tak, že $ |\{y|(x,y)\in A\}|=|\{y|(\beta(x),y)\in B\}| $

#P-úplný problém: #SAT je #P-úplný - jasné, když dostaneme nějaký problém v #P, tak relaci s ním asociovanou umíme převést na SAT (protože SAT je NP-úplný).

Zajímavější problém je: #DNF-SAT je #P-úplný - to nám ukazuje to, že $ NP\neq \#P $

Důkaz: DNF-SAT je v PF, takže #DNF-SAT určitě v #P. Když převedeme #SAT na #DNF-SAT tak budeme hotovi (protože #SAT je #P-úplný). Zjevně pro vstup na n proměnných platí: $ \#KNF-SAT(\phi)=2^n-\#DNF-SAT(\neg \phi) $ a negaci umíme spočítat polynomiálně pomocí de-morganových pravidel. Funkce $ \beta(\phi)=\neg\phi $ a funkce $ \alpha(\phi,c)=2^n-c $.

Polynomiální hierarchie[editovat | editovat zdroj]

see polynomiální hierarchie, wen:Polynomial hierarchy, Pekne a jednoduche vysvetleni - souvislost s TQBF a PSPACE, alternujici kvantifikatory.
Dobre je si vygooglit v obrazcich heslo polynomial time hierarchy.

Def: TS s orákulem A (jazyk) je TS co má navíc pásku, pomocí které může 'zavolat' orákulum pro $ w\in A $. Jazyk slov pro TS M s orákulem A je L(M,A).

Def: Turingovská převoditelnost (pomocí orákula): A je det. turingovsky převoditelný na B pokud existuje DTS M s orákulem B pro nějž A=L(M,B). Značíme $ A\leq_T B $. Obdobně nedet. turingovská převoditelnost $ A\leq_{NP} B $. Například, každý jazyk A v P je tur. převoditelný na prázdný jazyk (na to, jestli je $ w\in A $ nepotřebujeme nic než klasický TS z P).

Def: Teď můžeme definovat tzv. Relativizované třídy:

  • $ P(A)=\{B|B\leq_T A\} $ - všechny jazyky, které můžeme deterministicky rozpoznávat s pomocí orákula jazyka A, např $ P(\emptyset)=P $
  • $ P(C)=\{B|\exists A\in C: B\leq_T A\} $ - všechny jazyky, které můžeme deterministicky rozpoznávat s pomocí nějakého orákula z třídy C, např $ P(P)=P $
  • $ NP(A)=\{B|B\leq_{NP} A\} $ - všechny jazyky, které můžeme nedeterministicky rozpoznávat s pomocí orákula jazyka A, např $ NP(\emptyset)=NP $
  • $ NP(C)=\{B|\exists A\in C: B\leq_{NP} A\} $ - všechny jazyky, které můžeme nedeterministicky rozpoznávat s pomocí nějakého orákula z třídy C, např $ NP(P)=NP $
  • Pozn: zjevně tyhle třídy můžeme rekurzivně volat samy na sebe P(NP(P)), NP(NP(NP)) apod
  • Pozn: NP(NP)=? ... nevime! (nemuzem pouzit postup jako u P(P), vypocet simulace nema jednu vetev).

Pro každou množinu jazyků platí $ P(C) \subseteq NP(C) \subseteq PSPACE(C) $.

Def:Polynomiální hierarchie - Třídy $ \Sigma_k, \Pi_k, \Delta_k $ definované následovně:

  1. $ \Sigma_0 = \Pi_0 = \Delta_0 = P $
  2. $ \Sigma_{i+1} = NP(\Sigma_i) $
  3. $ \Delta_{i+1} = P(\Sigma_i) $
  4. $ \Pi_{i+1} = coNP(\Sigma_i) $ kde coNP je definované klasicky množinově na jazycích $ coNP(B)=\{A'|A\in NP(B)\} $
  5. $ PH=\bigcup_{i\geq 0}\Sigma_i $

Zde je dobré vědět nějaké vztahy mezi jednotlivými třídami. Viz obrázek na anglické wikipedii.

Věta: $ PH = \bigcup_{k\geq 0}\Pi_k = \bigcup_{k\geq 0}\Delta_k $.

PH je v PSPACE[editovat | editovat zdroj]

Věta
$ PH \subseteq PSPACE $

Dokazuje se indukcí podle i

  1. i = 0; $ \Sigma_0 = P \subseteq PSPACE $
  2. předpokládáme, že tvrzení platí pro i (IP), chceme ukázat, že $ \Sigma_{i+1} \subseteq PSPACE $
    $ \Sigma_{i+1} = NP(\Sigma_i) \subseteq^{IP} NP(PSPACE) \subseteq^* PSPACE(PSPACE) $
    * -- co poznám v NP, poznám v i PSPACE, a orákulum mám stejné
    $ PSPACE(PSPACE) \subseteq PSPACE $
    místo orákula může stroj kolikrát chce pouštět DTS, co si bude vedle psát ve svém polynomiálním prostoru

Věta: O kolapsu PH - Pokud P=NP, tak PH=P

Tato část je neúplná a potřebuje rozšířit. Další vzájemné vztahy, alternující kvatifikátory, kolaps PH

Pseudopolynomiální algoritmy[editovat | editovat zdroj]

see wen:Pseudo-polynomial time
  • Nechť je dán rozhodovací problém (úloha, jejímž výstupem je ANO/NE) π a jeho instance I. Def:
    • kód(I) .. délka zápisu I v nějakém kódování (např. binárním)
    • max(I) .. velikost největšího čísla v I (ne jeho kódu)
  • Alg. řešící π se nazývá pseudopolynomiální, pokud je jeho čas. slož. omezena polynomem v proměnných kód(I) a max(I).
  • Pokud je π tž. forall I: max(I)≤p(kód(I)) potom pseudopolynomiální=polynomiální
  • Problémy, pro které obě skupiny nesplývají se nazývají číselné. tj. neexistuje polynom p tž. viz výš
  • Ne však každý číselný problém lze řešit pseudopolynomiálně (tzv. silně NP-uplné problémy)
    • πp omezení na podproblém π tž. platí max(I)≤p(kód(I)). Pokud πp NPÚ, tak π S-NPÚ
    • Klika, TSP je S-NPÚ
Tato část je neúplná a potřebuje rozšířit. S-NPÚ patří do tohoto požadavku taky!

Dolní odhady pro uspořádání (rozhodovací stromy)[editovat | editovat zdroj]

podle http://ksvi.mff.cuni.cz/~topfer/ppt/Progr-11.pdf

popsano v otazkach k Datovym strukturam: Státnice_-_Informatika_-_Datové_struktury#Doln.C3.AD_odhady_pro_uspo.C5.99.C3.A1d.C3.A1n.C3.AD_.28rozhodovac.C3.AD_stromy.29

Aproximační algoritmy a schémata[editovat | editovat zdroj]

Pozri tiež Státnice - Aproximační algoritmy a schémata

see wen:Approximation algorithm, kus na straně 12 z [2]
  • Předpoklady: Každé řešení má nezápornou hodnotu.
  • Značení: $ n $ velikost zadání, C* hodnota optimálního řešení, C hodnota aproximovaného řešení

Definice[editovat | editovat zdroj]

  • Poměrová chyba: $ \rho(n) \geq max\left\{ \frac{C^*}{C}, \frac{C}{C^*} \right\} $
  • Relativní chyba: $ \epsilon(n) \geq \frac{|C-C^*|}{C^*} $
    • Pozn.: Pokud jsou $ \rho(n),\epsilon(n) $ konstanty, tak se obyčejně parametr $ n $ vynechává.
  • Aproximační schéma (AS) pro optimalizační úlohu je aproximační alg., který pro vstup délky $ n $ a číslo $ \epsilon>0 $ najde řešení s relativní chybou $ \epsilon $. Může být exponenciální vzhledem k $ n $ i $ 1/\epsilon $.
  • Polynomiální AS: AS, které je polynomiální vzhledem k $ n $.
  • Úplně Polynomiální AS (ÚPAS): PAS, které je polynomiální i k $ 1/\epsilon $.

Well done article that. I'll make sure to use it wisley.

Příklady[editovat | editovat zdroj]

Vrcholové pokrytí[editovat | editovat zdroj]

  • ρ=2.
  • Stačí v cyklu: Vždy vzít ze zbylých hran jednu. Oba její vrcholy přidat do pokrytí a odstranit ostatní incidentní hrany.
DK: Ať je F množina všech hran vybraných během algoritmu a C nalezené pokrytí. Platí: |C|=2*|F| (každá hrana má 2 vrcholy) a navíc |F|≤|C*| (optimální řešení musí pokrýt i hrany z F).
|C|=2*|F| a |F|≤|C*| potom |C|≤2*|C*|


ÚPAS pro součet podmnožiny[editovat | editovat zdroj]

  • Je dána konečná podmnožina množ. přirozených čísel A s prvky xi, hodnota součtu t a aproximační parametr 0<ε<1.
  • Součet L+x označuje seznam vzniklý ze seznamu L přičtením hodnoty x ke všem jeho položkám. Zachovává uspořádání.
  • Prořezat seznam L s parametrem δ znamená, že pro každý odstraněný prvek y existuje v prořezaném seznamu L' prvek z splňující: (1-δ)y ≤ z ≤ y. Zachovává uspořádání.
  • Algoritmus řešení:
APPROX_SP(A,t,ε):
L0=(0) for i = 1 to n do Li=MERGE(Li-1, Li-1+xi) //vytvoří nový a slitím původního a součtu původního Li=PRUNE(Li, ε/n) //prořeže Li=CROP(Li, t) //odstraní prvky větší než t end return Ln //vrátí řešení
  • Prořezávání s parametrem ε/n zajišťuje nepřekročení výsledné meze chyby ε, která se může kumulativně zvětšovat v každé iteraci.
  • Časová složitost algoritmu je $ O\left(\frac{n^2\cdot log~t}{\epsilon}\right) $ (v nejhorsim pripade se kazdy prvek od predchoziho lisi o 1-e/n, tedy budou prvky tvorit geometrickou posloupnost (1-e/n)^i a t=(1-e/n)^|L_i| a tedy |L_i|=log_{1-e/n}t).

Obchodní cestující:

  • Pro TSP na úplném grafu s troj. nerovností (ΔTSP) ex. aprox. algoritmus s poměrovou chybou ρ=2.
    • Pro ΔTSP platí: $ \forall u,v,w\in V: c(u,v)\leq c(u,w)+c(w,v) $. Je to vůbec NP-těžké? ANO: Lze řešit HK pomocí ΔTSP následujícím způsobem: Graf se doplní na K|V| a váhy se definují $ c(e)=1\mbox{ pokud }e\in E $, $ c(e)=2\mbox{ pokud }e\notin E $. Potom řešení hledá ΔTSP pro k=|V|.
    • Řešení problému ΔTSP:
  1. Nalezení min. kostry (např. Primův alg. - staví se na jedna komponenta postupným připojováním vrcholů) → kostra T
  2. Zvolí se vrchol u a preorder (pořadí prvního navštívení vrcholu) se očíslují vrcholy pomocí DFS(T,u) → pořadí vrcholů dané očíslováním.
  3. Výsledná HK je určena očíslováním z kroku 2.
DK: Ať H* je opt. HK a T je minimální kostra, potom c(T)≤c(H*).
W je úplná procházka po T (viz krok 2.), potom c(W)=2*c(T)≤c(H*).
Z W se vyrobí H nahrazováním cest délek ≥2 jednou hranou (vracení se v DFS průchodu a první dopředný krok). Jelikož zde platí trojúhelníková nerovnost, platí také: c(H)≤c(W).
Platí c(H)≤c(W)=2*c(T)≤c(H*) potom ρ≤2.
  • Ať ρ≥1 je konstanta. Pokud P≠NP, potom neexistuje polynomiální aproximační algoritmus řešící obecný TSP s poměrovou chybou ρ.
    • Pokud by existoval, umí řešit HK (ten je NPÚ). Graf se doplní na K|V| a váhy hran se definují:
$ c(e) = \begin{cases} 1, & \mbox{pokud }e\in E \\ \rho\cdot n+1, & \mbox{pokud }e\notin E \end{cases} $
Nyní algoritmus buď vydá HK délky n (→Odpověď na HK v původním grafu je ANO), nebo vydá HK délky >ρ·n (→Odpověď na HK v původním grafu je NE).

Metody tvorby algoritmů[editovat | editovat zdroj]

Dynamické programování[editovat | editovat zdroj]

Viz wen:Dynamic programming, Násobení matic od Jakuba Černého nebo dynamické programování podle kuchařky KSP.

Věta o dynamickém programování: papír Dynamické programování od Jiřího Vyskočila na strojilovych stránkách.

Využití:

  1. "překrývání podproblému" (problém lze rozdělit na podproblémy, jejichž řešení se využívá opakovaně).
  2. "optimální podstruktury" (optimální řešení lze zkonstruovat z optimálních řešení podproblémů).

Příklady použití:

Hladový algoritmus[editovat | editovat zdroj]

wen:Greedy algorithm

Matroid je usp. dvojice M=(S,I) splňující podmínky:

  1. S je konečná neprázdná množ. prvků.
  2. I je neprázdná množina podmnožin množiny S (nezávislých podmnožin - význam podle kontextu konkrétního matroidu) taková, že má dědičnou vlastnost (B in I & A subset B potom A in I).
  3. Ivýměnnou vlastnost (pokud A,B in I tž. |A|<|B| potom existuje x in B-A: A+{x} in I).

(Pozn. Pro vážený matroid se doplňuje funkce w: S->R0+ pro podmnožiny S suma přes prvky.)

Všechny max. nezávislých množiny mají stejnou velikost.

Greedy(M,w):
0. A={}
1. Setřiď S sestupně
2. foreach x in S do //seřazené podle vah
     if A+{x} in I then //test na nezávislost!
       A=A+{x} //rozšíření
3. return A

Složitost:

  1. Θ(n*log(n))
  2. n*test na nezávislost (zde jsme ignorovali složitost rozšiřování A, asi snazší než test na nezávislost)
    • Lemma 1: x in S tž. {x} not in I, potom neex. A in I tž. x in A.
    • Lemma 2: S setříděný dle vah do nerost. posl. a x je první v S tž {x} in I. Potom existuje optimální A sub S tž. x in A.
    • Lemma 3: x z lemma 2. pak pro matroid M je nalezení optima ekvivalentní hledání optima pro M' tž. $ S'=\{y \in S; \{x,y\} \in I\} $ a $ I'=\{B \subseteq S-\{x\}; B+\{x\} \in I\} $ (kontrakce prvkem x).

Pozn.: Lemma 1–3 -> Greedy(M,w) vrací optimální množinu.

Pr.: Minimalní kostra grafu

Základy pravděpodobnostních algoritmů[editovat | editovat zdroj]

Viz kapitola 7 knihy Computational Complexity:A Modern Approach - Arora S., Barak B.
Testovani prvociselnosti, Koubek
Základ (lidštěji) shrnut na 5 stranách:
Crash course on complexity theory with emphasis to Randomized computation, Mark Bläser

Zmatení pojmů[editovat | editovat zdroj]

Pri studiu clovek narazi na dve deleni v souvislosti s použitím náhodnosti ve výpočtech:
  • Deleni dle typu algoritmu: [en.wikipedia.org/wiki/Las_Vegas_algorithm, Las Vegas] , [en.wikipedia.org/wiki/Monte_Carlo_algorithm, Monte Carlo], Atlantic City [pouziva prof. Koubek na zaklade S.Ulama/N.Metropolise - tvurcu pojmenovani MonteCarlo]
  • Deleni dle slozitostnich trid - BPP, BTIME, ZPP, coRP, RP,PP, ... [pouziva prof.Sgall, Arora Barak a "složitostníci"]

Dělení dle algoritmů se dá namapovat na složitostní třídy (a je dobře popsáno na anglické Wikipedii).

Pravdepodobnostní Turingův stroj (PTS) - definice[editovat | editovat zdroj]

Rozsirime Turinguv stroj o moznost pouzivat ve vypoctech náhodnost. Pravdepodobnostní Turingův stroj (PTM) je Turingův stroj se dvěma přechodovýma funkcema $ \delta_0, \delta_1 $.

Výpočet PTS M na vstupu x probíhá tak, že v každém kroku se s pravděpodobností $ \tfrac{1}{2} $ použije $ \delta_0 $ a s pravděpodobností $ \tfrac{1}{2} $ použije $ \delta_1 $. Toto rozhodnutí je nezávislé na předchozích rozhodnutích.

Výstupem stroje je buď 1(přijetí) nebo 0(odmítnutí). M(x) označíme náhodnou proměnnou, jejíž hodnota je hodnota výstupu stroje M nad vstupem x.

Stroj M běží v čase T(n), kde $ T: N \rarr N $, pokud se zastaví maximálně po $ T( \left | x \right | ) $ krocích nezávisle na náhodných rozhodnutích.

Strom možných výpočtů PTS po $ t $ krocích je tedy úplný binární strom, existuje tedy $ 2^t $ různých větví výpočtu. Každá větev má pravdepodobnost $ \frac{1}{2^t} $. Tedy pravděpodobnost, že stroj M přijme vstup x, tj. $ P[M(x) = 1] $ je počet přijímajících větví z celkového počtu větví.

Pozor! Zde vznikaji jemné rozdíly mezi nedeterministickym Turingovym strojem (NDTM) a PTM. U NTDM řekneme, že přijímá slovo, pokud existuje ve stromu možných výpočtů větev, která končí v přijímacím stavu. U PTM uvažujeme celou množinu výpočetních větví, ve kterých končí výpočet v přijímacím stavu. Další rozdíl je na urovni konceptu kde jsou PTM blizke TM, protoze narozdil od NDTM maji modelovat skutecne vypocetni stroje.

RP, co-RP[editovat | editovat zdroj]

Jazyk L patří do třídy RP, když pro něj existuje PTS M pracující v polynom. čase. Slovo z L storj přijme s pstí aspoň 0.5, slovo mimo jazyk vždy odmítne: $ x\in L \implies p(acc) \geq 0.5; x \notin L \implies p(acc) = 0 $. Tedy, pokud stroj slovo přijal, je určitě z jazyka. Pokud slovo odmítl, nic nevíme.

P je podmnožina RP - daný TS převedeme na PTS tak, že obě přechodové funkce zvolíme totožné. PTS přijme slovo z jazyka pravděpodobností 1, 1 >= 0.5. RP je podmnožina NP - PTS převedeme na NTS tak, že z každého displeje zvolíme dvě možná pokračování podle dvou přech. fcí. NTS vždy přijme slovo z jazyka, jelikož v PTS existovala přijímající větev.

Když zauvažujeme nad podobou co-RP, odvodíme, že pro L z co-RP existuje PTS M, který vždy přijme slovo z L, slovo mimo L odmítne s pstí >= 0.5. $ ZPP = RP \cap co-RP $. Pro jazyk ze ZPP tedy existují dva stroje A (RP) a B (co-RP). Nový stroj může pustit slovo do A: když přijme, vracím ANO. Pak pustí slovo do B: když odmítne, vracím NE. Jinak můžu vrátit třetí hodnotu NEVÍM (třetí hodnota (vědomí si své chyby) nebyla možná u RP ani u co-RP, jen u ZPP). Algoritmy ze ZPP se označují Las Vegas (vrací ANO, NE, NEVÍM v poly-čase, vždy jim lze věřit).

BPP[editovat | editovat zdroj]

Jazyk L patří do třídy BPP, když pro něj existuje PTS M pracující v polynom. čase. Slovo z L stroj přijme s pstí aspoň 2/3, slovo mimo L stroj odmítne s pstí aspoň 2/3: $ x\in L \implies p(acc) \geq 2/3; x \notin L \implies p(acc) < 1/3 $. Jinými slovy, pravděpodobnost chybné odpovědi je menší než 1/3.

RP je podmnožina BPP. Stroj M pro jazyk z RP vždy odmítne slovo mimo jazyk, 0 < 1/3. Stroj M přijme slovo z L s pstí 1/2, pro třídu BPP ale potřebujeme 2/3 ... Spustíme M dvakrát! Pokud aspoň jednou vrátí ANO, vracíme ANO, jinak NE. Pro slovo z jazyka, pst(NE) < 1/2, pst(NE, NE) < 1/4, po dvou spuštěních je pravděpodobnost přijetí aspoň 3/4, 3/4 > 2/3 (a čas zůstal polynomiální). Tento trik (opakování) je velmi častý v této oblasti, říká se mu "amplifikace pravděpodobnosti".

Je zvykem se domnívat, že P není rovno NP. Podobně je zvykem se domnívat, že P = BPP.

$ P \subseteq ZPP \subseteq (RP, co-RP) \subseteq BPP \subseteq PSPACE $

Algoritmy z BPP se označují Monte Carlo (vrací ANO, NE v poly-čase, ale nelze jim vždy věřit). Odpověď ANO může být chybná i NE může být chybná (oboustranná chyba). Někdy odpověď ANO je vždy správná a NE může být chybná (jednostranná chyba) - pak algoritmus vyhovuje dokonce třídě RP. Chybu lze zmenšovat opakováním.

BPP a BPTIME[editovat | editovat zdroj]

  • BPP znamená 'bounded-error probabilistic polynomial-time'
  • BPP prijima i odmita s psti 2/3.
    • Coz muze vest k otazce: 2/3 + 2/3 je vice nez jedna (coz se nam u pravdepodobnosti nelibi). Zde je nutne uvedomit si, co veta rika. Pokud slovo do jazyka patri, pak s psti 2/3 je prijato (a s psti 1/3 odmitnuto). Pokud slovo do jazyka nepatri je s psti 2/3 odmitnuto (a psti 1/3 prijato).

Complexity BPP class definition.jpg

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


Pracovni text:

BPP prijima i odmita s psti 2/3.
Alternativni definice: podobne jako u NTS - spolu se vstupem dame DTS polynomialni certifikat(sekvence rozhodnuti pro kazdy krok)
Vi se, ze BPP je nekde mezi P a EXP.
Ale nevi se ani jestli BPP je ostre v NEXP.
Hlavni otevreny problem je jestli BPP = P. (Hodne teoretiku veri, ze ano!)
Priklady: pocitani medianu, testovani prvociselnosti,

RP, coRP, ZPP[editovat | editovat zdroj]

Tato část je neúplná a potřebuje rozšířit. chtelo by to sem prepsat nejaky vycuc

Materiály[editovat | editovat zdroj]

  • Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach [draft January 2007]. Remark 1.5, page 1.7 (17).