Vybran´e tˇr´ıdy sloˇzitosti Pavel Erlebach Abstrakt: Tato pr´ace popisuje z´aklady teorie sloˇzitosti. Jsou zde uk´az´any jen z´akladn´ı teor´emy a definice, o to v´ıc se soustˇred´ı na pˇr´ıklady popisovan´ych tˇr´ıd a na jednoduchost pod´an´ı. C´ılem pr´ace je sezn´amit cˇ ten´aˇre s v´yznaˇcn´ymi tˇr´ıdami sloˇzitosti, s typick´ymi pˇr´ıklady jejich probl´em˚u a s d˚uleˇzit´ymi otevˇren´ymi probl´emy.
Tato pr´ace byla vypracov´ana v r´amci pˇredmˇetu Modern´ı teoretick´a informatika
Obsah: ´ 1 Uvod
3
2 Z´akladn´ı pojmy
3
3 Nejzn´amˇejˇs´ı teor´emy
4
´ e 4 Tˇr´ıdy upln´ 4.1 NL-complete . . . . . . 4.2 P-complete . . . . . . . 4.3 BQP-complete . . . . . . 4.4 NP-complete . . . . . . 4.5 (N)PSPACE-complete . . 4.6 EXPTIME-complete . . 4.7 NEXPTIME-complete . 4.8 (N)EXPSPACE-complete 4.9 2EXPTIME-complete . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
5 Tˇr´ıdy sloˇzitosti 5.1 SPACE(1) . . . . . . . . . . . . . . . . 5.2 L . . . . . . . . . . . . . . . . . . . . . 5.3 SL . . . . . . . . . . . . . . . . . . . . 5.4 NL . . . . . . . . . . . . . . . . . . . . 5.5 Bezkontextov´e jazyky . . . . . . . . . . 5.6 NC . . . . . . . . . . . . . . . . . . . . 5.7 NSPACE(n) . . . . . . . . . . . . . . . 5.8 P . . . . . . . . . . . . . . . . . . . . . 5.9 BPP . . . . . . . . . . . . . . . . . . . 5.10 BQP . . . . . . . . . . . . . . . . . . . 5.11 NP . . . . . . . . . . . . . . . . . . . . 5.12 (N)PSPACE . . . . . . . . . . . . . . . 5.13 EXPTIME, NEXPTIME, EXPSPACE... 5.14 rekurzivn´ı, rekurzivnˇe spoˇcetn´e, ... . . .
. . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . .
6 6 6 7 7 9 10 10 10 10
. . . . . . . . . . . . . .
11 11 12 12 12 12 12 13 13 13 13 14 14 14 14
6 Vztahy mezi tˇr´ıdami
15
7 Z´avˇer
16
2
´ 1 Uvod Proˇc se vlastnˇe zab´yvat nˇejakou sloˇzitost´ı, kdyˇz tu m´ame vyˇc´ıslitelnost, kter´a n´am zodpov´ı ot´azky typu: ”Je dan´y probl´em algoritmicky ˇreˇsiteln´y? D´a se dan´y probl´em ˇreˇsit z´asobn´ıkov´ym automatem??”. Potˇrebujeme vlastnˇe vˇedˇet jeˇstˇe nˇeco jin´eho? Ano. Napˇr´ıklad jak asi dlouho bude trvat vyˇreˇsen´ı dan´eho probl´emu pro vstup dlouh´y obecnˇe n. Napˇr´ıklad zkusme porovnat trv´an´ı vyhodnocen´ı formule d´elky n Presburger logiky, trv´an´ı komprese LZ78 pro ˇretˇezec d´elky n a trv´an´ı spoˇcten´ı hodnoty Ackermann(n, n). Vyˇc´ıslitelnost n´am ”pov´ı”, zˇ e na vˇsechny tyto probl´emy postaˇc´ı Turing˚uv stroj, ale tˇreba z´asobn´ıkov´y automat by si s nimi neporadil. Sloˇzitost n´am oproti tomu ˇrekne i to, zˇ e zat´ımco doba zpracov´an´ı komprese LZ78 s rostouc´ım n poroste polynomi´alnˇe (napˇr. n 3 + n), tak doba rozhodnut´ı n zm´ınˇen´e formule poroste 2-exponenci´alnˇe (22 ) a doba vyˇc´ıslen´ı Ackermannovy funkce dokonce jeˇstˇe rychleji (rychleji neˇz 2 na 2 na ... 2 na n pro libovoln´y poˇcet exponent˚u). ˇ z toho plyne praktick´a ˇreˇsitelnost tˇechto probl´em˚u. Zat´ımco zm´ınˇen´a Cili komprese se d´a zvl´adnout v re´aln´em cˇ ase (a taky se bˇezˇ nˇe pouˇz´ıv´a), Presburger logika je pouˇziteln´a uˇz v pouze velmi omezen´e m´ıˇre a hodnoty Ackermannovy funkce pro vˇetˇs´ı parametry (napˇr. Ackermann(5, 5)) zn´am´e prostˇe nejsou. Dalˇs´ı kapitoly jsou cˇ lenˇeny n´asleduj´ıc´ım zp˚usobem. Z´akladn´ı pojmy, zaveden´e pojmenov´an´ı tˇr´ıd a zp˚usoby mˇeˇren´ı sloˇzitosti najdeme v kapitole 2. Nejzn´amˇejˇs´ı teor´emy a prvn´ı otevˇren´e probl´emy si uk´azˇ eme v kapitole 3. O u´ plnosti obecnˇe a u´ pln´ych tˇr´ıd´ach si nˇeco pov´ıme v kapitole 4 a stejnˇe tak tu najdeme pˇr´ıklady probl´em˚u vˇsech v´yznaˇcn´ych u´ pln´ych tˇr´ıd. V kapitole 5. si pop´ısˇeme bl´ızˇ e nˇekter´e tˇr´ıdy sloˇzitosti a nast´ın´ıme jejich vztahy a koneˇcnˇe 6. kapitola obsahuje z´avˇer s koment´aˇri k t´eto pr´aci.
2 Z´akladn´ı pojmy Jak jiˇz bylo v u´ vodu nast´ınˇeno, sloˇzitost se zab´yv´a ot´azkami n´aroˇcnosti algoritm˚u. Rozliˇsujeme zejm´ena cˇ asovou sloˇzitost (ˇcili jak dlouho potrv´a v´ypoˇcet) a prostorovou sloˇzitost (kolik pamˇeti algoritmus zabere, pˇriˇcemˇz vstup nepoˇc´ıt´ame). Mezi prvn´ımi ot´azkami, co n´as napadnou, bude asi jak sloˇzitost vyj´adˇrit a jak ji mˇeˇrit. Pro pops´an´ı sloˇzitosti pouˇzijeme funkci s parametrem n, coˇz je d´elka vstupu, pˇr´ıpadnˇe dalˇs´ımi parametry jako napˇr. poˇcet v´ypoˇcetn´ıch stroj˚u apod. Zkuˇsenosti a statistiky ukazuj´ı, zˇ e nejvˇetˇs´ı vypov´ıdac´ı hodnotu m´a nejhorˇs´ı pˇr´ıpad a mˇeˇr´ı se i pr˚umˇern´y moˇzn´y pˇr´ıpad. Hodnoty pro jednotliv´e d´elky vstup˚u se 3
poˇc´ıtaj´ı, nebo se mˇeˇr´ı na dostateˇcn´em poˇctu n´ahodn´ych vzork˚u. Pokud napˇr´ıklad porovn´av´ame ˇrad´ıc´ı algoritmy, pracujeme s pˇresn´ymi tvary funkc´ı (napˇr. n 2 + 20n + 3), ale pracujeme-li se tˇr´ıdami probl´em˚u, zanedb´av´ame konstanty. Proˇc? I funkce 10100 n roste pomaleji neˇz n2 . Co se t´ycˇ e praktick´eho dopadu pˇri zanedb´an´ı konstant, v tomto pˇr´ıkladˇe by samozˇrejmˇe byla chyba pˇredpokl´adat, zˇ e by bylo pouˇzit´ı algoritmu s line´arn´ı sloˇzitost´ı dobrou volbou. Ale v praxi se podobn´e pˇr´ıklady nevyskytuj´ı (alespoˇn ne cˇ asto). Kromˇe zanedb´an´ı konstant provedeme jeˇstˇe dalˇs´ı zjednoduˇsen´ı, a to zˇ e rozdˇel´ıme funkce na nˇekolik skupin, kter´e pro n´as budou atomick´e. Urˇcitˇe je moˇzn´e rozdˇelit si napˇr. tˇr´ıdu P (tˇr´ıda probl´em˚u s polynomi´aln´ı cˇ asovou sloˇzitost´ı ˇreˇsen´a deterministicky) d´ale do tˇr´ıd probl´em˚u line´arn´ıch, kvadratick´ych, kubick´ych atd. Nicm´enˇe toto rozdˇelen´ı zde pro jednoduchost pomineme. Zato budeme zkoumat u kaˇzd´e z tˇr´ıd jeˇstˇe deterministrick´y, pˇr´ıp. nedeterministick´y pˇr´ıstup. Ve svˇetov´e literatuˇre [1, 2, 3] se cˇ asto vyskytuj´ı n´asleduj´ıc´ı konvence v oznaˇcen´ı tˇr´ıd. Je-li pˇredmˇetem z´ajmu cˇ asov´a, resp. prostorov´a sloˇzitost, naz´yv´a se tˇr´ıda TIME, resp. SPACE (napˇr. TIME[2n ], SPACE[1] ). Nedeterministick´y pˇr´ıstup odliˇs´ıme od deterministick´eho pˇrid´an´ım p´ısmena N na zaˇca´ tek (napˇr. NTIME[log(n)] ). Pokud jde o komplement´arn´ı tˇr´ıdu, pˇredsune se pˇred jm´eno tˇr´ıdy ”co” (napˇr. coNP). A nakonec se pouˇz´ıvaj´ı n´asleduj´ıc´ı synonyma (poly pˇredstavuje polynom): (N)SPACE[log(n)] = (N)L (N)TIME[poly(n)] = (N)P (N)SPACE[poly(n)] = (N)PSPACE (N)TIME[2n ] = (N)EXPTIME (N)SPACE[2n ] = (N)EXPSPACE n (N)TIME[22 ] = (N)EXP2TIME ...
3 Nejzn´amˇejˇs´ı teor´emy Z´akladn´ı vztahy popisuje n´asleduj´ıc´ı teor´em, kter´y plat´ı pro kaˇzdou funkci f (n): TIME[ f (n)] ⊆ NTIME[ f (n)] ⊆ SPACE[ f (n)] ⊆ NSPACE[ f (n)] ⊆ TIME[2 f (n) ] ⊆ ... 4
Dalˇs´ım zaj´ımav´ym teor´emem je tzv. teor´em prostˇredk˚u (resources theorem), kter´y n´am ˇr´ık´a, zˇ e pˇrid´an´ım cˇ asu nebo prostoru vˇzdy zv´ysˇ´ıme mohutnost tˇr´ıdy ˇreˇsiteln´ych probl´em˚u. f (n) < g(n) → TIME[ f (n)] ⊂ TIME[g(n)] → SPACE[ f (n)] ⊂ SPACE[g(n)] Savitch˚uv teor´em ukazuje, zˇ e tˇr´ıda probl´em˚u ˇreˇsen´ych nedeterministicky s nˇejakou prostorovou sloˇzitost´ı nikdy nepˇres´ahne tˇr´ıdu probl´em˚u ˇreˇsen´ych deterministicky s ”kvadraticky vˇetˇs´ı” prostorovou sloˇzitost´ı. NSPACE[ f (n)] ⊆ SPACE[ f 2 (n)] Nejd˚uleˇzitˇejˇs´ım d˚usledkem tohoto teor´emu je zejm´ena rovnost: NSPACE[poly(n)] = SPACE[poly(n)], cˇ ili NPSPACE = PSPACE A na konci t´eto kapitoly si uk´azˇ eme jeˇstˇe vztahy mezi z´akladn´ımi tˇr´ıdami s rozd´ıln´ymi funkcemi. Povˇsimnˇeme si, zˇ e kromˇe d˚usledku Savitchova teor´emu (viz v´ysˇe) a kromˇe nadˇrazenost´ı mnoˇzin vypl´yvaj´ıc´ıch z jejich ”exponenci´aln´ıho rozd´ılu” (exponential gap), jsou vˇsechny vztahy mezi tˇr´ıdami otevˇren´ym probl´emem, takˇze je tu obrovsk´y prostor pro v´yzkum. ˇ se odshora dol˚u (L ⊆ NL ⊆ P ⊆ ...), Jak ch´apat n´asleduj´ıc´ı sch´ema? Cte pˇriˇcemˇz tˇr´ıda vpravo od dan´e tˇr´ıdy je jej´ı vlastn´ı nadtˇr´ıdou (L ⊃ (N)PSPACE). L NL P NP (N)PSPACE EXPTIME NEXPTIME (N)EXPSPACE EXP2TIME ...
⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆
( ⊃ (N)PSPACE ) ( ⊃ (N)PSPACE ) ( ⊃ EXPTIME ) ( ⊃ NEXPTIME ) ( ⊃ (N)EXPSPACE ) ( ⊃ EXP2TIME ) ( ⊃ NEXP2TIME ) ( ⊃ (N)EXP2SPACE ) ( ⊃ EXP3TIME )
5
´ 4 Tˇr´ıdy upln´ e Pojem u´ plnosti se zavedl kv˚uli jednoduˇssˇ´ımu dokazov´an´ı ekvivalence nebo naopak odliˇsnosti tˇr´ıd. Neform´alnˇe m˚uzˇ eme u´ pln´y probl´em (resp. tˇr´ıdu u´ pln´ych probl´em˚u) popsat jako ”ten nejtˇezˇ sˇ´ı” probl´em dan´e tˇr´ıdy (resp. tˇr´ıdu ”tˇech nejtˇezˇ sˇ´ıch” ´ y probl´em probl´em˚u, co existuj´ı v pˇr´ısluˇsn´e nadtˇr´ıdˇe). Popiˇsme to form´alnˇeji. Upln´ dan´e tˇr´ıdy (napˇr. NP-´upln´y probl´em) je probl´em z pˇr´ısluˇsn´e nadtˇr´ıdy (tedy v naˇsem pˇr´ıkladˇe z NP) a plat´ı, zˇ e na nˇej mohou b´yt vˇsechny probl´emy ze stejn´e ´ a tˇr´ıda je pak tˇr´ıda tˇechto probl´em˚u. nadtˇr´ıdy polynomi´alnˇe zredukov´any. Upln´ V samotn´ych d˚ukazech se pak m˚uzˇ e postupovat napˇr´ıklad n´asledovnˇe. Chceme dok´azat, zˇ e NP = P. V´ıme uˇz, zˇ e P ⊆ NP. Opaˇcnou inkluzi dok´azˇ eme tˇreba tak, zˇ e vybereme nˇejak´y NP-´upln´y probl´em (napˇr. SAT probl´em nebo probl´em barven´ı grafu) a pro nˇej vymysl´ıme algoritmus, kter´y bude m´ıt polynomi´aln´ı sloˇzitost (a samozˇrejmˇe ho ˇreˇs´ı deterministickou cestou). T´ım je inkluze dok´az´ana a my jsme slavn´ı. Tato kapitola bude pokraˇcovat v´ycˇ tem v´yznaˇcn´ych u´ pln´ych tˇr´ıd a hlavnˇe pˇr´ıklad˚u pˇr´ısluˇsn´ych probl´em˚u, v´ıce viz [2].
4.1 NL-complete Tato tˇr´ıda je sp´ısˇe okrajovou z´aleˇzitost´ı. Pˇr´ıkladem u´ pln´eho probl´emu, kter´y se d´a ˇreˇsit na nedeterministick´em stroji s logaritmickou prostorovou n´aroˇcnost´ı, je dosaˇzitelnost v orientovan´em grafu (GAP).
4.2 P-complete Tato tˇr´ıda je mnohem zn´amˇejˇs´ı. Z´akladn´ı P-complete probl´em: mˇejme Turing˚uv stroj s nˇejak´ym vstupem na prvn´ı p´asce a cˇ ´ıslo T zapsan´e un´arnˇe (T jedniˇcek) na druh´e p´asce. Zastav´ı Turing˚uv stroj s t´ımto vstupem dˇr´ıve neˇz po T kroc´ıch? Dalˇs´ı pˇr´ıklady P-´upln´ych probl´emu jsou napˇr • Circuit Value Problem (CVP) - Pro dan´y obvod a vstupy obvodu vypoˇc´ıtat v´ystup obvodu. • Line´arn´ı programov´an´ı - napˇr. naj´ıt maximum nˇejak´e line´arn´ı funkce vzhledem k omezuj´ıc´ım podm´ınk´am 6
• Depth First Search Ordering - Pro dan´y graf a uzly u a v urˇcit, zda bude u navˇst´ıven dˇr´ıve neˇz v v prohled´av´an´ı do hloubky. • Context Free Grammar Membership - Pro danou bezkontextovou gramatiku a ˇretˇezec urˇcit, zda m˚uzˇ e b´yt tento ˇretˇezec touto gramatikou generov´an. • Horn satisfiability - naj´ıt pro danou mnoˇzinu Hornov´ych klauzul´ı promˇennou, pro kterou budou vˇsechny klauzule platit. • Hra Life - Mˇejme nˇejakou poˇca´ teˇcn´ı konfiguraci hry Life, buˇnku a cˇ ´ıslo T (zapsan´e un´arnˇe), pt´ame se, zda buˇnka bude po T kroc´ıch zˇ iv´a. • LZW algoritmus - pro dan´e ˇretˇezce s a t urˇcit, zd´a se pˇrid´a t po kompresi s (LZ78 metodou) do slovn´ıku (bereme v potaz napˇr. Unisys LZW technologii).
4.3 BQP-complete O tˇr´ıdˇe BQP se dov´ıme v´ıce v kapitole 5.10. Prozat´ım postaˇc´ı vˇedˇet, zˇ e je to nadmnoˇzina tˇr´ıdy P. Nev´ı se, jestli v˚ubec tˇr´ıda BQP m´a nˇejak´e u´ pln´e probl´emy, ale jsou zn´amy nˇekter´e probl´emy, kter´e jsou v BQP a vˇeˇr´ı se, zˇ e nejsou v P (d˚ukaz zat´ım nebyl proveden). Jsou zn´am´e tˇri takov´e probl´emy. • Faktorizace cˇ´ısel - pro dan´e cˇ´ıslo chceme vˇedˇet jeho rozklad na prvoˇc´ısla (napˇr. pro cˇ´ıslo 48 to 24 .3). • Diskr´etn´ı logaritmus - to je sloˇzitˇe popsateln´y algoritmus, kde pro cyklickou grupu G a jej´ı gener´ator b definujeme funkci celoˇc´ıseln´eho logaritmu se z´akladem b. • Simulace kvantov´ych syst´em˚u.
4.4 NP-complete Tato tˇr´ıda byla pravdˇepodobnˇe prvn´ı u´ plnou tˇr´ıdou. Kdyby se totiˇz uk´azalo, zˇ e se d´a nˇekter´y probl´em z t´eto tˇr´ıdy ˇreˇsit deterministicky v polynomi´aln´ım cˇ ase, znamenalo by to, zˇ e P = NP, coˇz je probl´em, o jehoˇz dok´az´an´ı nebo vyvr´acen´ı se snaˇz´ı teoretici z cel´eho svˇeta uˇz nˇekolik desetilet´ı. V roce 1971, kdy byl pojem u´ plnosti zaveden, byl prvn´ım pˇr´ıkladem NPu´ pln´eho probl´emu probl´em splitelnosti (Boolean satisfiability problem - SAT). 7
Jde o probl´em, kde pro nˇejak´y boolovsk´y v´yraz s promˇenn´ymi m´ame rozhodnout, zda existuje nˇejak´e ohodnocen´ı promˇenn´ych, pro kter´e m´a cel´y v´yraz plat´ı. Od t´e doby byly nalezeny doslova tis´ıce dalˇs´ıch NP-´upln´ych probl´em˚u, uvedeme si zde nˇekolik nejzn´amˇejˇs´ıch. Co se pˇr´ıklad˚u t´ycˇ e, budeme t´eto tˇr´ıdˇe vˇenovat nejv´ıce prostoru, protoˇze jde o z´akladn´ı tˇr´ıdu teorie sloˇzitosti a nav´ıc je zde nadˇeje, zˇ e nˇejak´eho cˇ ten´aˇre napadne deterministick´e ˇreˇsen´ı nˇekter´eho z probl´em˚u v polynomi´aln´ım cˇ ase, coˇz by bylo vskutku v´yborn´e (P = NP). • N-puzzle - jde o zn´amou hru, kde je N posunovac´ıch cˇ tvereˇck˚u a jedna mezera, c´ılem je dos´ahnout v´ychoz´ıho postaven´ı, pˇr´ıpadnˇe rozhodnout, zda to z dan´eho postaven´ı jde. • Knapsack problem - tento pˇr´ıklad je postaven na situaci, zˇ e jsme naˇsli poklad, ale cel´y ho neuneseme. Chceme odn´est maxim´aln´ı moˇzn´e bohatstv´ı za pˇredpokladu, zˇ e m´ame danou nosnost, pˇriˇcemˇz kaˇzd´a poloˇzka pokladu m´a nˇejakou cenu a nˇejakou v´ahu. • Hamiltonova kruˇznice - pro dan´y graf rozhodnout, zda tam existuje Hamiltonova kruˇznice, coˇz je kruˇznice (cesta grafem, kter´a zaˇc´ın´a a konˇc´ı ve stejn´em bodˇe), kter´a proch´az´ı vˇsemi body grafu. • Traveling salesman problem (TSP) - pro dan´y poˇcet mˇest a pro ceny cest mezi jednotliv´ymi mˇesty naj´ıt nejlevnˇejˇs´ı zp˚usob cestov´an´ı, aby kaˇzd´e mˇesto bylo navˇst´ıveno aspoˇn jednou a aby se nakonec cestovatel dostal zp´atky do startuj´ıc´ıho mˇesta. • Izomorfismus podgraf˚u - rozhodnout, zda pro dan´e dva grafy G1 , G2 plat´ı, zˇ e je G1 izomorn´ı s nˇejak´ym podgrafem G2 . • Subset sum problem - je zn´am´y a d˚uleˇzit´y probl´em v teorii sloˇzitosti a v kryptografii. Pro danou mnoˇzinu cel´ych cˇ ´ısel se pt´ame, jestli existuje nˇejak´a jej´ı podmnoˇzina takov´a, zˇ e je souˇcet cˇ ´ısel t´eto podmnoˇziny 0 (pˇr´ıpadnˇe jak´ekoliv k). Napˇr. pro mnoˇzinu { 2, 6, 1, 10, -4, -5 } je odpovˇed´ı ANO, protoˇze podmnoˇzina { 2, 6, 1, -4, -5 } m´a souˇcet 0. • Hled´an´ı nejvˇetˇs´ı kliky v grafu - klika je mnoˇzina vrchol˚u, kter´e jsou navz´ajem sousedn´ı kaˇzd´y s kaˇzd´ym, ˇreˇceno neform´alnˇe. • Probl´em pokryt´ı grafu - pro dan´y graf a nˇejak´e cˇ ´ıslo k se pt´ame, existuje-li pokryt´ı grafu o velikosti k nebo menˇs´ı. Pokryt´ım grafu rozum´ıme mnoˇzinu 8
vrchol˚u takovou zˇ e, pro vˇsechny hrany grafu potom plat´ı, zˇ e aspoˇn jeden konec hrany konˇc´ı ve vrcholu z mnoˇziny pokryt´ı. • Probl´em obarven´ı grafu. Graf je korektnˇe obarven´y, pokud kaˇzd´emu vrcholu pˇriˇrad´ıme cˇ ´ıslo (barvu) a plat´ı, zˇ e zˇ a´ dn´e dva sousedn´ı vrcholy nejsou obarveny stejnou barvou. Samotn´y probl´em pak zn´ı: d´a se dan´y graf obarvit s pouˇzit´ım k barev nebo m´enˇe?
4.5 (N)PSPACE-complete Prvn´ım probl´emem t´eto tˇr´ıdy byl podobnˇe jako u pˇredchoz´ı tˇr´ıdy probl´em splnitelnosti (SAT) s t´ım rozd´ılem, zˇ e zat´ımco SAT coby NP-complete bychom mohli zapsat takto: ∃x1 ∃x2 ∃x3 : (x1 ∨ x2 ∨ ¬x3 ) ∧ (¬x1 ∨ ¬x2 ∨ ¬x3 ) Tak v PSPACE-complete pˇribyde jeˇstˇe univerz´aln´ı kvantifik´ator a pˇr´ıklad by pak mohl vypadat takto: ∃x1 ∃x2 ∀x3 : (x1 ∨ x2 ∨ ¬x3 ) ∧ (¬x1 ∨ ¬x2 ∨ ¬x3 ) Povˇsimnˇete si, zˇ e NP-complete probl´em pˇripom´ın´a typickou h´adanku - je nˇejak´a kombinace hodnot takov´a, aby to splnilo nˇejakou podm´ınku? Proti tomu PSPACE-complete probl´em pˇripom´ın´a hru - je nˇejak´y tah, kter´y bych mohl udˇelat, ˇ abych mohl vyhr´at nez´avisle na tahu protivn´ıka (tj. abych vyhr´al po V SECH moˇzn´ych taz´ıch protivn´ıka). V t´eto ot´azce se stˇr´ıd´a existenˇcn´ı a univerz´aln´ı kvantifik´ator. Po takov´em u´ vodu asi nikoho nepˇrekvap´ı, zˇ e se mnoho PSPACE u´ pln´ych probl´em˚u rekrutuje z ˇrad her • Reversi - je typick´ym PSPACE-complete probl´emem, resp. nalezen´ı nejlepˇs´ıho tahu v Reversi, pokud zobecn´ıme hru na n × n pol´ı. Stejnˇe tak hra CEX. Jsou to hry, kde se stˇr´ıda n´asˇ tah s protivn´ıkov´ym. Pˇritom ale st´ale spˇejeme ke konci hry. Nen´ı moˇzn´e se nˇejak´ym zp˚usobem ”zacyklit”. Takˇze pro pevn´e n m˚uzˇ e hra trvat nˇejak´y koneˇcn´y poˇcet tah˚u (konkr´etnˇe n2 ). Proto tˇreba sˇachy zobecnˇen´e na n × n pol´ı do t´eto tˇr´ıdy nepatˇr´ı, jelikoˇz neform´alnˇe ˇreˇceno dokonal´ı hr´acˇ i mohou hr´at jednu hru ”velmi dlouho”. M´ısto toho patˇr´ı do tˇr´ıdy EXPTIME (pˇriˇcemˇze ale nen´ı dok´az´ano, plat´ı-li PSPACE ⊂ EXPTIME) 9
• Mahjong - patˇr´ı tak´e do t´eto tˇr´ıdy, i kdyˇz prakticky hraje cˇ lovˇek s´am se sebou. Stejnˇe tak atomix, sokoban nebo Rush Hour. • Context Sensitive Grammar Membership - do t´eto tˇr´ıdy nepatˇr´ı samozˇrejmˇe jen hry. Tento probl´em je velice podobn´y jako Context Free Grammar Membership (kapitola 4.2). Pro danou kontextovou gramatiku a dan´y ˇretˇezec m´ame rozhodnout, jestli je moˇzn´e tou gramatikou vygenerovat ten ˇretˇezec.
4.6 EXPTIME-complete Jak uˇz jsme se doˇcetli v pˇredchoz´ı kapitole, nejzn´amˇejˇs´ı probl´emy t´eto tˇr´ıdy jsou hrami, kde proti sobˇe stoj´ı dva protivn´ıci, pˇriˇcemˇz nen´ı zˇ a´ dn´ym zp˚usobem zaruˇcen konec hry, jako tomu je tˇreba v sˇach´ach, d´amˇe nebo Go. Probl´em m˚uzˇ eme definovat jako urˇcen´ı, zda m˚uzˇ e hr´acˇ , kter´y je pr´avˇe na tahu, vyhr´at za vˇsech okolnost´ı (tj. pˇri vˇsech moˇznostech odpovˇed´ı protihr´acˇ e). Plat´ı exponenci´aln´ı z´avislost jak ji zn´ame, pokud zobecn´ıme zm´ınˇen´e hry na velikost sˇachovnice n × n.
4.7 NEXPTIME-complete Tato tˇr´ıda je tu pops´ana sp´ısˇe pro u´ plnost. Pˇr´ıkladem probl´emu, kter´y do n´ı patˇr´ı, je rozhodnout, zda dva regul´arn´ı v´yrazy popisuj´ı stejn´e nebo r˚uzn´e jazyky, pˇriˇcemˇz v´yrazy jsou limitov´any n´asleduj´ıc´ımi operacemi: sjednocen´ı, konkatenace a mocnina na druhou (dvˇe kopie v´yrazu).
4.8 (N)EXPSPACE-complete Dalˇs´ı tˇr´ıda sp´ısˇe okrajov´eho charakteru, protoˇze sloˇzitost vˇetˇsinou zamezuje praktick´e pouˇzit´ı. Nicm´enˇe uvedeme si zde jeden pˇr´ıklad, kter´y u´ zce souvis´ı s pˇredchoz´ım, cˇ ili opˇet jde o to rozhodnout, zda dva regul´arn´ı v´yrazy popisuj´ı stejn´e nebo r˚uzn´e jazyky, pˇriˇcemˇz v´yrazy jsou limitov´yny operacemi: sjednocen´ı, konkatenace, mocnina na druhou a Kleenova hvˇezda (nula nebo v´ıce kopi´ı v´yrazu).
4.9 2EXPTIME-complete Tato tˇr´ıda je nejsloˇzitˇejˇs´ı u´ plnou tˇr´ıdou, kterou si zde uk´azˇ eme. Nen´ı dok´az´an (nebo aspoˇn jsem nenaˇsel) zˇ a´ dn´y u´ pln´y probl´em t´eto tˇr´ıdy, nicm´enˇe si uk´azˇ eme probl´em, pro kter´y se v roce 1974 podaˇrilo dok´azat, zˇ e patˇr´ı do tˇr´ıdy 2EXPTIME a nepatˇr´ı do tˇr´ıdy EXPTIME. Je to rozhodnut´ı pravdivosti formul´ı Presburgerovy 10
aritmetiky, coˇz je aritmetika, kde se vyskytuj´ı konstanty 0 a 1, funkce +, predik´at = a kvantifik´ator ∀. Pouˇz´ıv´a se i pˇres svou enormn´ı sloˇzitost ve verifikaci mal´ych probl´em˚u. Z´akladem jsou n´asleduj´ıc´ı axiomy: 1. ∀x : ¬(0 = x + 1) 2. ∀x∀y : ¬(x = y) → ¬(x + 1 = y + 1) 3. ∀x : x + 0 = x 4. ∀x∀y : (x + y) + 1 = x + (y + 1) 5. Tento axiom se skl´ad´a z nekoneˇcnˇe mnoha axiom˚u. Pokud P(x) je formule zahrnuj´ıc´ı pouze konstanty 0, 1, +, = a volnou promˇennou x, potom n´asleduj´ıc´ı formule je axiom: (P(0) ∧ ∀x : P(x) → P(x + 1)) → ∀x : P(x) Z´aleˇzitosti jako dˇelitelnost nebo prvoˇc´ısla nemohou b´yt formalizov´any v Presburgerovˇe aritmetice. Nicm´enˇe tˇreba n´asleduj´ıc´ı pˇr´ıklad se dok´azat d´a. Ukazuje, zˇ e pokud x ≤ y + 1, potom y + 2 > x. ∀x∀y : ((∃z : x + z = y + 1) → (∀z : ¬(((1 + y) + 1) + z = x)))
5 Tˇr´ıdy sloˇzitosti V t´eto kapitole si pop´ısˇeme dalˇs´ı zaj´ımav´e tˇr´ıdy, z nichˇz nˇekter´e pak zaˇrad´ıme do tabulky tˇr´ıd sloˇzitosti, kter´a pak bude v dalˇs´ı kapitole. Tato pr´ace se nesnaˇz´ı vyˇcerp´avaj´ıc´ım zp˚usobem popsat vˇsechny publikovan´e tˇr´ıdy, jen pop´ısˇe nˇekter´e zaj´ımavˇejˇs´ı a o ostatn´ıch se tˇreba zm´ın´ı. Kompletn´ı v´ycˇ et a popis vˇsech tˇr´ıd je k nalezen´ı v [1].
5.1 SPACE(1) Tˇr´ıda probl´em˚u ˇreˇsiteln´ych s konstantn´ı prostorovou sloˇzitost´ı je ekvivalentn´ı tˇr´ıdˇe jazyk˚u typu 3 v Chomsk´eho hierarchii. D´ale plat´ı, zˇ e SPACE(1) = SPACE(log log n) Probl´emy t´eto fundament´aln´ı tˇr´ıdy jsou ˇreˇsiteln´e deterministick´ym i nedeterministick´ym koneˇcn´ym automatem. A typick´ym pˇr´ıkladem z t´eto tˇr´ıdy je ot´azka: je poˇcet jednoˇcek na vstupu sud´y? Ale uˇz ne ot´azka: Je na vstupu v´ıce jedniˇcek neˇz nul? To se obˇcas oznaˇcuje jako nˇeco, co ”koneˇcn´e automaty neum´ı spoˇc´ıst”. 11
5.2 L Jde o tˇr´ıdu probl´em˚u s logaritmickou prostorovou sloˇzitost´ı ˇreˇsen´ych deterministicky (pˇriˇcemˇz vstup se do souhrnu prostorov´e sloˇzitosti nepoˇc´ıt´a, pokud nen´ı mˇenˇen). Novˇe (v roce 2004) bylo uk´az´ano, zˇ e L = SL (viz dalˇs´ı tˇr´ıda).
5.3 SL Symetrick´a tˇr´ıda s logaritmickou prostorovou sloˇzitost´ı (definovan´a v roce 1982) obsahuje takov´e probl´emy, kter´e jsou ˇreˇsiteln´e nedeterministick´ym Turingov´ym strojem tak, zˇ e: 1. Pokud je v´ysledkem ANO, jedna nebo v´ıce v´ypoˇcetn´ıch cest vstup pˇrij´ım´a. 2. Pokud je v´ysledkem NE, vˇsechny v´ypoˇcetn´ı cesty vstup zam´ıtne. 3. Pokud m˚uzˇ e Turing˚uv stroj prov´est pˇrechod z A do B, potom m˚uzˇ e prov´est pˇrechod i z B do A (to je to, co je myˇsleno symetriˇcnost´ı).
5.4 NL Tˇr´ıda probl´em˚u ˇreˇsiteln´ych nedeterministicky s logaritmickou cˇ asovou sloˇzitost´ı. V roce 1988 bylo uk´az´ano, zˇ e je tato tˇr´ıda ekvivalentn´ı s tˇr´ıdou coNL, coˇz je komplementn´ı tˇr´ıda probl´em˚u k NL.
5.5 Bezkontextov´e jazyky Dobˇre zn´am´a tˇr´ıda jazyk˚u typu 2 Chomsk´eho hierarchie. Je to tˇr´ıda probl´em˚u ˇreˇsiteln´a deterministick´ym z´asobn´ıkov´ym automatem. Je podtˇr´ıdou tˇr´ıdy NTIME(n), vztah k NL je otevˇren´ym probl´emem.
5.6 NC Tzv. Nickova tˇr´ıda (Nick Class) je tˇr´ıda probl´em˚u ˇreˇsiteln´ych v polylogaritmick´em cˇ ase (tj. (log(n))c) na paraleln´ım poˇc´ıtaˇci s polynomi´aln´ım poˇctem procesor˚u (tj. nk ). Je zn´amo, zˇ e NC je podmnoˇzina P, ale nev´ı ze, jestli to plat´ı naopak. Pˇredpokl´ad´a se, zˇ e ne, cˇ ili zˇ e P je vlastn´ı nadmnoˇzina NC. A dovol´ım si drobnou pozn´amku pod cˇ arou - n´azev Nickova tˇr´ıda vznikla d´ıky Stephenovi Cookovi, kter´y tuto tˇr´ıdu tak nazval po Nickovi Pippengerovi, kter´y se intenzivnˇe zab´yval v´yzkumem probl´em˚u s polylogaritmickou cˇ asovou sloˇzitost´ı. 12
5.7 NSPACE(n) Tˇr´ıda probl´em˚u ˇreˇsiteln´a nedeterministicky s line´arn´ı cˇ asovou sloˇzitost´ı je ekvivalentn´ı dobˇre zn´am´e tˇr´ıdˇe jazyk˚u typu 1, tedy kontextov´ych jazyk˚u. Je zˇrejm´e, zˇ e je podtˇr´ıdou tˇr´ıdy PSPACE, nicm´enˇe jej´ı vztah k NC, P, NP a mnoha dalˇs´ım tˇr´ıd´am sloˇzitosti nen´ı zn´am´y.
5.8 P Tato tˇr´ıda to vˇsechno zaˇcala. Byla definov´ana uˇz v roce 1960 a zahrnuje netrivi´aln´ı probl´emy (viz kapitola 4.). Je to tˇr´ıda jazyk˚u ˇreˇsiteln´a deterministicky v polynomi´aln´ım cˇ ase. I kdyˇz to byla prakticky prvn´ı definovan´a tˇr´ıda sloˇzitosti, nen´ı s n´ı spjata t´emˇeˇr zˇ a´ dn´a jistota, co se t´ycˇ e vztah˚u s okoln´ımi tˇr´ıdami. Je nadmnoˇzinou tˇr´ıdy NC a podmnoˇzinou tˇr´ıd NP, BPP, BQP, coNP, ale o ekvivalenci pˇr´ıp. neekvivalenci tˇechto mnoˇzin nebylo zat´ım dok´az´ano nic. Nejvˇetˇs´ım a nejzn´amˇejˇs´ım otevˇren´ym probl´emem je (ne)ekvivalence tˇr´ıd P a NP. Odborn´ıci cel´eho svˇeta se o potvrzen´ı nebo o vyvr´acen´ı rovnosti snaˇz´ı uˇz t´emˇeˇr 50 let. Vˇetˇsina z nich zast´av´a n´azor, zˇ e tˇr´ıdy ekvivalentn´ı nejsou, nˇekteˇr´ı si nav´ıc mysl´ı, zˇ e ot´azka P vs NP nen´ı ˇreˇsiteln´a zn´am´ymi axiomy mnoˇzinov´e teorie. J´a se tedy pˇrizn´am, zˇ e jsem objevil zp˚usob, jak dok´azat, zˇ e P = NP. Bohuˇzel nen´ı v tomto cˇ l´anku tolik prostoru, abych sem cel´y d˚ukaz pˇredvedl. Je to obrovsk´a sˇkoda, protoˇze jinak bych dostal 1.000.000$, coˇz je sl´ıbeno cˇ lovˇeku, kter´y tuto ot´azku zodpov´ı a d˚ukazem potvrd´ı. Nevad´ı, snad se to vejde do jin´eho cˇ l´anku.
5.9 BPP Bounded-Error Probablistic Polynomial-Time je tˇr´ıda probl´em˚u ˇreˇsiteln´a na pravdˇepodobnostn´ım Turingovˇe stroji v polynomi´aln´ım cˇ ase s pravdˇepodobnost´ı chyby maxim´alnˇe 1/3. Tato tˇr´ıda nem´a u´ pln´e probl´emy nebo zat´ım nejsou zn´am´e. Co se t´ycˇ e t´e tˇretiny, bylo dok´az´ano, zˇ e BPP = BPPp, kde p = (0, 1/2). Ideou je, zˇ e m˚uzˇ eme bˇeh libovolnˇekr´at zopakovat, pˇriˇcemˇz pravdˇepodobnost chyby kles´a exponenci´alnˇe. Je zn´amo, zˇ e BPP = coBPP. Nev´ı se vˇsak, jak´y je vztah NP a BPP.
5.10 BQP Bounded-Error Quantum Polynomial-Time je tˇr´ıda probl´em˚u ˇreˇsiteln´a na kvantov´em poˇc´ıtaˇci s pravdˇepodobnost´ı chyby maxim´alnˇe 1/3. Stejnˇe jako v pˇr´ıpadˇe pˇredchoz´ı tˇr´ıdy ani u t´eto tˇr´ıdy nez´avis´ı na konstantˇe vyjadˇruj´ıc´ı maxim´aln´ı chybu, 13
je li z intervalu (0, 1/2). O t´eto tˇr´ıdˇe se sice taky nev´ı, zda m´a u´ pln´e probl´emy, ale jsou zn´amy tˇri, kter´e patˇr´ı do BQP, ale vˇeˇr´ı se tomu, zˇ e nepatˇr´ı do P (kapitola 4.3). ˇ dok´az´ano nen´ı zase skoro nic. Je zn´amo, zˇ e BQP je nadtˇr´ıdou P a podtˇr´ıdou Cili NP (narozd´ıl od BPP!).
5.11 NP Tˇr´ıda jazyk˚u ˇreˇsiteln´a nedeterministicky v polynomi´aln´ım cˇ ase obsahuje nezvykle velk´y poˇcet probl´em˚u, se kter´ymi se bˇezˇ nˇe setk´av´ame. Pˇr´ıklady jsou rozeps´any v kapitole 4.4. Tato tˇr´ıda je podmnoˇzinou tˇr´ıdy PSPACE a nadmnoˇzinou tˇr´ıd BQP a P, ale opˇet nebyl zat´ım uk´az´an d˚ukaz potvrzuj´ıc´ı nebo vyvracej´ıc´ı ekvivalenci nˇekter´e dvojice tˇechto mnoˇzin. Probl´em P vs NP je bl´ızˇ e pops´an v kapitole 5.8.
5.12 (N)PSPACE Tato tˇr´ıda zastˇreˇsuje ”ˇcasovˇe rozumn´e” probl´emy. Je vlastn´ı nadtˇr´ıdou tˇr´ıdy kontextov´ych jazyk˚u a NC tˇr´ıdy. Je nadtˇr´ıdou tˇr´ıd coNP, NP, BPP, BQP, P a podtˇr´ıdou tˇr´ıdy EXPTIME. Protoˇze v´ıme, zˇ e NC ⊂ PSPACE NC ⊆ P ⊆ NP ⊆ PSPACE Je zˇrejm´e, zˇ e aspoˇn jeden z ⊆ symbol˚u bude ⊂. Vˇeˇr´ı se, zˇ e jsou vlastn´ı ikluze vˇsechny tˇri, nicm´enˇe nepodaˇrilo se dok´azat zat´ım ani jednu.
5.13 EXPTIME, NEXPTIME, EXPSPACE... Tyto tˇr´ıdy nebudeme d´ale rozeb´ırat. Uˇz v pˇredchoz´ıch kapitol´ach byly naznaˇcen´e k nim pˇr´ısluˇsn´e u´ pln´e probl´emy a vztahy tˇechto tˇr´ıd.
5.14 rekurzivn´ı, rekurzivnˇe spoˇcetn´e, ... Ani tyto tˇr´ıdy nebudeme analyzovat. Stoj´ı totiˇz mimo popisovanou oblast sloˇzitosti (ˇci pˇresnˇeji nad n´ı).
14
typ 0
EXP2TIME
EXPSPACE
EXPTIME
PSPACE = NPSPACE
NSPACE(n) = typ 1
NP
BQP
coNP
BPP
P
NC
typ 2
NL = coNL = SL
SPACE(1) = NSPACE(1) = typ 3
L
6 Vztahy mezi tˇr´ıdami Na z´avˇer pr´ace si jeˇstˇe pˇrehlednˇe a souhrnnˇe na obr´azku (na t´eto str´ance) uk´azˇ eme vztahy vˇsech zmiˇnovan´ych tˇr´ıd. Nepˇreruˇsovan´a (resp. pˇreruˇsovan´a) sˇ ipka od A do B znamen´a A ⊃ B (resp. A ⊇ B). U tˇr´ıd bez vz´ajemn´e sˇipky na stejn´e u´ rovni nen´ı zn´am vztah. Nalevo jsou tˇr´ıdy Chomsk´eho klasifikace. Vpravo dole jsou tˇr´ıdy okrajovˇejˇs´ıho charakteru s logaritmickou prostorovou sloˇzitost´ı. Uprostˇred jsou uk´az´any vztahy mezi hlavn´ımi tˇr´ıdami, kter´e tu byly pops´any. Cel´e sch´ema zastˇreˇsuje tˇr´ıda jazyk˚u typu 0. 15
7 Z´avˇer V pr´aci jsem se snaˇzil co moˇzn´a nejpˇr´ıstupnˇejˇs´ı formou vyloˇzit z´aklady teorie sloˇzitosti, uk´azat nˇekter´e zaj´ımav´e tˇr´ıdy, jejich vz´ajemn´e vztahy, pˇr´ıklady jejich probl´em˚u a nˇekter´e otevˇren´e probl´emy. Pr´ace nem´a zˇ a´ dn´y objevn´y charakter, byla vypracov´ana v r´amci pˇredmˇetu TID (Modern´ı teoretick´a informatika) a souvislost s mou vlastn´ı dizertaˇcn´ı prac´ı je minim´aln´ı. Proto zde asi chyb´ı prvky vlastn´ıho pˇr´ınosu do dan´e oblasti a ze stejn´eho d˚uvodu asi nebude dosahovat kvalit prac´ı m´ych koleg˚u, jejichˇz v´yzkum s danou oblast´ı u´ zce souvis´ı.
Zdroje informac´ı: [1] The Complexity Zoo http://www.complexityzoo.com [2] Wikipedia, the free encyclopedia http://en.wikipedia.org/wiki/Computation [3] Complexity And Other Software Metrics http://web.cs.mun.ca/˜ulf/gloss/complex.html
16
