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)

  1. DTIME(T(n)) \subseteq DSPACE(T(n))
  2. NTIME(T(n)) \subseteq NSPACE(T(n))
  3. DSPACE(S(n)) \subseteq DTIME(2^{O(S(n))})
  4. NSPACE(S(n)) \subseteq NTIME(2^{O(S(n))})

Idea důkazu pro 3. a 4.1):
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ří ):
  1. Nedeterministicky uhádneme |A| řetězců
  2. Pro každý zvolený řetězec \alpha nedeterministicky ověříme, zda \alpha \in A.
  3. 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

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

Diskuze

, 2013/06/11 21:49

Pekný základný prehľad. Osobne mi tam ešte chýba (v prípade potreby si asi každý doplňte sám):

- Oráklové TS a polynomiálna hierarchia
- Alternujúce TS a ich zložitostné triedy
- Pravdepodobnostné TS a triedy RP, BPP (ktoré mne osobne prídu hodne zaujímavé, dôležité a ľahko predstaviteľné)
- (?)Kvantové zložitostné triedy(?)


You could leave a comment if you were logged in.
mgr-szz/in-tei/2-tei.txt · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)
Nahoru
CC Attribution-Noncommercial-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0