====== IN14 Složitost ======
===== Zadání ====

(časová a prostorová složitost, hierarchie tříd složitosti a vztahy mezi nimi. NP-těžké a NP-úplné úlohy. Polynomiální redukce. Příklady NP-těžkých a NP-úplných úloh. Metody důkazu NP-těžkosti.)

===== Vypracování =====

==== Základní informace ====
Pro tuto otázku se předpokládá základní znalost [[home:inf:in12|Turingových strojů]], [[home:inf:in13|redukce]] a algebry (měla by stačit v rozsahu [[home:inf:ap1|AP1,IN1 Množiny a relace]]).

Hlavní sdělení teorie složitosti:
  * Některé z řešených problémů nejsou prakticky řešitelné v rozumném čase
  * Klasifikace a možnost porovnání složitosti algoritmicky řešitelných i neřešitelných problémů
  * Problémy lze řešit nekonečně mnoha programy, existují mezi nimi nejjednodušší?





==== Časová a prostorová složitost ====

Časovou složitost chápeme jako počet kroků výpočtu algoritmu (Turingova stroje), závisí na velikosti vstupu, proto provádíme analýzu nejhoršího případu tzv. horní odhad (s analýzou nejlepšího případu se setkáváme zřídka).
<box 95% round blue|Definice(1), časová složitost DTS>
Nechť **//M//** je daný deterministrický TS(DTS), který zastaví pro každý vstup. <color blue>Časová složitost</color> stroje **//M//** je funkce **//Time<sub>M</sub>:N->N//** definována takto:

//

**Time<sub>M</sub>(n) = max{ Steps<sub>M</sub>(x) | |x|=n }**//

kde Steps<sub>M</sub>(x) je počet kroků, které provede stroj **//M//** pro vstup //**x**// a //**|x|**// je délka vstupu TS</box>

<box 95% round blue|Definice(2), časová složitost NDTS>Nechť **//M//** je daný nedeterministrický TS(NDTS) takový, že pro každý stup má výpočetní strom všechny výpočetní cesty konečné. Čas výpočtu (//**RunTime<sub>M</sub>(x)**//) stroje **//M//** je pro vstup //**x**// je roven maximální délce výpočetní cesty (t.j. maximálnímu počtu kroků, které provede stroj //**M**// pro vstup //**x**//). <color blue>Časová složitost</color> stroje **//M//** je funkce **//Time<sub>M</sub>:N->N//** definovaná takto:

//**Time<sub>M</sub>(n) = max{ RunTime<sub>M</sub>(x) | |x|=n }**// ((slidy Složitost výpočtů a problému, Přednáška č. 6 str 5, definice 1 a 2))</box>


Prostorová složitost je obecně brána jako počet paměťových buněk potřebných k výpočtu algoritmu. U TS je to počet políček pásky. Často se liší s rozdílnou délkou vstupu, provádíme analýzu nejhoršího případu (s analýzou nejlepšího případu se setkáváme zřídka).
<box 95% round blue|Definice(8), prostorová složitost DTS>Nechť **//M//** je daný deterministrický TS(DTS), který zastaví pro každý vstup. Řekneme, že **//M//** má prostorovou složitost **//Space<sub>M</sub>:N->N//**, jestliže  **//Space<sub>M</sub>(n)//** je maximální počet políček pásky čtený strojem **//M//**, kde maximum se bere přes všechny vstupy délky **//n//**</box>

<box 95% round blue|Definice(9), prostorová složitost NDTS>Nechť **//M//** je daný nedeterministrický TS(NDTS) takový, že pro každý stup má výpočetní strom všechny výpočetní cesty konečné. Prostorová složitost stroje **//M//** je funkce **//Space<sub>M</sub>:N->N//** taková, že **//Space<sub>M</sub>(n)//** je maximální počet políček čtený strojem **//M//**, kde maximum se bere přes všechny vstupy délky //**n**// a pro každý vstup //**n**// přes všechny výpočetní cesty. ((slidy Složitost výpočtů a problému, Přednáška č. 6 str 23 a 24, definice 8 a 9))</box>
Dále potřebujeme mít nějaký nástroj, který nám pomůže říct, která funkce je obecně složitější, nebo zda jsou dvě funkce podobně složité. Zajímá nás především růst řádu funkce, nikoliv konkrétní složitost v konkrétním případě. Při použití růstu řádu je možné se odprostit od konkrétních podrobností funkce a zdůrazníme tím asymptotické chování t.j. **<color blue>O kolik se výpočet zpomalí pro velmi velký vstup.</color>**

<box 95% round blue|Definice(3) Růst řádu>Nechť <math>\small f:N\rightarrow R^+</math> Položme
<math>O(f)=\{r:N\rightarrow R^+ | \exists n_0\in N,\exists c \in N\ tak, ze\ \forall n \geq n_0 : r(n)\leq c.f(n)\}</math>
Pro <math>\small r\in O(f)</math> říkáme, že //**r**// <color blue>neroste asymptoticky rychleji</color> než //**f**//.


Položme <math>\Omega (f) = \{r:N\rightarrow R^+| \exists n_0 \in N, \exists c \in N\ tak,ze\ \forall n \geq n_0 : r(n)\geq \frac{1}{c} f(n)\} </math>
Pro <math>\small r\in \Omega (f)</math> říkáme, že //**r**// <color blue>roste asymptoticky alespoň tak rychle</color> jako //**f**//.


Položme <math> \Theta (f) = O(f)\cap \Omega (f)</math>. Pro <math> g\in \Theta (f)</math> říkáme, že //**g**// a //**f**// jsou <color blue>asymptoticky ekvivalentní</color> (mají stejný řád růstu)


Nechť <math>\small f,g: N\rightarrow R^+</math>. Jestliže
<math>\lim_{\small{n\rightarrow \infty}}\frac{f(n)}{g(n)}=0</math>
Pak řekneme, že //**g**// <color blue>roste asymptoticky rychleji</color> než //**f**// a píšeme
<math>f=o(g)</math>((slidy Složitost výpočtů a problému, Přednáška č. 6 str 9 a 1, definice 3))</box>

==== Hierarchie tříd složitosti ====
Základní rozdělení je dle toho, zda je problém řešitelný v polynomickém čase DTS, nebo TS.
Následně podle složitosti výpočtu máme třídy logaritmické, polynomické a exponenciální

<box 95% round blue|Deterministické třídy složitosti>

Nechť //**f:N->R<sup>+</sup>**//

<math> 
TIME(f) = \{L(M) | Time_M (n) \in O(f(n)) \}
</math>

<math>
SPACE(f) =  \{L(M) | Space_M (n) \in O(f(n)) \}
</math>

<math>
DLOG = SPACE(logn)
</math>

<math>
P = \bigcup_k TIME(n^k)
</math>

<math>
PSPACE = \bigcup_k SPACE(n^k)
</math>

<math>
EXPTIME = \bigcup_k TIME(2^{n^k})
</math> ((slidy Složitostní třídy, přednáška č. 7, str. 1))</box>Příklady problémů z P:
  * PATH (hledání nejkratší cesty)
  * RELPRIME = {<x,y> | x a y jsou relativní prvočísla} (2 čísla jsou relativní prvočísla, když jejich NSD je roven 1), v P vypočítáme například pomocí Euklidova algoritmu
  * Každý CFL in P (důkaz pomocí dynamického programování)

<box 95% round blue|Nedeterministické složitostní třídy>

Nechť //**f:N->R<sup>+</sup>**//

<math>
NTIME(f) = \{L(M) | M\ je\ NTS\ a \ Time_M (n) \in O(f(n)) \}
</math>

<math>
NSPACE(f) =  \{L(M) |M\ je\ NTS\ a \ Space_M (n) \in O(f(n)) \}
</math>

<math>
NLOG = NSPACE(logn)
</math>

<math>
NP = \bigcup_k NTIME(n^k)
</math>

<math>
NPSPACE = \bigcup_k NSPACE(n^k)
</math>

<math>
NEXPTIME = \bigcup_k NTIME(2^{n^k})</math> ((slidy Složitostní třídy, přednáška č. 7, str. 14))</box>

<box 95% round blue|Definice (12), verifikátor>Verifikátorem pro jazyk **//A//** je algoritmus **//V//** takový, že  **//A//** = {//**w**// | //**V**// akceptuje <//**w**//,//**c**//> pro nějaký řetězec //**c**// }((slidy Složitostní třídy, přednáška č. 7, str. 19))</box>Verifikátor požívá dodatečnou informaci (//**c**//) k potvrzení, že //**w**// je z //**A**//. //**c**//
se nazývá <color blue>svědek</color>.

<box 95% round blue|Definice (13), třída NP>**NP** je třída jazyků, které mají polynomický verifikátor. ((slidy Složitostní třídy, přednáška č. 7, str. 20))
</box>
Idea důkazu: NTS nedeterministicky uhádne řešení problému a poté ověří v polynomickém čase (pomocí verifikátoru).
Takže problém patří do NP, jestliže umíme v polynomickém čase potvrdit správné řešení.


příklady z **NP**
  * HAMPATH neorientovaný graf má hampath, jestliže existuje orientovaný cyklus, která vede přes každý vrchol právě jednou (obdobný s TSP - obchodní cestující - projít všechny body s nejkratší celkovou cestou)
  * 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ů)
  * další příklady viz. NP-úplné předměty




==== Vztahy mezi třídami složitosti ====
<math>
DTIME(f(n)) \subseteq NTIME(f(n))
</math>

<math>
DSPACE(f(n)) \subseteq NSPACE(f(n))
</math>
//Odůvodnění: deterministické TS jsou i nedeterministicke TS.//

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

<note tip>Nemáte o prázdninách brigádu a chcete něco solidně zaplaceného? Zkuste třeba vyřešit otázku, zda <math>\large NP=^?P</math>. Dostanete 1 milion dolarů a navíc budete ve skriptech, a to se vyplatí. Více informací naleznete na stránkách [[http://www.claymath.org/millennium/|Clay Mathematics Institute]]. Jde o otevřený problém, který zatím nikdo nevyřešil. Obecně se věří v nerovnost. Pokud by se třídy rovnaly, mělo by to zásadní dopad na současné fungování např. kryptografie.
</note>

Nejlepší dosud možný způsob, jak řešit problémy z NP na deterministických strojích, je použít exponenciální algoritmus. Umíme dokázat, že:
<math>
NP \subseteq EXPTIME
</math>

<box 95%  round orange|Cook-Karpova teze>//**P**// obsahuje právě všechny prakticky řešitelné problémy
</box>Pouze teze, podobně jako Churchova, je pro ni méně indicií, než pro Churchovu tezi, ale v současnosti se věří, že platí(t.j., že <math> NP\neq P</math>). 

Další známé vztahy mezi složitostními třídami:
<box 95%  round green| Věta 1.> Nechť <math>\small S(n)\geq log(n)</math>(složitost musí být alespoň logaritmická, při konstantní složitosti budou vztahy "hezčí").
Pak

  - <math>DTIME(T(n)) \subseteq SPACE(T(n))</math>
  - <math>NTIME(T(n)) \subseteq NSPACE(T(n))</math>
  - <math>DSPACE(S(n)) \subseteq DTIME(2^{OS(n)})</math>
  - <math>NSPACE(S(n)) \subseteq NTIME(2^{OS(n)})</math>
</box>
Odůvodnění 3. a 4. části - lze dokázat, že (N)DTS může být upraven tak, aby skončil po <math>\small 2^{OS(n)}</math> krocích a přitom akceptoval stejný jazyk. Důkaz viz slidy((Slidy - vztahy mezi složitostními třídami, přednáška č.9 str 4,5))

<box 95%  round green| Věta 2.> Nechť  <math>\small S(n)\geq log(n)</math>. Pak

  - <math>NTIME(T(n)) \subseteq DSPACE(T(n))</math>
  - <math>NSPACE(S(n)) \subseteq DTIME(2^{OS(n)})</math>
</box>
Odůvodnění: Provedeme DFS TODO na výpočetním stromu NTS //**M**// a vytvoříme strom postupně. Akceptujeme, jakmile narazíme na akceptující konfiguraci. Důkaz 1. i 2. části viz slidy((Slidy - vztahy mezi složitostními třídami, přednáška č.9 str 6,7))

<box 95%  round green| Věta 3. Savitchova věta>

<math>
NSPACE(S(n)) \subseteq DSPACE(S((n)^2)
</math></box>Odůvodnění: Nedeterministický stroj o složitosti //**n**// lze simulovat deterministickým strojem, který bude potřebovat maximálně **//n<sup>2</sup>//** prostoru (což je pro nás obojí polynomické). Detailní důkaz viz slidy((Slidy - vztahy mezi složitostními třídami, přednáška č.9 str 10-13)) nebo skripta

Mnohem důležitější je však důsledek této věty:

<math>
NPSPACE = PSPACE
</math>

Celková klasifikace:

<math>
LOGSPACE \subseteq NLOGSPACE \subseteq P \subseteq NP \subseteq PSPACE = NPSPACE \subseteq EXPTIME
</math>

<math>
LOGSPACE \subset PSPACE
</math>

<math>
P \subset EXPTIME
</math>


==== Polynomiální redukce ====
Pro lepší pochopení jsem redukci zařadil před np-úplné problémy.
<box 95% round blue|Definice(11; 1.22) Polynomické redukce>Nechť <math>\small A, B \in \Sigma^*</math>, Řekneme, že **A** se polynomicky redukuje na **B**, píšeme <math>\small A \leq_P 
B</math> právě když <math>\small A \leq_m B</math> a redukční funkce <math>\small f:\Sigma^*\rightarrow\Sigma^*</math>, je vyčíslitelná TS **M**, který je časově omezen polynomem. (**f** je vyčíslitelná v polynomickém čase a taková, že pro každé <math>w \in \Sigma^*</math> platí: <math> w \in A <=> f(w) \in B</math> ((slidy Složitostní třídy, přednáška č. 7, str. 8))
</box> 

Definici <math>\small \leq_m</math> doufám naleznete [[home:inf:in13|zde]]

Lidově řečeno: Pokud máme problém **//A//** a dokážeme vymyslet alogritmus(fkce **f**), který nám tento problém převede na problém **//B//** a složitost toho algoritmu je maximálně polynomická, tak se **//A//** polynomicky redukuje na **//B//**

<box 95%  round green| Lemma 12; 1.23 Transitivita redukce>Relace <math>\small \leq_P </math> je reflexivní, transitivní, t.j. je kvaziuspořádání.
</box>//to by měl každý umět dokázat na požádání, pro jistotu://
  * 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á)


==== NP-těžké úlohy a NP-úplné úlohy====
Místo //**co-P**// uvažujeme problémy, které jsou stejně těžké, jako ostatní problémy v NP

<box 95%  round blue|Definice 1.26 NP-těžká a NP-úplná úloha>Jazyk **//B//** je **NP-úplný**, jestliže:
1. <math>\small B \in NP</math>
2. pro každý jazyk <math>\small A \in NP</math> platí <math>\small A \leq_P B</math>
Pokud **//B//** splňuje pouze druhou podmínku, pak se nazývá **NP-těžký**.((skripta Složitost, str. 16))</box>
<box 95%  round green|Věta 23; 1.27>Jestliže **//B//** je NP-úplný a <math>\small B \in P</math>, pak <math>\large P = NP</math> (z definice)</box>Pokud jste vzali tip na brigádu vážně, tak vám určitě došlo, že abychom dokázali, že **P = NP** stačí najít problém z P, který je zároveň NP-úplný. (pokud vám to nedošlo, tak hledejte brigádu radši [[http://brigady.prace.cz/index.php?page=result&branch%5B%5D=7&branch%5B%5D=5&branch%5B%5D=6&locality=1&work_kind=|tady]])

NP-úplné problémy hrají podobnou roli jako problém zastavení ve vyčíslitelnosti.



==== Příklady NP-těžkých a NP-úplných úloh ====
Mějme výrokovou formuli **F** (v [[home:inf:ap4|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).
Je dán kód formule **F**, a ptáme se Je **F** splnitelná?
Tuto úlohu nazýváme **SAT**

<box 95%  round green|Věta 1.29 Cook-Levin>SAT(problém splnitelnosti) je NP-úplný</box>//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á.



**3SAT**
Obdoba SAT, ale každá formule má právě 3 členy

**CLIQUE**
Ptáme se zda má zadaný graf n-kliku.

**HAMPATH**
Nalezení hamiltonské cesty v grafu

Ale pozor, funkce co-CLIQUE nepatří do NP. Verifikace toho, že něco není přítomno se zdá být obtížnější. Takovéto problémy patří do co-NP. Nevíme, zda se co-NP a NP liší.

==== Metody důkazu NP-těžkosti ====

Problémy dokazujeme redukcí problému, který víme, že je NP-těžký, respektive NP-úplný (např. SAT) na zadaný problém.

Příklady:
SAT se polynomicky redukuje na 3SAT
3SAT se polynomicky redukuje na CLIQUE //viz řešené příklady//
//nezapomeňte že polynomická redukce je transitivní//


===== Předměty =====
  * [[https://is.muni.cz/auth/predmety/predmet.pl?obdobi=3724;kod=IB107|FI:IB107]] Vyčíslitelnost a složitost (podzim 2007), prof. RNDr. Luboš Brim, CSc.
  * [[https://is.muni.cz/auth/predmety/predmet.pl?id=427574|FI:IA012]] Složitost (jaro 2008), prof. RNDr. Ivana Černá, CSc. (pozn. magisterský předmět)

===== Použitá literatura =====
  * prof. RNDr. Luboš Brim, CSc., [[http://www.fi.muni.cz/usr/brim/IB107/IB107-slidy.html|slidy přednášek]] (dostupné pouze z domény muni.cz)
  * prof. RNDr. Luboš Brim, CSc., [[http://www.fi.muni.cz/usr/brim/IB107/IB107-texty.html|staré nebo nové učební text]] (dostupné pouze z domény muni.cz)
  * [[http://www.fi.muni.cz/usr/brim/PS/IB107/cviceni_zadani.ps|příklady cvičení]] (dostupné pouze z domény muni.cz)



===== Vypracoval =====
Gizmo - Marek Babák ICQ: 67179550 zpracuji do 25.5.2008
stav - 99% z mé strany hotovo, pokud chcete někdo něco doplnit, do toho.

FIXME Je potřeba ještě zapracovat [[http://statnice.dqd.cz/tmp/slozitost.pdf|poznámky od Jitky Pospíšilové]].

~~DISCUSSION~~