[12] Alte Clase de Compl

Proiectarea algoritmilor: Alte clase de complexitate

Dorel Lucanu

Faculty of Computer ScienceAlexandru Ioan Cuza University, Iasi, Romania

[email protected]

PA 2014/2015

D. Lucanu (FII - UAIC) Alte clase de complexitate PA 2014/2015 1 / 25

Outline

1 co-NP

2 Clase fundamentale

3 Clase canoniceO problema PSPACE-completa


co-NP

Plan

1 co-NP




co-NP

co-probleme

Definitie

Daca P este o problema de decizie, atunci P desemneaza problemadefinita prin P(p) = P(p). Cu alte cuvinte, daca P(p) = true atunciP(p) = false si daca P(p) = false atunci P(p) = true.

Definitie

Fie C o clasa de probleme de decizie. co-C este clasa problemelor{P | P NP}.

Cazuri particulare:co-P = {P | P P}co-NP = {P | P NP}


co-NP

Exemplu

SATInstance O formula propozitionala F cu variabile din X = {x1, . . . , xn}.Question Exista o atribuire a : X {0, 1} (sau a : X {false, true})

care satisface F?

Formularea matematica a ntrebarii: (a) a(F ) = 1Intrebarea negata: (a) a(F ) = 0O formula F cu proprietatea (a) a(F ) = 0 se numeste nesatisfiabila.

SATInstance O formula propozitionala F cu variabile din X = {x1, . . . , xn}.Question Este F nesatisfiabila?

De remarcat dihotomia exists - for all.


co-NP

Exemplu

INDEPENDENT-SETInstance Un graf G = (V ,E ), un numar ntreg k 0.Question Exista o submultime U V independenta cu cel putin k

elemente?.

INDEPENDENT-SETInstance Un graf G = (V ,E ), un numar ntreg k 0.Question Este valida urmatoarea afirmatie: pentru orice submultime

U V , U nu este independenta sau are cel mult k 1elemente?.

De remarcat din nou dihotomia exists - for all.


co-NP

Exemplu

Urmatoarele probleme sunt reprezentate ca limbaje.

PRIME = {n | n este numar ntreg prim}PRIME = {n | n NU este numar ntreg prim}COMPOSITE = {n | n este numar ntreg compus}De multe ori se afirma PRIME = COMPOSITE. . . totusi 1 nu este nici prim si nici compus. . .


co-NP

co-P

Theorem

co-P = P.

Se arata ca o problema P este n P daca si numai daca este n co-NP.Exercitiu. De verificat afirmatia de mai sus.


co-NP

NP versus co-NP

NP- clasa problemelor de decize pentru care raspunsul DA estecertificat n timp polinomial

co-NP- clasa problemelor de decize pentru care raspunsul NU estecertificat n timp polinomial

de regula ntrebarile pentru problemele din NP ncep cu exista ()iar cele din co-NP ncep cu pentru toate/toti ()urmatoare problema este una tipica pentru co-NP:

TAUTOLOGYInstance O formula propozitionala F cu variabile din

X = {x1, . . . , xn}.Question Pentru toate atribuirile a : X {0, 1}, a(F ) = 1?


co-NP

NP versus co-NP

Nu se stie daca NP = co-NP.Se stie doar:

Propozitie

Daca P = NP atunci NP = co-NP.

Intersectia dintre NP si co-NP este nevida:

Propozitie

P NP co-NP.

Propozitie

O problema P este co-NP-completa daca si numai daca P esteNP-completa.


co-NP

P, NP, co-NP

PNP co-NP


co-NP

Cautare versus decizie

Reamintim:

problema de decizie: raspuns DA/NU

problema de cautare: gasirea unei solutii care da raspunsul DA

SAT:decizie: este F satisfiabila?cautare: sa se gaseasca o atribuire care satisface F .

Definitie

O problema P se numeste auto-reductibila daca versiunea sa de cautare sereduce Turing/Cook polinomial la versiunea sa de decizie.

Exercitiu. Sa se arate ca SAT este auto-reductibila.


co-NP

Cautare versus decizie

un algoritm eficient pentru cautare implica un algoritm eficient pentrudecizie;

daca problema de decizie este dificila atunci problema de cautare estedificila;

cand un algoritm eficient pentru cautare implica un algoritm eficientpentru cautare? (e.g. cazul problemelor NP-complete).


Clase fundamentale

Plan

1 co-NP




Clase fundamentale

Clase fundamentale (incomplet)

DTIME(t(n)) - clasa problemelor decise de algoritmi deterministi cucomplexitatea timp O(t(n)).

NTIME(t(n)) - clasa problemelor decise de algoritmi nedeterministi cucomplexitatea timp O(t(n)).

DSPACE(s(n)) - clasa problemelor decise de algoritmi deterministi cucomplexitatea spatiu O(s(n)).

NSPACE(s(n)) - clasa problemelor decise de algoritmi nedeterministi cucomplexitatea spatiu O(s(n)).


Clase canonice

Plan

1 co-NP




Clase canonice

Clase canonice (incomplet)

L = DTIME(log n)NL = NTIME(log n)P = DTIME(nO(1)) =

k0DTIME(n

k)

NP = NTIME(nO(1)) =

k0NTIME(nk)

PSPACE = DSPACE(nO(1)) =

k0DSPACE(nk)

NPSPACE = NSPACE(nO(1)) =

k0NSPACE(nk)

EXP = DTIME(2nO(1)) =

k0DTIME(2nk )

NEXP = NTIME(2nO(1)) =

k0NTIME(2nk )


Clase canonice

PSPACE versus NPSPACE

Teorema (Savitch, 1970)

PSPACE = NPSPACE


Clase canonice

P, NP, co-NP, PSPACE

PNP co-NP

PSPACE


Clase canonice O problema PSPACE-completa

Plan

1 co-NP





Formule booleene cuantificate

Fie F o formula booleana (propozitionala) care include variabila x .

Cuantificarea universala cu privire la x : (x)Fsemnificatie: (x)F are loc daca si numai daca pentru orice v {0, 1},F [v/x ] are loc.

Cuantificarea existentiala cu privire la x : (x)Fsemnificatie: (x)F are loc daca si numai daca exista v {0, 1}, F [v/x ]are loc.

Formula complet cuatificata: o formula prefixata cu un cuantificator (x)sau (x) pentru orice variabila x care apare n formula.Exemple:(x)(y)x y(x)(y)x y(x)(y)(z)(x y) (y (x z))Exrecitiu: Aratati ca orice formula booleana complet cuantificata este sauadevarata sau falsa.



TQBF

TQBF (True Quantified Booolean Formula)Instance O formula booleana complet cuantificata .Question Este adevarata

Teorema

TQBF este PSPACE-completa

Daca x1, . . . , xn sunt toate variabilele care apar n formula booleana F ,notam F (x1, . . . , xn).Presupunem ca este de forma Q1 . . .QnF (x1, . . . , xn), unde Qi este sau(xi ) sau (xi ).



TQBF este n PSPACE

Construim un algoritm recursiv val() astfel:

1 daca nu are cuantificatori (si deci F = nu are variabile), ntoarcevaloarea lui F

2 altfel1 A = val(Q2 . . .Qn(0, x2, . . . , xn))2 B = val(Q2 . . .Qn(1, x2, . . . , xn))3 daca Q1 (x1), atunci ntoarce A B4 daca Q1 (x1), atunci ntoarce A B

Exrecitiu: Sa se determine complexitatile timp si spatiu pentru val().



TQBF este PSPACE-dificila

Fie P o problema n PSPACE si A un algoritm care rezolva P utilizandspatiu polinomial.Peste configuratiile lui A consieram formula parametrizata c1,c2,t cusemnificatia:c1,c2,t = true daca si numai daca din configuratia c1 se poate ajunge nconfiguratia c2 in cel mult t pasi.Asociem lui A si instantei p P o formula c1,c2,t , unde:

c1 = starea initiala corespunzatoare lui p

c2 = starea finala

t = timpul dat de algoritmul A pentru rezolvarea lui p (exponential,marginit de un T )



TQBF este PSPACE-dificila

Cum poate fi calculata c1,c2,t n timp polinomial?

1 t = 1, trivial

2 t > 1 : c1,c2,t = (m)c1,m,t/2 m,c2,t/2Din pacate timpul este exponential pentru calculul formulei de mai sus.O solutie este sa o rescriem astfel ncat sa existe un singur apel recursiv:

c1,c2,t = (m)((c3, c4) {(c1,m), (m, c2)})c3,c4,t/2= (m)(m, c1, c2, c3, c4) = c3,c4,t/2= (m)(m, c1, c2, c3, c4) c3,c4,t/2


co-NPClase fundamentaleClase canoniceO problema PSPACE-completa

Date post:	18-Sep-2015
Category:	Documents
Upload:	eirdnocotim
View:	226 times
Download:	0 times

[12] Alte Clase de Compl

Documents