Obsah

IN14 Složitost
Diskuze

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 Turingových strojů, redukce a algebry (měla by stačit v rozsahu 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).

Definice(1), časová složitost DTS

Nechť M je daný deterministrický TS(DTS), který zastaví pro každý vstup. Časová složitost stroje M je funkce Time_M:N→N definována takto:

Time_M(n) = max{ Steps_M(x) | |x|=n }

kde Steps_M(x) je počet kroků, které provede stroj M pro vstup x a |x| je délka vstupu TS

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_M(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). Časová složitost stroje M je funkce Time_M:N→N definovaná takto:

Time_M(n) = max{ RunTime_M(x) | |x|=n } ¹⁾

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

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_M:N→N, jestliže Space_M(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

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_M:N→N taková, že Space_M(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. ²⁾

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. O kolik se výpočet zpomalí pro velmi velký vstup.

Definice(3) Růst řádu

Nechť $\small f:N\rightarrow R^+$ Položme
$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)\}$ Pro $\small r\in O(f)$ říkáme, že r neroste asymptoticky rychleji než f.

Položme $\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)\}$ Pro $\small r\in \Omega (f)$ říkáme, že r roste asymptoticky alespoň tak rychle jako f.

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

Nechť $\small f,g: N\rightarrow R^+$ . Jestliže
$\lim_{\small{n\rightarrow \infty}}\frac{f(n)}{g(n)}=0$ Pak řekneme, že g roste asymptoticky rychleji než f a píšeme
$f=o(g)$ ³⁾

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í

Deterministické třídy složitosti

Nechť f:N→R⁺

$TIME(f) = \{L(M) | Time_M (n) \in O(f(n)) \}$

$SPACE(f) = \{L(M) | Space_M (n) \in O(f(n)) \}$

$DLOG = SPACE(logn)$

$P = \bigcup_k TIME(n^k)$

$PSPACE = \bigcup_k SPACE(n^k)$

$EXPTIME = \bigcup_k TIME(2^{n^k})$ ⁴⁾

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

Nedeterministické složitostní třídy

Nechť f:N→R⁺

$NTIME(f) = \{L(M) | M\ je\ NTS\ a \ Time_M (n) \in O(f(n)) \}$

$NSPACE(f) = \{L(M) |M\ je\ NTS\ a \ Space_M (n) \in O(f(n)) \}$

$NLOG = NSPACE(logn)$

$NP = \bigcup_k NTIME(n^k)$

$NPSPACE = \bigcup_k NSPACE(n^k)$

$NEXPTIME = \bigcup_k NTIME(2^{n^k})$ ⁵⁾

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 }⁶⁾

Verifikátor požívá dodatečnou informaci (c) k potvrzení, že w je z A. c se nazývá svědek.

Definice (13), třída NP

NP je třída jazyků, které mají polynomický verifikátor. ⁷⁾

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

$DTIME(f(n)) \subseteq NTIME(f(n))$

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

Důsledek:
$P \subseteq NP$

Nemáte o prázdninách brigádu a chcete něco solidně zaplaceného? Zkuste třeba vyřešit otázku, zda $\large NP=^?P$ . Dostanete 1 milion dolarů a navíc budete ve skriptech, a to se vyplatí. Více informací naleznete na stránkách 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.

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:
$NP \subseteq EXPTIME$

Cook-Karpova teze

P obsahuje právě všechny prakticky řešitelné problémy

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 $NP\neq P$ ).

Další známé vztahy mezi složitostními třídami:

Věta 1.

Nechť $\small S(n)\geq log(n)$ (složitost musí být alespoň logaritmická, při konstantní složitosti budou vztahy „hezčí“).
Pak

$DTIME(T(n)) \subseteq SPACE(T(n))$
$NTIME(T(n)) \subseteq NSPACE(T(n))$
$DSPACE(S(n)) \subseteq DTIME(2^{OS(n)})$
$NSPACE(S(n)) \subseteq NTIME(2^{OS(n)})$

Odůvodnění 3. a 4. části - lze dokázat, že (N)DTS může být upraven tak, aby skončil po $\small 2^{OS(n)}$ krocích a přitom akceptoval stejný jazyk. Důkaz viz slidy⁸⁾

Věta 2.

Nechť $\small S(n)\geq log(n)$ . Pak

$NTIME(T(n)) \subseteq DSPACE(T(n))$
$NSPACE(S(n)) \subseteq DTIME(2^{OS(n)})$

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

Věta 3. Savitchova věta

$NSPACE(S(n)) \subseteq DSPACE(S((n)^2)$

Odůvodnění: Nedeterministický stroj o složitosti n lze simulovat deterministickým strojem, který bude potřebovat maximálně n² prostoru (což je pro nás obojí polynomické). Detailní důkaz viz slidy¹⁰⁾ nebo skripta

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

$NPSPACE = PSPACE$

Celková klasifikace:

$LOGSPACE \subseteq NLOGSPACE \subseteq P \subseteq NP \subseteq PSPACE = NPSPACE \subseteq EXPTIME$

$LOGSPACE \subset PSPACE$

$P \subset EXPTIME$

Polynomiální redukce

Pro lepší pochopení jsem redukci zařadil před np-úplné problémy.

Definice(11; 1.22) Polynomické redukce

Nechť $\small A, B \in \Sigma^*$ , Řekneme, že A se polynomicky redukuje na B, píšeme $\small A \leq_P B$ právě když $\small A \leq_m B$ a redukční funkce $\small f:\Sigma^*\rightarrow\Sigma^*$ , je vyčíslitelná TS M, který je časově omezen polynomem. (f je vyčíslitelná v polynomickém čase a taková, že pro každé $w \in \Sigma^*$ platí: $w \in A <=> f(w) \in B$ ¹¹⁾

Definici $\small \leq_m$ doufám naleznete 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

Lemma 12; 1.23 Transitivita redukce

Relace $\small \leq_P$ je reflexivní, transitivní, t.j. je kvaziuspořádání.

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

Definice 1.26 NP-těžká a NP-úplná úloha

Jazyk B je NP-úplný, jestliže:
1. $\small B \in NP$ 2. pro každý jazyk $\small A \in NP$ platí $\small A \leq_P B$ Pokud B splňuje pouze druhou podmínku, pak se nazývá NP-těžký.¹²⁾

Věta 23; 1.27

Jestliže B je NP-úplný a $\small B \in P$ , pak $\large P = NP$ (z definice)

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

Věta 1.29 Cook-Levin

SAT(problém splnitelnosti) je NP-úplný

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

FI:IB107 Vyčíslitelnost a složitost (podzim 2007), prof. RNDr. Luboš Brim, CSc.
FI:IA012 Složitost (jaro 2008), prof. RNDr. Ivana Černá, CSc. (pozn. magisterský předmět)

Použitá literatura

prof. RNDr. Luboš Brim, CSc., slidy přednášek (dostupné pouze z domény muni.cz)
prof. RNDr. Luboš Brim, CSc., staré nebo nové učební text (dostupné pouze z domény muni.cz)
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.

Je potřeba ještě zapracovat poznámky od Jitky Pospíšilové.

¹⁾

slidy Složitost výpočtů a problému, Přednáška č. 6 str 5, definice 1 a 2

²⁾

slidy Složitost výpočtů a problému, Přednáška č. 6 str 23 a 24, definice 8 a 9

³⁾

slidy Složitost výpočtů a problému, Přednáška č. 6 str 9 a 1, definice 3

⁴⁾

slidy Složitostní třídy, přednáška č. 7, str. 1

⁵⁾

slidy Složitostní třídy, přednáška č. 7, str. 14

⁶⁾

slidy Složitostní třídy, přednáška č. 7, str. 19

⁷⁾

slidy Složitostní třídy, přednáška č. 7, str. 20

⁸⁾

Slidy - vztahy mezi složitostními třídami, přednáška č.9 str 4,5

⁹⁾

Slidy - vztahy mezi složitostními třídami, přednáška č.9 str 6,7

¹⁰⁾

Slidy - vztahy mezi složitostními třídami, přednáška č.9 str 10-13

¹¹⁾

slidy Složitostní třídy, přednáška č. 7, str. 8

¹²⁾

skripta Složitost, str. 16