Složitost

Note	Složitost algoritmu versus složitost problému. Složitostní třídy (P, NP, PSPACE) a vztahy mezi nimi, příklady problémů z jednotlivých tříd. Těžkost a úplnost problému v dané třídě, polynomiální redukce problémů, NP-úplné úlohy. IB102/IB107

Problém má složitost toho nejlepšího algoritmu, který ho rozhoduje.

Časová složitost deterministického TS M: Je funkce $Time_{M} : N \to N$ , kde $Time_{M} (n)$ je největší počet kroků, které $M$ provede, přes všechny vstupy délky $n$ .
Časová složitost nedeterministického TS $M$: Je funkce $Time_{M} : N \to N$ , kde $Time_{M} (n)$ je délka nejdelší výpočetní cesty $M$ přes všechny vstupy délky $n$ .
Prostorová složitost deterministického TS $M$: Je funkce $Space_{M} : N \to N$ , kde $Space_{M} (n)$ je největší počet políček pásky čtených strojem $M$ přes všechny vstupy délky $n$ .
Prostorová složitost nedeterministického TS $M$: Je funkce $Space_{M} : N \to N$ , kde $Space_{M} (n)$ je největší počet políček pásky čtených strojem $N$ přes všechny vstupy délky $n$ a pro všechny výpočetní cesty.

Složitostní třídy

$TIME (f)$

Pro funkci $f : N \to N$ je $TIME (f) = {L ∣ existuje DTS M, kde L = L (M) \land Time_{M} \in O (f)}$

$NTIME (f)$

Pro funkci $f : N \to N$ je $NTIME (f) = {L ∣ existuje NTS M, kde L = L (M) \land Time_{M} \in O (f)}$

$SPACE (f)$

Pro funkci $f : N \to N$ je $SPACE (f) = {L ∣ existuje DTS M, kde L = L (M) \land Space_{M} \in O (f)}$

$NSPACE (f)$

Pro funkci $f : N \to N$ je $NSPACE (f) = {L ∣ existuje NTS M, kde L = L (M) \land Space_{M} \in O (f)}$

P

DTS s polynomiálním počtem kroků.

$⋃_{k \in N} TIME (n^{k})$

Příklady:

PATH — Existuje v daném orientovaném grafu $G$ cesta z $s$ do $t$ ?

NP

NTS s polynomiálním počtem kroků.

$⋃_{k \in N} NTIME (n^{k})$

Příklad: HAMPATH — Existuje v daném orientovaném grafu $G$ Hamiltonovská cesta z $s$ do $t$ (projde každým uzlem právě jednou)?

Příklady:

SAT — Je daná formule výrokové logiky splnitelná?
CLIQUE — Existuje úplný podgraf s $k$ vrcholy?
3SAT — Je daná výroková formule v KNF s nejvýše třemi literály na klauzuli splnitelná?
HAMCYCLE — Problém obchodního cestujícího, nejkratší kružnice, která prochazí všemi vrcholy.
K3COVER — Obarvitelnost grafu třemi barvami.
KNAPSACK — Najdi kombinaci zboží s nejvyšší hodnotou, která se vleze do váhového limitu.

PSPACE

DTS s polynomialním počtem políček na pásce.

$⋃_{k \in N} SPACE (n^{k})$

Příklady:

TQBF (QSAT) — Problém splnitelnosti výrokových formulí, kde proměnné jsou na začátku formule kvantifikovány $\forall$ nebo $\exists$ .

NPSPACE

NTS s polynomiálním počtem políček na pásce.

$⋃_{k \in N} NSPACE (n^{k})$

EXPTIME

DTS s exponenciálním počtem kroků.

$⋃_{k \in N} TIME (2^{n^{k}})$

Příklady: * Problém zastavení v nejvýše $k$ krocích.

NEXPTIME

NTS s exponenciálním počtem kroků.

$⋃_{k \in N} NTIME (2^{n^{k}})$

L

DTS s logaritmickým (ne lineárním) prostorovou složistostí (ne časovou).

NL

NTS s logaritmickým (ne lineárním) prostorovou složistostí (ne časovou).

Note	Ano, je to nekonzistentní a ano, je to na hovno.

Inkluze

L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE = NSPACE \subseteq EXPTIME

Platí $SPACE (f) \subseteq TIME (2^{O (f)})$: Přes maximální počet konfigurací DTS. Musí však platit $f \in Ω (lo g (n))$ .
Platí $NSPACE (f) \subseteq NTIME (2^{O (f)})$: Přes maximální počet konfigurací NTS. Musí však platit $f \in Ω (lo g (n))$ .
Platí $TIME (f) \subseteq SPACE (f)$: $SPACE (f)$ určitě uloží $TIME (f)$ konfigurací. Plyne z toho $P \subseteq PSPACE$ .
Platí $NTIME (f) \subseteq NSPACE (f)$: $NSPACE (f)$ určitě uloží $NTIME (f)$ konfigurací. Plyne z toho $NP \subseteq NPSPACE$ .
Savitchova věta: Platí $NSPACE (f) \subseteq SPACE (f^{2})$ , kde $f \in Ω (lo g (n))$ . Simuluje nedeterministické větvení, ale za cenu exponenciálního nárustu času, takže $NSPACE (f) \in TIME (2^{O (f)})$ .

Plyne z toho $PSPACE = NPSPACE$ , $NL \subseteq P$ a $NSPACE \subseteq EXPTIME$ .
PLatí $NTIME (f) \subseteq SPACE (f)$: Simuluj jednu větevv výpočtu NTS v paměti a backtrackuj. Musí však platit $f \in Ω (lo g (n))$ .

Plyne z toho $NP \subseteq PSPACE$ .

Polynomiální redukce

Převod mezi problémy je realizovatelný na DTS v polynomiálním čase.

Nechť $A \subseteq Σ^{*}$ a $B \subseteq Φ^{*}$ jsou jazyky. $A$ se polynomiálně redukuje na $B$ , píšeme $A \leq_{p} B$ , právě když existuje funkce $f : Σ^{*} \to Φ^{*}$ , pro kterou platí $(\forall a \in Σ^{*}) (a \in A ⟺ f (a) \in B)$ a která je totálně vyčíslitelná DTS v polynomiáním čase.

X-težký problém: Všechno ve složitostní třídě X se na něj redukuje.
X-úplný problém: Je X-těžký a navíc patří do X.

NP-úplné: HAMCYCLE, 3SAT, CLIQUE, K3COVER, KNAPSACK, …