Složitost II

transcript

Složitost II

TIN063

Ondřej Čepek

Sylabus

1. Výpočetní model – DTS a NTS2. Časová a prostorová složitost výpočtu3. Technické pomůcky: lineární komprese, lineární

zrychlení a redukce počtu pásek 4. Časová (prostorová) konstruovatelnost funkcí a

vyčíslitelnost funkcí v lineárním čase (prostoru)5. Věty o deterministické časové a prostorové hierarchii6. Věty o vztazích mezi časovou a prostorovou složitostí7. Translační lemma a nedeterministické hierarchie8. Základní složitostní třídy a jejich vzájemné vztahy9. Orákulové TS a relativizované třídy10. Polynomiální hierarchie

Deterministický Turingův Stroj (DTS)

DTS je abstraktní stroj definovaný pěticí (Q, Σ, δ,q0,F), který se skládá z:

• řídící jednotky, která je v každém okamžiku v jednom ze stavů v konečné množině stavů Q, obsahující počáteční stav q0 a množinu přijímacích stavů F

• potenciálně nekonečné (jednosměrné) vstupní pásky (pouze pro čtení) a několika potenciálně nekonečných (jednosměrných) pracovních pásek, které sestávají z buněk, z nichž každá může obsahovat právě jeden symbol abecedy Σ

• hlav pro čtení (vstupní páska) a čtení a zápis (pracovní pásky), které se mohou po páskách pohybovat oběma směry (v on-line modelu po vstupní pásce pouze vpravo)

• programu, který je zadán přechodovou funkcí δ : Q Σk Q Σk-1 { , , }k, kde k je počet pásek (včetně vstupní), funkce není definována pro všechny vstupy

Konfigurace TS = stav řídící jednotky + pozice hlav na všech páskách (včetně vstupní) + obsah pracovních pásek (té jejich konečné části kde došlo od počátku výpočtu k nějakým změnám)

Počáteční konfigurace TS = stav q0 + všechny hlavy na počátečních pozicích + vstupní slovo na vstupní pásce a prázdná slova (prázdné symboly) na pracovních páskách

Displej TS = stav řídící jednotky + symboly (obsahy buněk) pod všemi hlavami

Krok TS = jedno použití přechodové funkce na základě aktuálního displeje, tj. změna stavu řídící jednotky, přepsání symbolů pod pracovními hlavami a posun všech hlav (lze i zůstat na místě)

Výpočet TS = posloupnost kroků TS začínající v počáteční konfiguraci

Zastavení TS = okamžik kdy přechodová funkce není pro daný displej definována (vždy platí pokud je řídící jednotka v přijímacím stavu)

Přijímající výpočet TS = výpočet TS, který zastaví v přijímacím stavu

Odmítající výpočet TS = výpočet TS, který zastaví v jiném než přijímacím stavu nebo výpočet, který nezastaví (nekonečný výpočet)

Přijímané slovo: Slovo w je přijímáno DTS M pokud výpočet M nad vstupním slovem w zastaví v přijímacím stavu.

Přijímaný jazyk: Jazyk L(M) přijímaný DTS M sestává ze všech slov přijímaných DTS M.

Akceptor x Transducer

Dosud popisovaný TS je tzv. akceptor. Pokud chceme, aby TS počítal funkci, tak z něj uděláme transducer přidáním výstupní pásky, která je pouze pro zápis, hlava se po ní pohybuje pouze vpravo a symbol pod hlavou neovlivňuje přechodovou funkci (nepatří do displeje). Transducer může v každém svém kroku zapsat na výstupní pásku 1 symbol.

Definičním oborem vyčíslované funkce je přijímaný jazyk daného TS a funkční hodnotou přiřazenou přijímanému vstupnímu slovu je obsah výstupní pásky v okamžiku zastavení.

Proč zrovna TS jako výpočetní model?

Přesná definice časové i prostorové složitosti výpočtu + Church-Turingova teze.

Prostorová složitost výpočtu DTS

Nechť M je DTS takový, že w Σ* takové, že |w| = n, použije M při práci nad vstupním slovem w nejvýše S(n) buněk na pracovních páskách (prostor zabraný vstupním slovem na vstupní pásce se nepočítá). Potom říkáme, že M má prostorovou složitost S(n).

Deterministická prostorová složitost jazyka

Jazyk L má deterministickou prostorovou složitost S(n) pokud existuje DTS M s prostorovou složitostí S(n), který rozpoznává L, tj. takový že L(M) = L.

Časová složitost výpočtu DTS

Nechť M je DTS takový, že w Σ* takové, že |w| = n, udělá M při práci nad vstupním slovem w nejvýše T(n) kroků než zastaví. Potom říkáme, že M má časovou složitost T(n)

Deterministická časová složitost jazyka

Jazyk L má deterministickou časovou složitost T(n) pokud existuje DTS M s časovou složitostí T(n), který rozpoznává L, tj. takový že L(M) = L.

Deterministické třídy časové a prostorové složitosti

DSPACE(S(n)) = {L | L má deterministickou prostorovou složitost S(n)}

DTIME(T(n)) = {L | L má deterministickou časovou složitost T(n)}

Nedeterministický Turingův Stroj (NTS)

Všechny definice stejné jako pro DTS kromě přechodové funkce δ, která je nahrazena tabulkou δ, která přiřazuje každému displeji z množiny Q Σk množinu možných pokračování, tj. množinu z potenční množiny P(Q Σk-1 { , , }k).

Definice: NTS M přijímá vstup x Σ* tehdy a jen tehdy když existuje přijímající výpočet NTS M na vstupu x (výpočet končící v qy). Jazyk L(M) přijímaný NTS M sestává ze všech vstupních slov přijímaných NTS M.

Poznámka: Zatímco u DTS odpovídá jednomu vstupu jeden výpočet, u NTS odpovídá jednomu vstupu strom možných výpočtů (a vstup je přijat když alespoň jedna větev výpočtu končí v přijímající konfiguraci NTS)

Alternativní definice NTS: přidáme tzv. hádací pásku. Práce NTS pak sestává ze 2 fází:

1) Na hádací pásku je (nedeterministicky) zapsán řetězec y {1, … ,k}*, kde k je maximální počet možných pokračování pro nějaký displej v tabulce δ.

2) Pomocí y je výpočet na vstupu x změněn z nedeterministického na deterministický. Vstup x je přijat pokud existuje (certifikát) y kódující přijímající výpočet.

Poznámka: Řetězec (certifikát) na hádací pásce je vlastně kód nějaké větve výpočtu ve stromu možných výpočtů. Platný certifikát je pak kód větve výpočtu, která končí v přijímající konfiguraci. Vstup je přijímán daným DTS pokud pro něj existuje platný certifikát.

Prostorová složitost výpočtu NTS

Nechť M je NTS takový, že w Σ* takové, že |w| = n, použije M při práci nad vstupním slovem w nejvýše S(n) buněk na pracovních páskách (při jakémkoli z možných výpočtů M nad vstupem w). Potom říkáme, že M má prostorovou složitost S(n).

Nedeterministická prostorová složitost jazyka

Jazyk L má nedeterministickou prostorovou složitost S(n) pokud existuje NTS M s prostorovou složitostí S(n), který rozpoznává L, tj. takový že L(M) = L.

Časová složitost výpočtu NTS

Nechť M je NTS takový, že w Σ* takové, že |w| = n, udělá M při práci nad vstupním slovem w nejvýše T(n) kroků než zastaví (při jakémkoli z možných výpočtů M nad vstupem w). Potom říkáme, že M má časovou složitost T(n).

Nedeterministická časová složitost jazyka

Jazyk L má nedeterministickou časovou složitost T(n) pokud existuje NTS M s časovou složitostí T(n), který rozpoznává L, tj. takový že L(M) = L.

Nedeterministické třídy časové a prostorové složitosti

NSPACE(S(n)) = {L | L má nedeterministickou prostorovou složitost S(n)}

NTIME(T(n)) = {L | L má nedeterministickou časovou složitost T(n)}

Triviální vztahy

funkci S(n) : DSPACE(S(n)) NSPACE(S(n))

funkci T(n) : DTIME(T(n)) NTIME(T(n))

Pokud n: S1(n) ≤ S2(n) pak DSPACE(S1(n)) DSPACE(S2(n))

Pokud n: S1(n) ≤ S2(n) pak NSPACE(S1(n)) NSPACE(S2(n))

Pokud n: T1(n) ≤ T2(n) pak DTIME (T1(n)) DTIME (T2(n))

Pokud n: T1(n) ≤ T2(n) pak NTIME (T1(n)) NTIME (T2(n))

Zpracování výjimek

Pomocí přidání nových stavů řídící jednotky TS se lze jednoduše „postarat“ o libovolnou konečnou množinu „výjimečných vstupů“.

1. Zkonstruujeme konečný automat rozpoznávající danou množinu vstupů

2. TS napřed simuluje tento konečný automat (TS při tom nepoužívá pracovní pásky). Pokud je na vstupu jedno z hledaných slov (výjimek) tak se simulace zastaví (a TS přijme nebo odmítne podle druhu výjimky). Pokud na vstupu není žádné z hledaných slov (což TS zjistí nejpozději po přečtení tolika vstupních symbolů ze vstupní pásky kolik jich je v nejdelší výjimce), tak TS odjede hlavou na začátek vstupní pásky a spustí „normální“ výpočet (simuluje původní TS). Zpracováním výjimek se k výpočtu přidá konstantní čas (počet kroků) a nulový pracovní prostor.

Věta (o lineární prostorové kompresi)

Nechť je jazyk L přijímán (k+1)-páskovým DTS M (1 vstupní a k pracovních pásek), který má prostorovou složitost S(n). Potom rN+ existuje (k+1)-páskový DTS M’, který má prostorovou složitost S(n) / r a přijímá jazyk L.

Důsledek: (Ekvivalentní formulace) rN+ : DSPACE(S(n)) = DSPACE(S(n) / r )

Poznámka: Analogicky platí rN+ : NSPACE(S(n)) = NSPACE(S(n) / r ), důkaz projde beze změny i pro nedeterministický případ.

Věta (redukce počtu pásek pro prostorovou složitost)

Nechť je jazyk L přijímán (k+1)-páskovým DTS M (1 vstupní a k pracovních pásek), který má prostorovou složitost S(n). Potom existuje DTS M’ s 1 pracovní páskou, který má prostorovou složitost S(n) a přijímá jazyk L.

Poznámka: Důkaz lze upravit i pro NTS.

Definice: Nechť f(n) je funkce v proměnné n. Pak infnf(n) je limita pro n největší dolní meze posloupnosti f(n), f(n+1), f(n+2), …

Věta (o lineárním zrychlení – část 1)

Nechť je jazyk L přijímán k-páskovým DTS M (1 vstupní a k-1 pracovních pásek), který má časovou složitost T(n) a nechť infn(T(n) / n) = . Potom c>0 existuje DTS M’ s k pracovními páskami, který má časovou složitost cT(n) a přijímá jazyk L.

Poznámka: Postačující podmínka: T(n) ω(n) implikuje infn(T(n) / n) = .

Důsledek: Pokud infn(T(n) / n) = pak c>0 : DTIME(T(n)) = DTIME(cT(n) ).

Věta (o lineárním zrychlení – část 2)

Nechť je jazyk L přijímán k-páskovým DTS M (1 vstupní a k-1 pracovních pásek), který má časovou složitost T(n) = cn, kde c>1. Potom >0 existuje DTS M’ s k pracovními páskami, který má časovou složitost (1+)n a přijímá jazyk L.

Důsledek: Pokud T(n) = cn, kde c>1, pak >0 : DTIME(T(n)) = DTIME((1+)n ).

Věta (o lineárním zrychlení – NTS verze)

Pokud infn(T(n) / n) = pak c>0 : NTIME(T(n)) = NTIME(cT(n) ). Pokud T(n) = cn, kde c>1, pak >0 : NTIME(T(n)) = NTIME((1+)n ).

Věta (redukce počtu pásek pro časovou složitost – kvadratická verze)

Mějme jazyk L DTIME(T(n)) a nechť buď infn(T(n) / n) = nebo T(n) = cn, kde c>1. Potom existuje DTS M s 1 pracovní páskou, který má časovou složitost T2(n) a přijímá jazyk L.

Poznámka: Důkaz lze upravit i pro NTS.

Věta (redukce počtu pásek pro časovou složitost – logaritmická verze)

Mějme jazyk L DTIME(T(n)). Potom existuje DTS M s 2 pracovními páskami, který má časovou složitost T(n)·log2T(n) a přijímá jazyk L.

Poznámka: Důkaz lze opět upravit i pro NTS.

Konstruovatelnost funkcí

Definice: Funkce f : N N je rekurzivní tehdy a jen tehdy, když existuje DTS transducer s jednoprvkovou vstupní abecedou takový, že pro vstup 1n (n znaků na vstupní pásce). dává výstup 1f(n) (f(n) znaků na výstupní pásce).

Definice: Funkce f : N N je vyčíslitelná v lineárním čase tehdy a jen tehdy, když je rekurzivní a existuje konstanta c a DTS transducer s jednoprvkovou vstupní abecedou takový, že na vstupu 1n udělá nejvýše cf(n) kroků než vydá výstup 1f(n).

Definice: Funkce f : N N je vyčíslitelná v lineárním prostoru tehdy a jen tehdy, když je rekurzivní a existuje konstanta c a DTS transducer s jednoprvkovou vstupní abecedou takový, že na vstupu 1n použije nejvýše cf(n) buněk na pracovních páskách než vydá výstup 1f(n).

Definice: Funkce f : N N je časově konstruovatelná tehdy a jen tehdy, když existuje DTS takový, že pro každý vstup délky n zastaví po právě f(n) krocích.

Definice: Funkce f : N N je prostorově konstruovatelná tehdy a jen tehdy, když existuje DTS takový, že pro každý vstup délky n použije (označí) právě f(n) buněk na pracovních páskách než zastaví.

Poznámka: Pro příslušný DTS v předchozích dvou definicích lze opět předpokládat, že má jednoprvkovou vstupní abecedu (o výstupu rozhoduje pouze délka vstupu a ne jeho konkrétní obsah).

Lemma: Nechť f1 : N N a f2 : N N jsou funkce takové, že f1 + f2 a f2 jsou časově konstruovatelné a navíc platí >0 n0 n ≥ n0 : f1(n) ≥ f2(n) + (1+)n. Potom je také funkce f1 časově konstruovatelná.

Věta: Nechť f : N N je funkce taková, že >0 n0 n ≥ n0 : f(n) ≥ (1+)n. Potom platí

f je časově konstruovatelná f je vyčíslitelná v lineárním čase

Věta: Nechť f : N N je funkce. Potom platí

f je prostorově konstruovatelná f je vyčíslitelná v lineárním prostoru

Důsledek: Každá časově konstruovatelná funkce f taková, že splňuje výše uvedenou podmínku >0 n0 n ≥ n0 : f(n) ≥ (1+)n, je také prostorově konstruovatelná.

Lemma (o prostorové složitosti univerzálního TS)

Nechť x je kód (Gödelovo číslo) DTS M s jednou vstupní a jednou pracovní páskou pracujícího v prostoru S(n), který má vstupní abecedu {0,1} a pracovní abecedu s t symboly. Pak lze práci M na datech y odsimulovat na univerzálním DTS s jednou pracovní páskou (a jednou vstupní páskou, na které je vstup (x,y)) v prostoru

max { log2t S(|y|), |x| }

Věta (o deterministické prostorové hierarchii)

Nechť S1 : N N a S2 : N N jsou funkce takové, že S1o(S2), S2 je prostorově konstruovatelná a S1(n) ≥ log2n. Potom existuje jazyk L pro který platí

L DSPACE(S2(n)) \ DSPACE(S1(n))

Lemma (o časové složitosti univerzálního TS)

Nechť x je kód (Gödelovo číslo) DTS M s jednou vstupní a dvěma pracovními páskami pracujícího v čase T(n), který má vstupní abecedu {0,1} a pracovní abecedu s t symboly. Pak lze práci M na datech y odsimulovat na univerzálním DTS se čtyřmi pracovními páskami (a jednou vstupní páskou, na které je vstup (x,y)) v čase 5 |x| T(|y|).

Věta (o deterministické časové hierarchii)

Nechť T1 : N N a T2 : N N jsou funkce takové, že T1 log2 T1 o(T2) a T2 je časově konstruovatelná. Potom existuje jazyk L pro který platí

L DTIME(T2(n)) \ DTIME(T1(n))

Věta (o vztazích mezi třídami časové a prostorové složitosti)

Nechť f : N N je funkce. Potom platí

a) NTIME(f(n)) DSPACE(f(n))

b) LNSPACE(f(n)), f(n) ≥ log2n cL: LDTIME(cLf(n))

Poznámka: Část b) předchozí věty neimplikuje inkluzi NSPACE(f(n)) DTIME(cf(n)).

Věta (Savičova)

Nechť S : N N je prostorově konstruovatelná funkce taková, že S(n) ≥ log2n. Potom

NSPACE(S(n)) DSPACE(S2(n)).

Lemma (translační)

Nechť S1(n), S2(n) a f(n) jsou prostorově konstruovatelné funkce takové, že S2(n) ≥ n a f(n) ≥ n. Potom

NSPACE(S1(n)) NSPACE(S2(n)) NSPACE(S1(f(n))) NSPACE(S2(f(n))).

Poznámka: Translační lemma platí i pro DSPACE (stejný důkaz jako pro NSPACE) a pro DTIME a NTIME (jiný, komplikovanější důkaz, jiné předpoklady)

Věta (o nedeterministické prostorové hierarchii – omezená verze pro polynomy)

Nechť ε > 0 a r ≥ 1. Potom existuje jazyk L pro který platí

L NSPACE(nr+ε) \ NSPACE(nr)

Definice: Tvrzení parametrizované číslem n N je pravdivé

• skoro všude tehdy a jen tehdy když je nepravdivé pro konečně mnoho n

• nekonečně často tehdy a jen tehdy když je pravdivé pro nekonečně mnoho n

Lemma (pomocné č.1) Nechť je jazyk L přijímán DTS M s prostorovou složitostí S(n) skoro všude. Potom existuje DTS M’ přijímající L s prostorovou složitostí S(n) (všude).

Lemma (pomocné č.2) Nechť je dán DTS M, délka vstupu n a číslo m N. Potom existuje DTS M’ zjišťující, zda m je maximální počet použitých buněk na pracovních páskách při práci M na vstupech délky n. Výpočet M’ vždy skončí a odpoví ANO/NE.

Věta (Borodinova o mezerách) Nechť g(n) ≥ n je rekurzivní funkce. Potom existuje rostoucí rekurzivní funkce S(n) taková, že DSPACE(S(n)) = DSPACE(g(S(n))).

Poznámka: Platí i verze pro NSPACE, DTIME a NTIME.

Základní třídy prostorové a časové složitosti

Prostor Čas

LOGLOG = DSPACE(log n) PP = c≥0 DTIME(nc)

NLOGNLOG = NSPACE(log n) NPNP = c≥0 NTIME(nc)

POLYLOGPOLYLOG = c≥0 DSPACE(logcn) DEXTDEXT = c≥0 DTIME(2cn)

PSPACEPSPACE = c≥0 DSPACE(nc) NEXTNEXT = c≥0 NTIME(2cn)

NPSPACENPSPACE = c≥0 NSPACE(nc) EXPTIMEEXPTIME = c≥0 DTIME(2(nc))

EXPSPACEEXPSPACE = c≥0 DSPACE(2cn) NEXPTIMENEXPTIME = c≥0 NTIME(2(nc))

Věta NLOGNLOG PP

PSPACEPSPACE = NPSPACENPSPACE

NPNP PSPACEPSPACE

PSPACE PSPACE EXPTIMEEXPTIME

NLOGNLOG PSPACEPSPACE EXPSPACEEXPSPACE

PP DEXTDEXT EXPTIMEEXPTIME

Turingovy stroje s orákulem

Definice: DTS M s orákulem A, kde A je jazyk, se liší od „obyčejného“ DTS takto:

• M má navíc tzv. dotazovací pracovní pásku (na které používá abecedu jazyka A). Prostor zabraný během výpočtu na této pásce se počítá do prostorové složitosti M.

• M má navíc 3 stavy řídící jednotky: DOTAZ, ANO, NE

• Pokud během práce M dojde k přechodu do stavu DOTAZ, tak v následujícím kroku M buď přejde do stavu ANO pokud aktuální obsah dotazovací pásky je slovo z jazyka A nebo přejde do stavu NE pokud aktuální obsah dotazovací pásky není slovo z jazyka A a navíc v obou případech následně vymaže (naráz) celý obsah dotazovací pásky. Jazyk slov přijímaných DTS M s orákulem A značíme L(M,A).

Poznámka: DTS bez orákula lze chápat (z hlediska vzájemné simulovatelnosti) jako DTS s prázdným orákulem (tj. s A = ).

Poznámka: Výpočty DTS s orákulem pro různé jazyky orákula tvoří (stejně jako výpočty NTS bez orákula) strom možných výpočtů (větvících se v konfiguracích, kde je řídící jednotka ve stavu dotaz). NTS a DTS s orákulem ale nemají stejnou výpočetní sílu.

Definice: NTS M s orákulem A, kde A je jazyk, se liší od „obyčejného“ NTS zcela stejně jako DTS s orákulem od obyčejného DTS (jak je definováno výše).

Turingovská převoditelnost a relativizované třídy

Definice: Nechť A a B jsou jazyky. Řekneme, že jazyk A je (deterministicky) Turingovsky převoditelný na jazyk B v polynomiální čase, pokud existuje DTS M s orákulem pracující v polynomiálním čase takový, že A = L(M,B). Tento fakt značíme A ≤T B.

Poznámka: Slova „v polynomiálním čase“ budeme u Turingovské převoditelnosti často vynechávat.

Příklad: Když A PP, tak A ≤T (když A PP, tak lze A rozpoznávat na DTS bez orákula).

Definice: Nechť B je jazyk. Potom P(B) = { A | A ≤T B }. Nechť CC je třída jazyků. Potom P(CC) = { A | B CC : A ≤T B }.

Příklad: P(PP) = PP

Definice: Nechť A a B jsou jazyky. Řekneme, že A je nedeterministicky Turingovsky převoditelný na B v polynomiální čase, pokud existuje NTS M s orákulem pracující v polynomiálním čase takový, že A = L(M,B). Tento fakt značíme A ≤NP B.

Definice: Nechť B je jazyk. Potom NP(B) = { A | A ≤NP B }. Nechť CC je třída jazyků. Potom NP(CC) = { A | B CC : A ≤NP B }.

Poznámka: Obdobné definice lze udělat také pro PSPACE(B), LOG(B), DEXT(B), … i pro PSPACE(CC), LOG(CC), DEXT(CC), … Například třída PSPACE(B) je třída jazyků rozpoznatelných pomocí DTS s orákulem B, pracujícím v polynomiálním prostoru.

Platí: Inkluze mezi „obyčejnými“ (nerelativizovanými) třídami se přímo přenášejí i na relativizované třídy. Například pro každý jazyk B platí, že

P(B) NP(B) PSPACE(B)

a tím pádem pro každou třídu jazyků CC platí, že

P(CC) NP(CC) PSPACE(CC)

Příklad: NP(PP) = NPNP

Otázka: Čemu se rovná NP(NPNP) ??

Polynomiální hierarchie

Definice (zjednodušená verze PH)

Definujme třídy jazyků 0, 1, 2, … startovní podmínkou 0 =PP a rekurzivním předpisem k ≥ 0 : k+1 = NP(k). Potom polynomiální hierarchií rozumíme třídu PHPH = k ≥0 k.

Platí: 0 = P P , 1 = NP(PP) = NPNP, 2 = NP(NPNP), …

Poznámka: Pokud PP =NPNP, tak k ≥ 0 : k = PP a tím pádem PHPH = PP (hierarchie kolabuje).

Věta PH PH PSPACE PSPACE.

Poznámka: Pokud PHPH nekolabuje, tak je „jemnějším dělením“ mezi PP a PSPACEPSPACE.

Definice: Nechť A je jazyk nad abecedou . Pak co-A = { x * | x A } je doplněk A. Nechť CC je třída jazyků. Pak co-CC = { co-A | A CC } je doplněk CC.

Definice (úplný popis PH)

Polynomiální hierarchie sestává z k, k a k pro k ≥ 0 kde:

• 0 = 0 = 0 = P P

• k ≥ 0 : k+1 = NP(k)

• k ≥ 0 : k+1 = co-NP(k)

• k ≥ 0 : k+1 = P(k)

Nyní PHPH = k ≥0 k = k ≥0 k = k ≥0 k (ekvivalence definic plyne z následující věty).

Věta: Následující vztahy platí k ≥ 0 (pokud jsou parametrizovány číslem k): 1 = NPNP, 1 = co-NPNP, 1 = PP

k = co-k (a tím pádem k = co-k)

k+1 = NP(k)

k+1 = P(k )

k+1 = co-NP(k)

k+1 = NP(k+1)

k+1 = co-NP(k+1)

k = co-k

k = P(k)

k k k+1

• pokud k k (nebo k k) tak k = k

Polynomiální hierarchie a alternující kvantifikátory

Definice:

• p(n) x : R(x) znamená x : (|x| p(n)) (x má vlastnost R)

• Nechť CC je třída jazyků. Pak CC je třída jazyků, kde ACC pokud platí

BC C polynom p : xA p(|x|) y : (x,y)B

• Nechť CC je třída jazyků. Pak CC je třída jazyků, kde ACC pokud platí

BC C polynom p : xA p(|x|) y : (x,y)B

Definice: Třída CC je uzavřena na zdvojování pokud ACC platí, že B={(x,y) | xA }CC.

Lemma 1: Nechť CC je libovolná třída jazyků. Pak ACC co-Aco-CC (ekvivalentně co-CC =co-CC ). Pokud je navíc CC je uzavřena na zdvojování, tak C C CC a C C CC.

Definice: Nechť A je libovolný jazyk. Pak je jazyk A* definován následujícím předpisem

A* = { x | n y1A … ynA : x=(y1, … ,yn) }

Lemma 2: Nechť CC je libovolná třída jazyků z polynomiální hierarchie (tedy k nebo k

nebo k pro nějaké k). Pak pro libovolný jazyk A platí ACC A*CC.

Věta:PP=NPNPPP=co-NPNPk>0: k=k

k>0: k=k

k≥0: k=k+1

Důsledek 1 (definice PH pomocí alternujících kvantifikátorů)

a)Ak tehdy a jen tehdy když existují BPP a polynom p takové, že

xA p(|x|) y1 p(|x|) y2 … : (x,y1,y2, … ,yk)B

a)Ak tehdy a jen tehdy když existují BPP a polynom p takové, že

xA p(|x|) y1 p(|x|) y2 … : (x,y1,y2, … ,yk)B

Důsledek 2 (kolaps PH na k-té úrovni)

Pokud pro nějaké k>0 platí k=k pak j≥0: k+j=k+j=k.

Důsledek 3 Buď k≥0: kk+1 nebo se polynomiální hierarchie skládá z konečně mnoha různých tříd k.

Důsledek 4 Pokud existuje k takové že PP=0k pak platí PPNPNP.

Převoditelnost a úplnost jazyků

Definice Poly-time transducer je DTS transducer, který na vstupu velikosti n zastaví po nejvýše p(n) krocích, kde p je (nějaký) polynom. Log-space transducer je DTS transducer, který na každém vstupu zastaví a na vstupu velikosti n použije nejvýše log n buněk na pracovních páskách (vstup ani výstup se do pracovního prostoru nepočítají).

Definice Jazyk L’ je převoditelný na jazyk L v polynomiálním čase, pokud existuje poly-time transducer takový, že pro vstup x zkonstruuje výstup y a platí xL’ yL. Jazyk L’ je převoditelný na jazyk L v logaritmickém prostoru, pokud existuje log-space transducer takový, že pro vstup x zkonstruuje výstup y a platí xL’ yL.

Definice Nechť CC je třída jazyků. Jazyk L je úplný pro třídu CC vzhledem k převoditelnosti v polynomiálním čase (resp. logaritmickém prostoru), pokud LCC a L’CC platí, že L’ je v polynomiálním čase (resp. logaritmickém prostoru) převoditelný na L (obdobně lze definovat úplnost vzhledem k dalším typům převoditelností).

Definice Jazyk L je PP–úplný L je úplný pro třídu PP vzhledem k převoditelnosti v logaritmickém prostoru.

Definice Jazyk L je NPNP–úplný L je úplný pro třídu NPNP vzhledem k převoditelnosti v polynomiálním čase.

Definice Jazyk L je PSPACEPSPACE–úplný L je úplný pro třídu PSPACEPSPACE vzhledem k převoditelnosti v polynomiálním čase.

Poznámka Pokud bychom definovali: jazyk L je PP–úplný L je úplný pro třídu PP vzhledem k převoditelnosti v polynomiálním čase, tak každý jazyk ve třídě PP kromě jazyků a * je PP–úplný.

Věta Nechť L je PP–úplný. Pak pokud L LOG = DSPACE(log n), tak platí PP = LOG.

Věta Nechť L je PSPACEPSPACE–úplný. Pak pokud L k, tak platí PHPH = k, tedy polynomiální hierarchie kolabuje do třídy k = k.

Důsledek Pokud existuje PSPACEPSPACE–úplný jazyk, tak pokud PHPH = PSPACEPSPACE, tak existuje k takové, že PHPH = k = k, tedy polynomiální hierarchie kolabuje do třídy k.

Kvantifikované Booleovské Formule (QBF)

1.Pokud je x Booleovská proměnná, tak x je QBF (a x je v této QBF volná proměnná)

2.Pokud E a E’ jsou QBF, tak (E), (E)(E’) a (E)(E’) jsou QBF a výskyty proměnných jsou volné či vázané podle toho jaké jsou v E a E’.

3.Pokud je E QBF, tak x (E) a x (E) jsou QBF. Rozsahem kvantifikátoru jsou všechny volné výskyty proměnné x v E a tyto výskyty se stávají vázanými (status výskytů ostatních proměnných se nemění).

Pozorování QBF bez volných proměnných nabývá hodnoty true nebo false. Lze tedy definovat následující rozhodovací problém (QBF problém):

Vstup: QBF bez volných proměnných.

Otázka: Má daná QBF hodnotu true?

Věta QBF problém je PSPACEPSPACE–úplný (jazyk kladných instancí QBF problému je PSPACEPSPACE–úplný).

Věta (Ladnerova) Pokud jsou třídy PP a NPNP různé (tedy pokud PP NPNP), tak existuje jazyk A takový, že ANPNP \ P P a zároveň A není NPNP–úplný.

Složitost II

Documents