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

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ě

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

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:

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

  2. <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>:

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

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

  • Funkce <math>f:\mathbb{N} \rightarrow \mathbb{N}</math> je rekurzivní pokud existuje DTS M takový, že pro vstup 1n vydá výstup 1f(n).

  • Funkce <math>f:\mathbb{N} \rightarrow \mathbb{N}</math> 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 <math>f:\mathbb{N} \rightarrow \mathbb{N}</math> 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 <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) ≥ n + 1 1 ).

  • 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

  1. <math>DTIME (f(n)) \subseteq NTIME(f(n))</math><br/><math>DSPACE (f(n)) \subseteq NSPACE(f(n))</math>

    • triviálně platí

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

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

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

  1. <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 CL 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.

  2. <math>L \in NTIME(f(n))</math>, pak <math>L \in DTIME(C_L^{f(n)})</math>, 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 <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 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. <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>

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

  1. <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 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 <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ě:

  1. <math>\Sigma_0 = \Pi_0 = \Delta_0 = P</math>

  2. <math>\Sigma_{i+1} = NP(\Sigma_i)</math>

  3. <math>\Delta_{i+1} = P(\Sigma_i)</math>

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

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

  1. i = 0; <math>\Sigma_0 = P \subseteq PSPACE</math>

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

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 ~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í

*ρ=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<&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 δ 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,&epsilon;):

Metody tvorby algoritmů

Dynamické programování

Hladový algoritmus

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