Sloˇzitost Od Turingov´ych stroj˚ u k P=NP
Zbynˇek Koneˇcn´y Zimnˇ en´ı 2011
12.–16.2.2011
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
1 / 24
O ˇcem to dnes bude?
1
Co to je sloˇzitost
2
V´ypoˇcetn´ı modely
3
Vyˇc´ıslitelnost
4
Sloˇzitost na TS
5
Sloˇzitostn´ı tˇr´ıdy
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
2 / 24
Co to je sloˇzitost
Probl´em, jazyk
rozhodovac´ı probl´em: m´ame rozhodnout, jestli m´a nˇejak´y objekt nˇejakou vlastnost (Je v´yrokov´a formule splniteln´a? Lze graf obarvit ˇctyˇrmi barvami?) v´ypoˇcetn´ı probl´em: m´ame na z´akladˇe jednoho objektu naj´ıt jin´y objekt (Co dosadit do formule, aby byla splnˇena? Jak obarvit graf?) na t´eto pˇredn´aˇsce budeme mluvit pouze o rozhodovac´ıch jazykem naz´yv´ame mnoˇzinu vˇsech k´ od˚ u (bin´arn´ıch, nebo nad jinou koneˇcnou abecedou) objekt˚ u, kter´e maj´ı nˇejakou vlastnost rozpozn´avat jazyk = ˇreˇsit rozhodovac´ı probl´em instance probl´emu = konkr´etn´ı objekt, o nˇemˇz se m´a rozhodnout
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
3 / 24
Co to je sloˇzitost
Sloˇzitost
sloˇzitost algoritmu = mnoˇzstv´ı zdroj˚ u spotˇrebovan´en´e algoritmem k vyˇreˇsen´ı probl´emu v z´avislosti na velikosti instance sloˇzitost probl´emu = mnoˇzstv´ı zdroj˚ u potˇrebn´e k vyˇreˇsen´ı probl´emu v z´avislosti na velikosti jeho instance typicky ˇcas (poˇcet operac´ı) a prostor (mnoˇzstv´ı pamˇet´ı) z´avis´ı na v´ypoˇcetn´ım modelu
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
4 / 24
V´ ypoˇ cetn´ı modely
Turing˚ uv stroj
chceme poˇc´ıtat proveden´e instrukce bˇeˇzn´y poˇc´ıtaˇc: 32b / 64b, RISC/CISC ... pro form´aln´ı popis je lepˇs´ı Turing˚ uv stroj (d´ale TS) m´a jednu ”promˇennou” ve kter´e je uloˇzen stav, a nekoneˇcnˇe dlouhou p´asku, na kter´e je ze zaˇc´atku vstup na p´asku m˚ uˇze zapisovat pouze symboly dan´e abecedy na zaˇc´atku p´asky je nepˇrepsateln´e δ ”program”je funkce, kter´a symbolu na p´asce a stavu pˇriˇrad´ı nov´y symbol, nov´y stav a posun na p´asce dva speci´aln´ı stavy: pˇrijato a zam´ıtnuto
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
5 / 24
V´ ypoˇ cetn´ı modely
TS a jazyky
TS ˇc´asteˇcnˇe rozpozn´av´a jazyk L pokud nad jeho slovy skonˇc´ı ve stavu pˇrijato, pro ostatn´ı slova se zacykl´ı nebo skonˇc´ı ve stavu zam´ıtnuto TS rozpozn´av´a jazyk L pokud nad jeho slovy skonˇc´ı ve stavu pˇrijato a nad ostatn´ımi ve stavu zam´ıtnuto
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
6 / 24
V´ ypoˇ cetn´ı modely
Pˇr´ıklady
najdˇete TS pro bin´arn´ı z´apisy ˇc´ısel dˇeliteln´ych 7 najdˇete TS pro jazyk vˇsech slov, kter´a obsahuj´ı stejnˇe znak˚ u A, B a C
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
7 / 24
V´ ypoˇ cetn´ı modely
Alternativn´ı definice
v´ıce hlav v´ıce p´asek oboustrann´a p´aska pevn´a abeceda δ, 0, 1, − pouze jeden stav (pak je potˇreba velk´a abeceda)
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
8 / 24
V´ ypoˇ cetn´ı modely
Slabˇs´ı modely
stroj m´a dvˇe p´asky, na v´ystupn´ı p´asce mus´ı hlava vˇzdy ukazovat na posledn´ı symbol r˚ uzn´y od - (z´asobn´ıkov´y automat) stroj sm´ı pouze ˇc´ıst a hlavou pohybvat pouze doprava (koneˇcn´y automat) omezen´ı na poˇcet operac´ı / d´elku popsan´e p´asky
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
9 / 24
V´ ypoˇ cetn´ı modely
Dalˇs´ı modely
nedeterministick´e Turingovy stroje bˇeˇzn´e poˇc´ıtaˇce + programovac´ı jazyky (C, Pascal, Java) while-programy Random Access Machine paraleln´ı poˇc´ıtaˇce kvantov´e poˇc´ıtaˇce vˇsechny tyto modely um´ı ˇreˇsit stejn´e probl´emy, ale r˚ uznˇe rychle
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
10 / 24
Vyˇ c´ıslitelnost
Trocha teorie mnoˇzin
Turingovy stroje lze oˇc´ıslovat (je jich spoˇcetnˇe) jazyky oˇc´ıslovat nelze (je jich stejnˇe jako re´aln´ych ˇc´ısel) existuj´ı jazyky, kter´e nelze ˇc´asteˇcnˇe rozpoznat ostatn´ı naz´yv´ame ”rekurzivnˇe spoˇcetn´e” (Re)
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
11 / 24
Vyˇ c´ıslitelnost
Halting problem
existuje program, kter´y by dle zdroj´aku urˇcil, zda program pro dan´y vstup skonˇc´ı? jistˇe lze rozpoznat ˇc´asteˇcnˇe (simulace) pˇredpokl´adejme, ˇze halt vstup (i,x) akceptuje, pokud TS ˇc´ıslo i nad vstupem x skonˇc´ı; jinak zam´ıt´a vyrobme TS confuse, kter´y vstup i zam´ıt´a, pokud halt akceptuje (i,i); jinak confuse cykl´ı necht’ e je ˇc´ıslo programu confuse. Pokud confuse(e) = 0, pak halt(e, e) = 0, tedy confuse(e) cykl´ı. pokud confuse(e) cykl´ı, pak halt(e, e) 6= 0. To znamen´a, ˇze halt(e, e) = 0, spor.
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
12 / 24
Vyˇ c´ıslitelnost
Rekurzivn´ı jazyky
nˇekter´e jazyky (napˇr. jazyk ˇc´ısel vˇsech TS, kter´e necykl´ı) jsou jen ˇc´asteˇcnˇe rozpoznateln´e ostatn´ı naz´yv´ame ”rekurzivn´ı” (Rec) doplnˇek rekurzivn´ıho jazyka je jistˇe rekurzivn´ı doplnˇek rekurzivnˇe spoˇcetn´eho L nemus´ı je rekurzivnˇe spoˇcetn´y, pr´avˇe kdyˇz je L rekurzivn´ı
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
13 / 24
Sloˇzitost na TS
Sloˇzitost na TS
ˇcasov´a sloˇzitost TS = maxim´aln´ı moˇzn´y poˇcet pˇrechod˚ u TS (v z´avislosti na d´elce vstupu) pro nedeterministick´y stroj d´elka nejkratˇs´ıho moˇzn´eho v´ypoˇctu ˇcasov´a sloˇzitost probl´emu = ˇcasov´a sloˇzitost nejlepˇs´ıho TS, kter´y probl´em ˇreˇs´ı uvaˇzujeme TS se dvˇema p´askami, prvn´ı je read only prostorov´a sloˇzitost TS = maxim´aln´ı poˇcet pol´ı druh´e p´asky, kter´y je tˇreba popsat (v z´avislosti na d´elce vstupu) prostorov´a sloˇzitost probl´emu = opˇet optimum pˇri nedeterminismu opˇet minimum pˇres v´ypoˇcty
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
14 / 24
Sloˇzitost na TS
Landauova notace
f ∈ O(g ) – funkce f roste nejv´yˇse tak rychle, jako g (jejich pomˇer neroste do nekoneˇcna) f ∈ o(g ) – funkce f roste v´yraznˇe pomaleji, neˇz g (jejich pomˇer kles´a do nuly) f ∈ θ(g ) – plat´ı oboje v´yˇse uveden´e v´ıce nˇz
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
15 / 24
Sloˇzitostn´ı tˇr´ıdy
Sloˇzitostn´ı tˇr´ıdy dan´e konkr´etn´ı fc´ı
f je funkce DTIME (f ), DSPACE (f ), NTIME (f ), NSPACE (f ) znaˇc´ı mnoˇziny probl´em˚ u s ˇcasovou / prostorovou sloˇzitost´ı v O(f ) a to na deterministick´em / nedeterministick´em stroji DTIME (f ) ⊆ DSPACE (f ), NTIME (f ) ⊆ NSPACE (f ) DSPACE (f ) ⊆ DTIME (2f ), NSPACE (f ) ⊆ NTIME (2f )
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
16 / 24
Sloˇzitostn´ı tˇr´ıdy
Savitchova vˇeta
NSPACE (f ) ⊆ DSPACE (f 2 ) myˇslenka: m´ame orientovan´y graf konfigurac´ı TS (aˇz 2f vrchol˚ u), hled´ame cestu rekurze, p˚ ulen´ı interval˚ u
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
17 / 24
Sloˇzitostn´ı tˇr´ıdy
Obecn´e sloˇzitostn´ı tˇr´ıdy
P – polynomi´aln´ı ˇcasov´a sloˇzitost NP – nedeterministick´a obdoba P PSPACE – polynomi´aln´ı ˇcasov´a sloˇzitost NPSPACE – nepouˇz´ıv´a se (dle Savithovy vˇety spl´yv´a s PSPACE E , NE – ˇcasov´a sloˇzitost v 2O (n) EXPTIME , NEXPTIME – ˇcasov´a sloˇzitost v 2O (nk ) pro nˇejak´e k EXPSPACE
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
18 / 24
Sloˇzitostn´ı tˇr´ıdy
P=NP
jeden z Probl´em˚ u mil´enia (odmˇena milion USD) ”In a 2002 poll of 100 researchers, 61 believed the answer to be no, 9 believed the answer is yes, and 22 were unsure; 8 believed the question may be independent of the currently accepted axioms and so impossible to prove or disprove.” spousta pokus˚ u o d˚ ukaz (posledn´ı seri´ oznˇe vypadaj´ıc´ı v l´etˇe 2010)
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
19 / 24
Sloˇzitostn´ı tˇr´ıdy
NP-´upln´e probl´emy
probl´em A se polynomi´alnˇe redukuje na probl´em B pokud existuje turing˚ uv stroj ˇreˇs´ıc´ı A tak, ˇze udˇel´a polynomi´alnˇe mnoho operac´ı a polynomi´alnˇe mnohokr´at odsimuluje stroj B nad vstupem, kter´y m´a polynomi´aln´ı d´elku vzhledem k p˚ uvodn´ımu vstupu NP-tˇeˇzk´y probl´em je takov´y, ˇze se na nˇej redukuj´ı vˇsechny NP probl´emy NP-´ upln´y probl´em je NP tˇeˇzk´y NP probl´em probl´em splnitelnosti (SAT) je NP-´ upln´y
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
20 / 24
Sloˇzitostn´ı tˇr´ıdy
3-SAT
formule v konjunktivn´ı norm´aln´ı formˇe, pouze 3 liter´aly (promˇenn´a nebo nepromˇenn´a) v kaˇzd´e klauzuli SAT se redukuje na 3-SAT 2-SAT je v P
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
21 / 24
Sloˇzitostn´ı tˇr´ıdy
Subset sum
Um´ıme z dan´e mnoˇziny vybrat podmnoˇzinu s pevnˇe dan´ym souˇctem?
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
22 / 24
Sloˇzitostn´ı tˇr´ıdy
Hamiltonovsk´y cyklus
Existuje v grafu cyklus kter´y proch´az´ı kaˇzd´ym vrcholem pr´avˇe jednou.
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
23 / 24
Sloˇzitostn´ı tˇr´ıdy
Dalˇs´ı moˇzn´a rozˇs´ıˇren´ı P
ZPP – algoritmus dost´av´a n´ahodn´a data (krom vstupu), nulov´a pravdˇepodobnost chyby, pr˚ umˇern´a doba bˇehu je polynomi´aln´ı (pod NP) RP – algoritmus dost´av´a n´ahodn´a data (krom vstupu), v pˇr´ıpadˇe z´aporn´e odpovˇedi nulov´a pravdˇepodobnost chyby, v pˇr´ıpadˇe z´aporn´e omezen´a pravdˇepodobnost chyby. Pr˚ umˇern´a doba bˇehu je polynomi´aln´ı (pod NP) BPP – algoritmus dost´av´a n´ahodn´a data (krom vstupu), omezen´a pravdˇepodobnost chyby BQP – pouˇz´ıv´a kvantov´e v´ypoˇcty, jinak tot´eˇz, co BPP
Kondr (Neˇz v´ am klesnou v´ıˇ cka 2011)
Sloˇzitost
12.–16.2.2011
24 / 24
