Státnice - Informatika - Složitost

Z ωικι.matfyz.cz
Verze z 28. 5. 2008, 02:13, kterou vytvořil Che (diskuse | příspěvky) (Savitchova věta: formátování)

Přejít na: navigace, hledání

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 ztlačí jedno 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 stihnout změnit nejvýše dvě políčka nového stroje)
  • Je-li L jakyk příjímaný k-páskovým DTS M (k>=2) a s časovou složitostí $ t(n) \in \omega(n) $. Potom pro kažé 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řijmou musí, tj. taky spor.

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_1) \setminus DSPACE(S_2) $.

To s omegou znamená že $ S_1 $ není omezená $ S_2 $ (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 prostorově konstruovatelná. Potom existuje jazyk L takový, že $ L \in DTIME(T_1) \setminus DTIME(T_2) $.

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.

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". Z toho 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.
Necht 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 ceil(S(n)/r)
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).

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

  • $ DSPACE(TIME) \subseteq NSPACE(TIME) $
  • $ \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í
  2. $ DTIME(f(n)) \subseteq DSPACE(f(n)) $
    • z vět o lineární kompresi a redukci počtu pásek
  3. $ 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ů).
    • Zkonstruujeme M', který simuluje M a nejvýše po $ d^{f(n)} $ krocích se zastaví. (Potřebujeme předpoklad časové konstruovatelnosti funkce f.)
  4. $ 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). 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

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

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ň log2(n!). (Úplný binární strom s k listy má výšku log2 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(log2(n!)) = O(n log n).

Podle Stirlingovy formule:

$ n! \approx \sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n} $
$ 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 n log n, a požere to.)

Aproximační algoritmy a schémata

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

Metody tvorby algoritmů