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

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
(Konstruovatelné funkce)
(Vztahy mezi časovými a prostorovými mírami a determinismem a nedeterminismem)
Řádka 88: Řádka 88:
  
 
Triviální vztahy
 
Triviální vztahy
* <math>DSPACE(TIME) \subseteq NSPACE(TIME)</math>
 
 
* <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)
 
* <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)
  

Verze z 16. 9. 2008, 03:49

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 $ 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 pozici 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), pak zjistí, jak budou vypadat po těch 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.

Blumova věta o zrychlení

see wen:Blum's speedup theorem

Nechť $ r(n) $ je rekurzivní funkce. Potom existuje rekurzivní jazyk $ L $ takový, že pro každý DTS $ M_i $ rozpoznávající $ L $ v prostoru $ S_i(n) $ existuje DTS $ M_j $, rozpoznávající $ L $ v prostoru $ S_j(n) $, kde $ r(S_j(n)) \leq S_i(n) $ skoro všude.

(Tj. existují rekurzivní jazyky, jejichž rozpoznávání lze stále zrychlovat. Věta existuje i ve verzi pro časovou složitost. Věta ukazuje že když zkoumáme složitost a nepředpokládáme konstruovatelnost, můžeme dostat divnosti.)

Důkaz je ve Strojilovi na stranách 24-25.

Borodinova věta mezerách

see wen:Gap theorem

Nechť $ g(n) \geq n $ je rekurzivní funkce. Potom existuje rekurzivní funkce S(n) taková, že DSPACE( S(n) ) = DSPACE( g(S(n)) )

(Pokud nepředpokládáme konstruovatelnost, dostáváme divnosti -- viz věty o hierarchii, které říkají že když se přidá na prostoru, dostaneme větší třídu jazyků.)

Věty o hierarchii tříd složitosti

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

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

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) $ a $ S_2 $ je prostorově konstruovatelná. 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.

O časové hierarchii

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

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

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:PSPACE-complete
  • PSPACE-complete problém: kvantifikovaná boolovská proměnná (důkaz podobný důkazu Savichovy věty).
  • dále typicky hry (zoběcněný wen: Hex (board game))

Polynomiální hierarchie

see polynomiální hierarchie, wen:Polynomial hierarchy

NP(C) je třída jazyků, které v polynomiálním čase rozpozná NTS s orákulem detekujícím zda jeho vstup patří do nějakého jazyka z C.

NP(P) je potom třída jazyků, které v polynomiálním čase pozná NTS s orákulem na řešení problémů z P. NP(NP) řeší NTS s orákulem na řešení problémů z NP.

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

Polynomiální hierarchie
Máme $ \Sigma_0 = P $, $ \Sigma_{i+1} = NP(\Sigma_i) $
  1. $ \Sigma_0 = P $
  2. $ \Sigma_1 = NP(P) = NP $
  3. $ \Sigma_2 = NP(NP) $

Celá hierarchie je $ PH = \bigcup_{i=0}^\infty {\Sigma_i} $.

PH je v PSPACE

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

Pseudopolynomiální algoritmy

see wen:Pseudo-polynomial time

Dolní odhady pro uspořádání (rozhodovací stromy)

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

Třídíme-li s pomocí porovnávání, můžeme si výpočet znázornit binárním stromem. Začínáme v kořeni, v uzlech porovnáváme a větvíme, v listech máme setříděno. Pro každá vstupní data se výpočet někde odliší od ostatních, strom má $ n! $ listů (tolik je možných uspořádání množiny s $ n $ prvky.) Výška stromu je počet provedených porovnání při nejdelším výpočtu (v nejhorším případě) je alespoň $ \log_2(n!) $. (Úplný binární strom s $ k $ listy má výšku $ \log_2 k $, neúplný je vyšší.) Časová složitost třídícího algoritmu založeného na porovnávání proto nemůže být lepší než $ O(\log_2(n!)) = O(n\ \log n) $.

Podle Stirlingovy formule:

$ n! \approx \sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n} $ (to je ona)
$ O(\log_2 n!) = O(\log_2{\sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n}}) = O(n \log n) $ (Logaritmus odmocniny bude asymptoticky $ O(\log n) $, $ (n/e)^n $ bude $ O(n \log n) $, a požere to.)

Aproximační algoritmy a schémata

see wen:Approximation algorithm, kus na straně 12 z [1]

Metody tvorby algoritmů

dynamické programování podle kuchařky

soubory - vety, dukazy, lammata ze strojilovych stranek, autor Jiří Vyskočil

Další materiály

  • Dasgupta S., Papadimitriou C.H., Vazirani U.V., Algorithms, Berkeley [2]
  • Arora S., Barak B., Complexity Theory: A Modern Approach, Princeton [3]