Curs 9

Probleme NP -complete

Algoritmi nedeterministi

Clasele P si NP

Probleme NP -dificile si NP -complete

Exemple de probleme NP -complete

Algoritmi nedeterministi

O definitie a algoritmilor nedeterministi

activitatea unui alg. ned. se desfasoara in doua etape:

• etapa de ghicire: se “ghiceste” o anumita structura

• etapa de verificare: verifica daca structura ghicita este

solutie corecta a problemei

instructiuni:

choice (S) intoarce un element

ales aleator din S

success semnaleaza terminarii

cu succes

failure semnaleaza terminarii

cu esec

Probleme de decizie

formalizare

instanta: A, B A, x A

intrebare: x B?

exemplu: problema rucsacului

instanta

• o multime de obiecte O,

• fiecare obiect are o marime s(o) Z+ si o valoare v(o) Z+

• restrictie: M Z+

• scop K Z+

intrebare

• exista O’ O a.i. oO’ s(o) M si oO’ v(o) K?

Algoritm nedeterminist pentru rucsac 0/1

procedure rucsacND(O, s, v, M, K, x)

begin

/* ghiceste */

for fiecare o O do

x[o] choice(0,1)

/* verifica */

sGhicit vGhicit 0

for fiecare o O do

sGhicit sGhicit + x[o]*s[o]

vGhicit vGhicit + x[o]*v[o]

if (sGhicit M and vGhicit K)

then success

else failure

end

Clasele P si NP

P = clasa problemelor care pot fi rezolvate de algoritmi

deterministi in timp polinomial

NP = clasa problemelor care pot fi rezolvate de algoritmi

NEdeterministi in timp polinomial

Teorema

Daca P este in NP, atunci exista polinoamele p(n) si q(n) si

un algoritm determinist care rezolva P in timpul

O(p(n)2q(n)).

Reducerea problemelor

P Q

pp. P si Q doua probleme de decizie

P Q exista o functie t astfel incat

• t transforma o instanta p P intr-o istanta t(p) Q

• t este calculata in timp polinomial

• P(p) si Q(t(p)) au aceeasi valoare

P g(n) Q daca t(p) este calculabila in timpulO(g(n))

Teorema

Presupunem P g(n) Q

1. Daca P are compl. (f(n)) atunci Q are compl. (f(n) – g(n)).

2. Daca Q are compl. O(f(n)) atunci P are compl. O(f(n) + g(n)).

Reducerea problemelor

Exemple

Reducerea problemei sortarii la problema determinarii

infasuratorii convexe

Reducerea problemei determinarii subsecventei crescatoare

maximale la problema determinarii subsecventei comune

maximale

Probleme NP-complete

P este problema NP-dificila daca pentru orice problema Q

din NP are loc Q P.

P este problema NP-completa daca:

P este in NP si

P este NP-dificila

SAT - enunt

Problema satisfiabilitatii (SAT)

instanta: o formula F din calculul propozitional in forma

normala conjuctiva si in care apar variabile din {x0, ...,xn-1}

intrebare: exista o atribuire a variabilelor pentru care F este

satisfacuta?

Teorema (Steven Cook, 1971)

SAT este NP-completa.

SAT - demonstratie

algoritm nedeterminist care rezolva SAT:

1. ghiceste o atribuire pentru variabile

2. calculeaza valoarea formulei

3. daca formula este satisfacuta intoarce success; altfel

intoarce failure.

SAT - demonstratie (cont.)

(P in NP ) P SAT

fie A care rezolva P

Se considera variabilele:

• Bijt = valoarea bitului j din locatia i la momentul t

• Skt instructiunea de eticheta k se executa la momentul t

asociem lui A pentru intrarea x formula

F(A, x) = F1 F2 F3 F4 F5 F6 unde

• F1 - starea initiala

• F2 - prima instructiune care se executa

• F3 - dupa t pasi se executa exact o instructiune

• F4 - calculul instructiunii urmatoare

• F5 - schimbarea memoriei

• F6 - terminarea cu succes

SAT - demonstratie (cont.)

1: if (x > 2)

2: then y x*x

3: else y x*x*x

4:success

locatia 0 memoreaza 2, locatia 1 memoreaza x, locatia 2 memoreaza y

starea initiala pentru x = 3

F1 = B0,0,0 ¬B0,1,0 B1,0,0 B1,1,0

prima instructiune care se executa

F2 = S1,0 ¬S2, 0 ¬S3, 0 ¬S4, 0

dupa t pasi se executa exact o instructiune

F3 = G0 G1 G2

Gt = G1,t G2,t G3,t G4,t

...

G2,t= ¬S1,t S2, t ¬S3, t ¬S4, t

....

etc

Problema U

Formulare

Instanta

• un program A, o intrare x, un intreg k > 0

Intrebare

• programul A cu intrarea x se termina cu raspunsul DA in k pasi?

U este in NP

construim un algoritm U care simuleaza k pasi ai lui A si se termina cu DA daca si numai daca A se termina cu DA in cei k pasi

U este in NP-dificila

daca Q este in NP, atunci exista un alg. nedet. A care rezolva Q

transformam o instanta q Q de dimensiune n intr-o instanta (A, q, TA(n))

Exemple de probleme NP-complete

SAT

3SAT

Rucsac 0/1

Submultime de suma data

V-acoperire (VA)

instanta: un graf G = (V, E), K Z+

intrebare: exista o V-acoperire V’ a.i. #V’ K?

Circuit Hamiltonian intr-un digraf (CHD)

instanta: un digraf D = (V, A)

intrebare: exista un circuit Hamiltonian?

Circuit Hamiltonian intr-un graf (CHG)

Exemple de probleme NP-complete (continuare I)

Comis voiajor (CV)

instanta: un graf ponderat G = (V, E, c), c({i,j}) Z+, K

Z+

intrebare: exista un circuit Hamiltonian de cost K?

Planificare procesoare (PP)

instanta: o multime P de programe, m procesoare, un timp

de executie t(p) pentru fiecare program p, un termen D

intrebare: exista o planificare a procesoarelor pentru P a.i.

orice program sa fie executat in termenul D?

Exemple de probleme NP-complete (continuare II)

Congruente patratice (CP)

instanta: a, b, c Z+

intrebare: exista 0 < x < c a.i. x2 mod b = a ?

Ecuatii diofantice patratice

instanta: a, b, c Z+

intrebare: exista x, y Z+ a.i. ax2 + by = c ?

Cum se arata NP-completitudinea

reducere

daca P este in NP, Q este NP-completa si Q P

atunci P este NP-completa

exemplu: SAT 3SAT

• c = u1

c' = (u1 y1 y2)(u1 y1' y2) (u1 y1 y2') (u1 y1' y2')

• c = u1 u2

c' = (u1 u2 y1)(u1 u2 y1')

• c = u1 u2 u3 u4

c' = (u1 u2 y1)(u3 u4 y1')

3SAT VA

VA CHG

Cum se arata NP-completitudinea (cont.)

restrictia

daca Q este NP-completa si Q este caz special al lui P

atunci P este NP-completa

exemplu: CHG caz special al lui CHD

Alte clase

PSPACE = clasa problemelor care sunt rezolvate de algoritmi

deterministi in timp nelimitat si utilizand spatiu polinomial

NPSPACE = clasa problemelor care sunt rezolvate de algoritmi

NEdeterministi in timp nelimitat si utilizand spatiu polinomial

PSPACE = NPSPACE (Savitch, 1970)

problema co-P:

aceleasi instante ca P dar raspunde DA daca P raspunde NU

si raspunde NU daca P raspunde DA

co-NP = clasa problemelor co-P cu P in NP

Alte clase

P

co-NPNP

PSPACE

NP

complete

co-NP

complete

descopunerea

in factori primi

Bibliografie suplimentara

An Annotated List of Selected NP-complete Problems

http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html