Domáce úlohy

Prednášky

Prehľad

P

Problémy riešiteľné deterministicky v polynomiálnom čase, napr. na Turingovom stroji, alebo na RAM. Tiež problémy riešiteľné (logspace) uniformnými obvodmi polynomiálnej veľkosti. P = AL, teda sú to tiež problémy riešiteľné v logaritmickom priestore alternujúcim TS.

Problémy CVS (circuit value problem – vyhodnotiť daný boolovský obvod) či LP (lineárne programovanie) sú P-úplné (pri logspace redukcii).

NP a coNP

NP sú problémy riešiteľné nedeterministicky v polynomiálnom čase. Ekvivalentne, sú to také problémy, že ak nám niekto povie riešenie, vieme ho efektívne overiť. Problémy v NP majú pravdepodobnostne overiteľné dôkazy, NP = PCP[O(log n),O(1)]. coNP tvoria komplementy jazykov v NP.

NP-úplné sú napr. SAT, ILP (celočíselné lineárne programovanie), CLIQUE, VERTEX-COVER, HAMILTON-CIRCUIT, 3-COLORING. Zistiť, či je daná formula tautológia, je coNP-úplný problém.

PSPACE

Problémy riešiteľné v polynomiálnom priestore, napr. na TS alebo RAM. Podľa Savitchovej vety je PSPACE = NPSPACE (nedeterministický polynomiálny priestor). Podľa Immerman-Szelepcsényiho vety je priestor uzavretý na komplement, teda PSPACE = coPSPACE. Ďalšia charakterizácia je PSPACE = AP – sú to práve problémy riešiteľné v polynomiálnom čase alternujúcim TS; a PSPACE = IP (interaktívne dokazovacie systémy).

PSPACE-úplné sú QBF (quantified boolean formula), GEOGRAPHY, Sokoban, Reversi, ekvivalencia regulárnych výrazov, atď.

EXP a NEXP

EXP sú problémy riešiteľné v exponenciálnom čase (t.j. O(2^poly(n))). EXP = APSPACE – polynomiálny priestor + alternácie. NEXP to isté nedeterministicky. NEXP sú problémy, ktoré majú interaktívne dokazovacie systémy s aspoň dvoma provermi, NEXP = MIP, resp. pravdepodobnostne overiteľné dôkazy, NEXP = PCP[poly(n),poly(n)] = PCP[poly(n),O(1)].

Hry ako dáma, šach (zovšeobecnený), či Go (s japonským pravidlom ko) sa ukázali ako EXP-úplné. Rôzne varianty NP-úplných problémov, kde vstup zapíšeme úsporne sú NEXP-úplné, napr. úsporný 3SAT: na vstupe je obvod, ktorý kóduje exponenciálne dlhú formulu – je splniteľná?

PH

Polynomiálna hierarchia je hierarchia tried medzi P a PSPACE. P = Σ^P₀ ⊆ NP = Σ^P₁ ⊆ Σ^P₂ ⊆ ... ⊆ PH ⊆ PSPACE, resp. P = Π^P₀ ⊆ coNP = Π^P₁ ⊆ Π^P₂ ⊆ ... ⊆ PH ⊆ PSPACE. Definovať k-ty stupeň hierarchie môžeme cez alternujúce TS, ktoré iba (k-1)-krát alternujú alebo cez TS s orákulom: Σ^P_k+1 = NP ^ΣP_k alebo cez polynomiálne relácie: L ∈ Σ^P_k, ak y∈L práve vtedy, keď ∃x₁∀x₂...(∃/∀)x_k R(y,x₁,...,x_k). Π^P_k+1 = coNP^ΠP_k = co-Σ^P_k+1.

Hoci PH samotná asi nemá úplné problémy (inak skolabuje), na každej úrovni je úplný problém zistiť, či je kvantifikovaná formula s k kvantifikátormi pravdivá.

P/poly

Neuniformné triedy obvodov polynomiálnej veľkosti. Pre každú veľkosť vstupu máme iný obvod. Ekvivalentná definícia je cez TS, ktorým pre každú veľkosť vstupu môžeme dať "radu" polynomálnej veľkosti. Rada závisí iba od dĺžky vstupu, nie od vstupu samotného.

P/poly je trochu čudná trieda v tom, že obsahuje aj nerozhodnuteľné jazyky (odpovede môžeme zadrátovať do obvodu vďaka neuniformnosti). Avšak veríme, že ani neuniformné polynomiálne obvody nedokážu riešiť SAT (inak skolabuje PH). BPP ⊆ P/poly.

AC a NC

NC zachytáva pojem "efektívne paralelné algoritmy". NC je trieda problémov, ktoré sa dajú na PRAM riešiť paralelne v polylogaritmickom čase s polynomiálnym počtom procesorov. Ekvivalentná definícia cez obvody: NC = AC sú problémy riešiteľné (uniformnými) obvodmi (s AND/OR/NOT) polynomiálnej veľkosti a polylogaritmickej hĺbky. Obvody v NC majú AND/OR hradlá s dvoma vstupmi, v AC môžu mať neobmedzene veľa vstupov. Pre AC a NC môžeme zadefinovať hierarchie, pričom na k-tej úrovni povolíme obvody hĺbky O(log^k n). Zrejme AC⁰ ⊆ NC¹ ⊆ AC¹ ⊆ NC² ⊆ AC² ⊆ ... Podľa Barringtonovej vety NC¹ sú práve problémy riešiteľné vetviacimi programmi šírky 5. Vieme, že AC⁰ ≠ NC¹, predpokladá, sa že hierarchia je striktná celá, ale je to otvorený problém.

AC⁰ obsahuje napr. neregulárny jazyk aⁿbⁿ, sčítanie celých čísel, násobenie boolovských matíc, ale nedokáže spočítať paritu (regulárny jazyk!), či majoritu (je na vstupe viac 0 alebo 1?). NC¹ obsahuje všetky regulárne jazyky, súčin celých čísel, AC¹ vie počítať tranzitívny uzáver matice a teda napr. či v danom grafe existuje cesta medzi dvoma vrcholmi. AC¹ vie rozoznávať všetky bezkontextové jazyky.

L a NL

Deterministický, resp. nedeterministický logaritmický priestor. NL = coNL. NC¹⊆ L ⊆ NL = coNL ⊆ AC¹.

Hľadanie cesty v orientovanom grafe je NL-úplný problém. Úloha sa pre neorientované grafy dá riešiť deterministicky v L (ťažký výsledok založený na derandomizovaní náhodnej prechádzky po grafe).

BPP

Problémy riešiteľné efektívnymi pravdepodobnostnými algoritmami, ktoré sa môžu pomýliť (jedným aj druhým smerom) s pravdepodobnosťou 1/3 (dá sa zlepšiť na exponenciálne malú pravdepodobnosť). BPP ⊆ P/poly a zároveň BPP ⊆ Σ^P₂. Predpokladá sa, že P = BPP, teda každý BPP problém sa dá efektívne derandomizovať (otvorený problém).

O známom probléme testovania prvočíselnosti sa nakoniec ukázalo, že sa dá riešiť deterministicky v polynomiálnom čase (hoci v praxi sa dodnes používajú rýchlejšie pravdepodobnostné algoritmy). Problém testovania, či sa dva polynómy viacerých premenných (nad nejakým konečným poľom) rovnajú, je v BPP (stačí polynómy vyhodnocovať na náhodných vstupoch). Zatiaľ sa nevie, či sa dá efektívne derandomizovať.

#P

Trieda funkcií (nie rozhodovacích problémov) f, ktoré predstavujú počet riešení problémov v NP (počet akceptačných výpočtov NTS). Prekvapujúco, PH ⊆ P^#P ⊆ PSPACE.

Problém #SAT (počet splňujúcich ohodnotení), či #PERFECT-MATCHING (počítanie perfektných párovaní) je #P-úplné.