*Tento souhrn slouží pro přípravu k magisterským [státnicím](Státnice) pro obory [Teoretická informatika](Státnice%20-%20Informatika%20-%20I1:%20Teoretická%20informatika) a [Diskrétní modely a algoritmy](Státnice%20-%20Informatika%20-%20I4:%20Diskrétní%20modely%20a%20algoritmy). Detailní informace o předmětu hledej na stránkách [Složitost I](Složitost%20I) a [Složitost II](Složitost%20II).* ## Rozsah látky ## Seznam [oficiálních](http://www.mff.cuni.cz/studium/bcmgr/ok/i3b4.htm) státnicových otázek pro studijní obory [Teoretická informatika](Státnice%20-%20Informatika%20-%20I1:%20Teoretická%20informatika) a [Diskrétní modely a algoritmy](Státnice%20-%20Informatika%20-%20I4:%20Diskrétní%20modely%20a%20algoritmy) (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](Státnice%20-%20Informatika%20-%20I2:%20Softwarové%20systémy) a [Matematická lingvistika](Státnice%20-%20Informatika%20-%20I3:%20Matematická%20lingvistika) mají okruhy [Složitost](Státnice%20-%20Informatika%20-%20Složitost%20%28obory%20Matematická%20lingvistika%20a%20Softwarové%20systémy%29) a [Vyčíslitelnost](Státnice%20-%20Informatika%20-%20Vyčí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, [v Majerechovi](http://ktiml.mff.cuni.cz/teaching/files/materials/VladanMajerech_UvodDoSlozitostiANPuplnosti.pdf), 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](http://www.cs.duke.edu/%7Ereif/courses/complectures/books/AB/ABbook.pdf). 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](http://popelka.ms.mff.cuni.cz/cerno/index.php?menu=notes&lang=en) ## 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í](Složitost%20II#Věta%20o%20lineárním%20zrychlení) (asi i [wen:Linear speedup theorem](wen:Linear%20speedup%20theorem))* * 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 ## :*see [Složitost II#Základní třídy složitosti](Složitost%20II#Základní%20třídy%20složitosti), [wen:Complexity class](wen:Complexity%20class), [http://blog.computationalcomplexity.org/2004/07/time-and-space-hierarchies.html](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 $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ý. 1. $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 ### 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 ### #### O prostorové hierarchii #### 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 ##### 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)$. 1. 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) n 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]{: note-class="footnote"}). * 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 ## 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 ### 1. $DTIME (f(n)) \subseteq NTIME(f(n))$
$DSPACE (f(n)) \subseteq NSPACE(f(n))$ * triviálně platí 1. $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) 1. $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))$. 1. $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.) 1. $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. 1. $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 ## :*see [wen:Savitch's theorem](wen:Savitch's%20theorem)* 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 ## :*see [wen:NP-complete](wen:NP-complete), [wen:PSPACE-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)](wen:%20Hex%20%28board%20game%29)) ### Důkazy různých NP-C ### Pochopitelnější důkazy jsou uvedené v Majerechových skriptách (ke stažení ve [studnici](Studnice%20vědomostí)). Lidsky vysvětlený důkaz Cook-Levinovy věty ("Existuje NP-úplný problém") je [zde](KACHL). 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) $ 1. $ 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) $ 1. $ 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 ## **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 ## :*see [polynomiální hierarchie](Složitost%20II#Polynomiální%20hierarchie), [wen:Polynomial hierarchy](wen:Polynomial%20hierarchy), [Pekne a jednoduche vysvetleni](http://www.cs.umd.edu/%7Ejkatz/complexity/f11/lecture8.pdf) - 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$ 1. $\Sigma_{i+1} = NP(\Sigma_i)$ 1. $\Delta_{i+1} = P(\Sigma_i)$ 1. $\Pi_{i+1} = coNP(\Sigma_i)$ kde coNP je definované klasicky množinově na jazycích $coNP(B)=\{A'|A\in NP(B)\}$ 1. $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 ### Věta :: $PH \subseteq PSPACE$ Dokazuje se indukcí podle i 1. i = 0; $\Sigma_0 = P \subseteq PSPACE$ 1. 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 {{TODO|Další vzájemné vztahy, alternující kvatifikátory, kolaps PH}} ## Pseudopolynomiální algoritmy ## :*see [wen:Pseudo-polynomial time](wen:Pseudo-polynomial%20time)* * 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Ú {{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](St%25C3%25A1tnice_-_Informatika_-_Datov%25C3%25A9_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](Státnice%20-%20Aproximační%20algoritmy%20a%20schémata) :*see [wen:Approximation algorithm](wen:Approximation%20algorithm), kus na straně 12 z * ***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 ### ***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 ### #### Vrcholové pokrytí #### *ρ=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 #### *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,ε)**: * ## Metody tvorby algoritmů ## ### Dynamické programování ### 1. 1. * * * * * ### Hladový algoritmus ### 1. 1. 1. 1. 1. * * * ## Základy pravděpodobnostních algoritmů ## ### Zmatení pojmů ### :: * * ### Pravdepodobnostní Turingův stroj (PTS) - definice ### ---- ### RP, co-RP ### ### BPP ### ### BPP a BPTIME ### * * * ### RP, coRP, ZPP ### ## Materiály ## * * * * [^1]: Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach \[draft January 2007]. Remark 1.5, page 1.7 (17).