===== Zadání =====
2. Třídy výpočtové složitosti a vztahy mezi nimi
===== Vypracování =====

==== Základní pojmy ====

=== Časová složitost ===
T: N->N
NTS M má časovou složitost T(n)  <math>\Leftrightarrow</math> výpočet pro každý vstup x se zastaví pro nanejvýš max T(|x|) výpočetních kroků (nerozlišujeme akceptující a zamítající stavy).

=== Prostorová složitost ===
S: N->N
NTS M má prostorovou složitost S(n)  <math>\Leftrightarrow</math> v každém výpočtu v každém vstupu x je stroj operací max S(|x|) políček (zajímají nás políčka na pracovní pásce, ne samotný vstupní řetězec).
  * regulární jazyk má nulovou prostorovou složitost

=== Prostorově konstruovatelná funkce ===
S(n) je prostorově konstruovatelná  <math>\Leftrightarrow \exists</math> TS se vstupní a 1 pracovní páskou takový, že pro vstup délky n, označí na pracovní pásce přesně S(n) políček.
  * např. c, n, log(n), f + g, f*g, n!,...

=== Komplement ===
Mějme jazyk L nad abecedou <math>\Sigma</math>.
<math>co-L = \Sigma^*\backslash L </math>

Mějme složitostní třídu C (množina jazyků).
<math>co-C = \{co-L | L \in C \} </math>

co-DTIME(T(n))=DTIME(T(n)) *
co-DSPACE(S(n))=DSPACE(S(n)) *
* změníme akceptující a zamítající stavy

co-NTIME(T(n)) = ? ... jestli není uzavřeno na komplement P <math>\neq</math> NP 
co-NSPACE(S(n)) = NSPACE(S(n))

=== Uzavřenost ===
Deterministické složitostní třídy jsou uzavřené na <math> +, \cdot, \cap, \cup, co- </math>
U nedeterministických je otevřenost na komplement otevřeným problémem.



==== Složitostní třídy ====
= množiny jazyků, které jsou rozhodované se složitostí ohraničenou danou funkcí
  * DTIME(T(n)) = {L(M)| M je DTS s časovou složitostí T(n)}

  * NTIME(T(n)) = {L(M)| M je NTS s časovou složitostí T(n)}

  * DSPACE(S(n)) = {L(M)| M je DTS s prostorovou složitostí T(n)}

  * NSPACE(S(n)) = {L(M)| M je NTS s prostorovou složitostí T(n)}

<box 95% >
 <math> P = DTIME (n^{O(1)}) = \bigcup_{k>0}{DTIME(n^k)} </math>

 <math> NP = NTIME (n^{O(1)}) = \bigcup_{k>0}{NTIME(n^k)} </math>

<math> PSPACE = DSPACE (n^{O(1)}) = \bigcup_{k>0}{DSPACE(n^k)} </math>

<math> NSPACE = NSPACE (n^{O(1)}) = \bigcup_{k>0}{NSPACE(n^k)} </math>

<math> LOGSPACE = DSPACE (log(n)) </math>

<math> NLOGSPACE = NSPACE (log(n)) </math>

<math> EXPTIME = DTIME (2^{n^{O(1)}}) </math>

<math> NEXPTIME = NTIME (2^{n^{O(1)}}) </math>

<math> EXPSPACE = DSPACE (2^{n^{O(1)}}) </math>

<math> NEXPSPACE = NSPACE (2^{n^{O(1)}}) </math>

</box>

<math>
LOGSPACE \subseteq NLOGSPACE  \subseteq P \subseteq NP \subseteq PSPACE = NSPACE \subseteq EXPTIME \subseteq NEXPTIME \subseteq EXPSPACE = NEXPSPACE
</math>

<math>LOGSPACE, NLOGSPACE \subset PSPACE \subset NEXPSPACE</math>

<math>P \subset DEXPTIME</math>

<math>NP \subset NEXPTIME</math>

==== Vztahy mezi složitostními třídami ====
<box 95%| ** Lineární urychlení **>
Je možno dosáhnout konstantního zrychlení za cenu nárustu potřebné paměti.
</box>

=== Determinismus je speciálním případem nedeterminismu: ===
<math>DTIME(T(n)) \subseteq NTIME(T(n))</math>
<math>DSPACE(S(n)) \subseteq NSPACE(S(n))</math>

důsledek: <math>P \subseteq NP </math>

<math>NTIME(T(n)) \subseteq DTIME(2^{O(T(n))})</math>


=== Vztahy mezi časem a prostorem: ===
- prostor je vždy omezen potřebným časem
- nechť S(n) >= log(n)

    - <math>DTIME(T(n)) \subseteq DSPACE(T(n))</math>
    - <math>NTIME(T(n)) \subseteq NSPACE(T(n))</math>
    - <math>DSPACE(S(n)) \subseteq DTIME(2^{O(S(n))})</math>
    - <math>NSPACE(S(n)) \subseteq NTIME(2^{O(S(n))})</math>

Idea důkazu pro 3. a 4.((viz. Vyčíslitelnost a složitost slidy č.9. str.5)):
DTS pracující v prostoru S(n) může být upraven tak, aby skončil po <math> 2^{O(S(n))}</math> krocích a přitom akceptoval stejný jazyk.


=== pro S(n) ≥ log(n) platí: ===
 <math> NTIME(T(n)) \subseteq DSPACE(T(n))</math>
<math> NSPACE(S(n)) \subseteq DTIME (2^{O(S(n))})</math>

  * Idea důkazu: převod NTS na DTS prostřednictvím simulace každé konfigurace a následné procházení grafem, jehož velikost odpovídá počtu konfigurací. Akceptujeme, jakmile narazíme na akceptující konfiguraci.
  * Konstrukce grafu dosažitelných konfigurací: vrcholy stromu představují konfigurace (stavy) a hrana představuje přechod jedním krokem.


=== Sawitchova věta ===
- nechť <math> S(n) \geq log(n) </math>
<math> NSPACE(S(n)) \subseteq DSPACE(S(n)^2)</math>

  * Konstrukce používá pro simulaci rekurzivní proceduru pro hledání cesty (výpočtu) mezi dvěma konfiguracemi simulovaného stoje.

  * Důsledek: PSPACE = NSPACE


=== Immerman - Szelepcsénejiho věta ===
<math>NSPACE(S(n)) = co-NSPACE(S(n))</math>

Idea důkazu:
  * Předpokládáme, že S je prostorově konstruovatelná
  * Předpokládáme, že máme konečnou množinu řetězců A, nedeterministický test příslušnosti do množiny A, známe mohutnost |A| a můžeme si pamatovat maximální délku => z tohoto je možno vytvořit nedet. test pro NEpříslušnost do A (<math> x \notin A \Leftrightarrow \exists </math> akceptující výpočet -- akceptuje, když tam nepatří ):
  - Nedeterministicky uhádneme |A| řetězců
  - Pro každý zvolený řetězec <math> \alpha </math> nedeterministicky ověříme, zda <math> \alpha \in A</math>.
  - Pokud všechny zvolené řetězce patří do A a x není mezi nimi, platí <math>x \notin A</math>.



==== Seperace složitostních tříd ====
Je hirearchie nekonečná? Existuje dolní mez složitosti?
=== DSPACE ===
    * pro deterministické složitostní třídy
    * **Metoda diagonalizace**
    * Věta: Nechť S(n) je prostorově konstruovatelná funkce, pak <math>\exists</math> jazyk <math> L \in DSPACE(S(n))</math> takový, že <math> L \notin DSPACE (S'(n)) </math> pro žádno funkci S'(n) = o(S(n)) (těsná hirearchie - f-ce rostoucí asymptoticky pomaleji než S(n)).

=== DTIME ===
    * Věta: Nechť T(n) je časově konstruovatelná funkce, pak <math>\exists</math> jazyk <math> L \in  DTIME(T(n))</math> takový, že <math> L \notin DTIME (T'(n)) </math> pro žádno funkci T'(n) takové, že <math> T'(n)log(T'(n)) \in o(T(n))</math>.

=== NSPACE ===
    * pro nedeterministické složitostní třídy
    * **Metoda padding **
    * Věta: <math> NSPACE(n^3)  \subset    NSPACE(n^4) </math>


==== P-úplné problémy ====
=== CVP (Circuit Value Problem)===
Problém hodnoty logického obvodu

=== Náležitost řetězce do jazyka bezkontextové gramatiky ===


=== RELPRIME ===
{<x,y> | x a y jsou relativní prvočísla} (2 čísla jsou relativní prvočísla -- také nesoudělná čísla -- když jejich NSD je roven 1), v P vypočítáme například pomocí Euklidova algoritmu 


==== Polynomiální redukce ====
Jazyk **A** se **polynomicky redukuje** na jazyk **B**,<math>A \leq_P B \Leftrightarrow </math> existuje zobrazení <math>R:\Sigma_a^*\rightarrow\Sigma_b^*</math> takové, že pro každý řetězec  <math>w \in \Sigma^*: R(w) \in B \Leftrightarrow w \in A</math> a R je polynomiálně vyčíslitelná.

    * Funkce <math>f:\Sigma^*\rightarrow\Sigma^*</math> je **polynomiálně vypočitatelná ** <math>\Leftrightarrow \exists</math> polynomiálně časově ohraničený TS, který pro vstup w délky n ukončí výpočet v konfiguraci, ve které na pracovní pásce bude zaúsaný řetězec f(w). (dá se vypočítat v polynomiálním čase)
    *3SAT: Obdoba SAT, ale každá formule má právě 3 členy
    
    * Jestli <math>A \leq_P B, B \in P </math>, tak i <math>A \in P </math>. (Problém A je právě tak složitý jako problém B, pokud B se dá redukovat na A)

    * Relace <math>A \leq_P B </math> je reflexivní a transitivní (kvaziuspořádání).
        - reflexivita - libovolný problém dokážeme převést na ten stejný problém v polynomickém čase
        - transitivita - pokud máme alg. //**f**// který redukuje problém //**A**// na problém //**B**// a algoritmus //**g**// který redukuje problém //**B**// na problém //**C**//, pak máme i algoritmus, který převede //**A**// na //**C**// (tím že na problém použijeme nejprve algoritmus //**f**// a následně //**g**//, pokud jejich složitost byla polynomická, bude i výsledná složitost součtem dvou polynomických složitostí, t.j. také polynomická

Jazyk L nazveme **C-těžký** vzhledem k polynomiální redukci pr složitostní třídu C <math>\Leftrightarrow \forall</math> jazyky <math>A \in C</math> platí: <math>A \leq_P L</math> (každý jazyk A z L se dá redukovat na C). Jestli navíc <math>L \in C</math>, tak L nazýváme **C-úplný**(C těžký jazyk nemusí patřit do třídy C).

<box 95%>
    * Jestli nějaký NP-úplný problém patří do P, tak P=NP
    * Jestli <math>P \neq NP</math>, pak žádný NP-ťažký problém není řešitelný v polynomiálním čase
</box>  

==== NP-úplné problémy ====
=== SAT (Cook-Levinova věta) ===
VSTUP: výroková formule **F** v CNF.
Formule **F** je splnitelná, jestliže existuje přiřazení hodnot 0,1 proměnným ve výrokové formuli tak, že je formule pravdivá (1).
OTÁZKA: Je **F** splnitelná?

    * Idea důkazu NP-úplnosti SAT: Nechť //**M**// je nedeterministický TS takový, že //**L(M) = A**//. Nechť //**w**// je vstupní slovo pro //**M**//. Sestrojíme výrokovou formuli //**X**// takovou, že //**M**// akceptuje //**w**// právě, když //**X**// je splnitelná. Konstrukce formule //**X**// bude polynomická.


=== k-CLIQUE ===
VSTUP: neorientovaný graf
OTÁZKA: obsahuje G kliku o k vrcholech?
    * SAT <math>\leq</math> k-CLIQUE 

Klika v neorientovaném grafu je podgraf takový, že existuje hrana mezi každými dvěma uzly. k-klika je klika, která má k vrcholů

=== HAM-PATH ===
VSTUP: neorientovaný graf
OTÁZKA: najít Hemiltovskou cestu
    * SAT <math>\leq</math> HAM-PATH

=== TSP ===
Problém obchodního cestujícího.

=== SUBSET-SUM ===
    * 3-SAT <math>\leq</math> SUBSET-SUM

=== k-ZABARVENÍ GRAFU ===
- pro <math>k \geq 3</math> 
- k=2 - zabarvitelný 2 barvami => je bipartitní (nemá cyklus liché délky) -- v čase polynomiálním prohledáváním do hloubky (šířky)

=== Vrcholové/Množinové pokrytí ===

=== Nezávislá množina ===

=== Celočíselné lineární programování ===

=== Problém rozvrhu ===

==== Logaritmická redukce ====
Jazyk **A** se **logaritmicky redukuje** na jazyk **B**,<math>A \leq_{log} B \Leftrightarrow </math> existuje zobrazení <math>R:\Sigma_a^*\rightarrow\Sigma_b^*</math> takové, že pro každý řetězec  <math>w \in \Sigma^*: R(w) \in B \Leftrightarrow w \in A</math> a R je konstruovatelná v logaritmickém prostoru.


    * Zobrazení <math>R:\Sigma^*\rightarrow\Sigma^*</math> je **log-space konstruovatelné**  <math>\Leftrightarrow \exists</math> DTS se 3 páskami (vstupní, pracovní, výstupní) takový, že pro vstup w vypočítá hodnotu R(w) v prostoru log(|w|).

    * Jestli <math>A \leq_{log} B, B \in DLOG </math>, tak i <math>A \in DLOG </math>. 

    * jestli NLOG-úplný problém patří do DLOG, tak DLOG=NLOG.

==== LOG-úplné problémy====
=== PATH ===
- problém cesty (existuje cesta mezi dvěma vrcholy v neorientovaném grafu?)

    * existence cesty mezi dvěma vrcholy v orientovaném grafu patří do NLOG-úplných problémů. (stejně jako 2-SAT)

==== PSPACE-úplné problémy ====
=== QFB ===
Quantified Boolean Formula - formule predikátové logiky

=== Hra dvou hráčů ===
Jeden hráč se snaží zvítězit tak, že vybírá univerzálně kvantifikované proměnné tak, aby druhý hráč nemohl zvolit žádný existenčně kvantifikovaný prvek.


===== Předměty =====
  * [[https://is.muni.cz/auth/predmet/fi/IB107|IB107 Vyčíslitelnost a složitost]]
  * [[https://is.muni.cz/auth/predmet/fi/IA012|IA012 Složitost]]

===== Zdroje =====
  * [[https://complexityzoo.uwaterloo.ca/Complexity_Zoo|Complexity ZOO]] (especially [[https://complexityzoo.uwaterloo.ca/Petting_Zoo|Petting ZOO]])


~~DISCUSSION~~