mgr-szz:in-tei:2-tei

Obsah

Zadání
Vypracování
Předměty
Zdroje
Diskuze

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) $\Leftrightarrow$ 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) $\Leftrightarrow$ 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á $\Leftrightarrow \exists$ 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 $\Sigma$ .
$co-L = \Sigma^*\backslash L$

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

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 $\neq$ NP
co-NSPACE(S(n)) = NSPACE(S(n))

Uzavřenost

Deterministické složitostní třídy jsou uzavřené na $+, \cdot, \cap, \cup, co-$ 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)}

$P = DTIME (n^{O(1)}) = \bigcup_{k>0}{DTIME(n^k)}$

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

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

$NSPACE = NSPACE (n^{O(1)}) = \bigcup_{k>0}{NSPACE(n^k)}$

$LOGSPACE = DSPACE (log(n))$

$NLOGSPACE = NSPACE (log(n))$

$EXPTIME = DTIME (2^{n^{O(1)}})$

$NEXPTIME = NTIME (2^{n^{O(1)}})$

$EXPSPACE = DSPACE (2^{n^{O(1)}})$

$NEXPSPACE = NSPACE (2^{n^{O(1)}})$

$LOGSPACE \subseteq NLOGSPACE \subseteq P \subseteq NP \subseteq PSPACE = NSPACE \subseteq EXPTIME \subseteq NEXPTIME \subseteq EXPSPACE = NEXPSPACE$

$LOGSPACE, NLOGSPACE \subset PSPACE \subset NEXPSPACE$

$P \subset DEXPTIME$

$NP \subset NEXPTIME$

Vztahy mezi složitostními třídami

Lineární urychlení

Je možno dosáhnout konstantního zrychlení za cenu nárustu potřebné paměti.

Determinismus je speciálním případem nedeterminismu:

$DTIME(T(n)) \subseteq NTIME(T(n))$ $DSPACE(S(n)) \subseteq NSPACE(S(n))$

důsledek: $P \subseteq NP$

$NTIME(T(n)) \subseteq DTIME(2^{O(T(n))})$

Vztahy mezi časem a prostorem:

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

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

Idea důkazu pro 3. a 4.¹⁾:
DTS pracující v prostoru S(n) může být upraven tak, aby skončil po $2^{O(S(n))}$ krocích a přitom akceptoval stejný jazyk.

pro S(n) ≥ log(n) platí:

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

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ť $S(n) \geq log(n)$ $NSPACE(S(n)) \subseteq DSPACE(S(n)^2)$

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

$NSPACE(S(n)) = co-NSPACE(S(n))$

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 ( $x \notin A \Leftrightarrow \exists$ akceptující výpočet – akceptuje, když tam nepatří ):

Nedeterministicky uhádneme |A| řetězců
Pro každý zvolený řetězec $\alpha$ nedeterministicky ověříme, zda $\alpha \in A$ .
Pokud všechny zvolené řetězce patří do A a x není mezi nimi, platí $x \notin A$ .

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 $\exists$ jazyk $L \in DSPACE(S(n))$ takový, že $L \notin DSPACE (S'(n))$ 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 $\exists$ jazyk $L \in DTIME(T(n))$ takový, že $L \notin DTIME (T'(n))$ pro žádno funkci T'(n) takové, že $T'(n)log(T'(n)) \in o(T(n))$ .

NSPACE

pro nedeterministické složitostní třídy
Metoda padding
Věta: $NSPACE(n^3) \subset NSPACE(n^4)$

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, $A \leq_P B \Leftrightarrow$ existuje zobrazení $R:\Sigma_a^*\rightarrow\Sigma_b^*$ takové, že pro každý řetězec $w \in \Sigma^*: R(w) \in B \Leftrightarrow w \in A$ a R je polynomiálně vyčíslitelná.

Funkce $f:\Sigma^*\rightarrow\Sigma^*$ je polynomiálně vypočitatelná $\Leftrightarrow \exists$ 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 $A \leq_P B, B \in P$ , tak i $A \in P$ . (Problém A je právě tak složitý jako problém B, pokud B se dá redukovat na A)

Relace $A \leq_P B$ je reflexivní a transitivní (kvaziuspořádání).
1. reflexivita - libovolný problém dokážeme převést na ten stejný problém v polynomickém čase
2. 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 $\Leftrightarrow \forall$ jazyky $A \in C$ platí: $A \leq_P L$ (každý jazyk A z L se dá redukovat na C). Jestli navíc $L \in C$ , tak L nazýváme C-úplný(C těžký jazyk nemusí patřit do třídy C).

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

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 $\leq$ 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 $\leq$ HAM-PATH

TSP

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

SUBSET-SUM

3-SAT $\leq$ SUBSET-SUM

k-ZABARVENÍ GRAFU

- pro $k \geq 3$ - 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, $A \leq_{log} B \Leftrightarrow$ existuje zobrazení $R:\Sigma_a^*\rightarrow\Sigma_b^*$ takové, že pro každý řetězec $w \in \Sigma^*: R(w) \in B \Leftrightarrow w \in A$ a R je konstruovatelná v logaritmickém prostoru.

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

Jestli $A \leq_{log} B, B \in DLOG$ , tak i $A \in DLOG$ .

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

Zdroje

Complexity ZOO (especially Petting ZOO)

¹⁾

viz. Vyčíslitelnost a složitost slidy č.9. str.5