NP Completitudine

C Clasificarea problemelor din perspectiva complexitii procesului de rezolvareCursul caracterizeaz problemele din punctul de vedere al naturii procesului de rezolvare i, implicit, al dificultii rezolvrii. Definiia C.12 Spunem c un algoritm este determinist dac fiecare operaie coninut, de control sau de prelucrare a datelor, are un rezultat unic determinat. Caracteristica esenial este serialitatea algoritmului. Execuia unui algoritm determinist, pentru o instan dat a problemei rezolvate, conduce la o secven a operaiilor efectuate, astfel nct pentru orice moment de timp t din cursul execuiei exist o singur operaie derulat la momentul t. Mulimea operaiilor efectuate n cursul rezolvrii este echipotent cu mulimea momentelor de timp la care sunt executate aceste operaii. Prin urmare, comportarea algoritmului poate fi descris printr-o funcie TimpOperaii pentru fiecare instan a problemei rezolvate. Definiia C.13 Un algoritm este nedeterminist dac are operaii al cror rezultat nu este unic definit ci este o valoare dintr-o mulime finit de posibiliti. Caracteristica esenial este paralelismul nerestricionat al algoritmului. Execuia unui algoritm nedeterminist, pentru o instan dat a problemei rezolvate, conduce la o structur arborescent de operaii. Operaiile de pe o cale din arbore sunt efectuate serial, n timp ce operaiile de pe ci diferite sunt efectuate n paralel. Execuia algoritmului pentru o instan a problemei rezolvate nu mai poate fi descris printr-o funcie TimpOperaii, ci printr-o o relaie peste mulimea Timp Operaii. Pentru a construi algoritmi nedeterminiti introducem urmtoarele operaii: choice(A), unde A este o mulime finit de valori, construiete, pentru fiecare valoare x din A, o copie a algoritmului executat, copie ce conine copii ale tuturor variabilelor algoritmului cu valorile avute n momentul execuiei choice(A). Copiile algoritmului sunt executate n paralel i independent una fa de celelalte. Complexitatea operaiei choice este (1), iar rezultatul rentors pentru copia algoritmului corespunztoare valorii x din A este chiar x. fail termin cu insucces execuia copiei algoritmului n care se afl. Celelalte copii aflate n execuie ale algoritmului nu sunt afectate. Complexitatea operaiei este (1). success termin cu succes execuia copiei algoritmului n care se afl i a tuturor celorlalte copii. Execuia ntregului algoritm este terminat. Complexitatea operaiei este (1). Un algoritm nedeterminist se termin cu succes doar dac exist o operaiesuccess efectuat n cursul execuiei algoritmului. Algoritmul se termin cu insucces atunci cnd toate copiile algoritmului se termin prin fail. Individual, success i fail

nu au rezultat. Prin convenie, un algoritm nedeterminist terminat cu succes rentoarce valoarea 1; dac algoritmul se termin cu insucces valoarea rentoars este 0.

2

Cristian Giumale/ Note de curs

Un algoritm nedeterminist Alg asociat unei probleme Q:I{0,1} emuleaz procesul de ghicire a cii cu complexitate minim corespunztoare rezolvrii problemei Q. Pentru date de intrare iI fixate, astfel nct Alg(i)=1, complexitatea algoritmului se definete ca sum a complexitii operaiilor din calea cu complexitate minim care termin algoritmul cu success. Astfel msurat, complexitatea se numete angelic. Spunem c un algoritm nedeterminist are complexitate angelic limitat de o funcie f:R+, dac pentru orice date de intrare iI de dimensiune n, astfel nct Alg(i)=1, complexitatea angelic a algoritmului pentru datele i este (f(n)). Exemplul C.5 Fie ecuaia Ec(x) = 0. Care dintre urmtoarele soluii este corect: (1) x = val1; (2) x = val2; (3) x = val3 ... (n) x = valn.// Algoritm determinist ecuaie(val,n) { x = Rezolvare(Ec); for(i=1; in; i++) if(x = vali) return i; } // Algoritm nedeterminist N_ecuaie(val,n) { i = choice(1..n); if(Ec(vali)0){print i; success;} fail; }

Rezolvarea determinist impune cunoaterea rezolvrii ecuaiei Ec(x)=0. Rezolvarea nedeterminist impune doar cunoaterea operaiilor folosite n ecuaie, iar complexitatea este (4)+Timp_verificare(Ec). Dac algoritmul N_ecuaie este rescris ca un algoritm determinist, complexitatea devine (n)*Timp_verificare(Ec) fa de (n)+Timp_rezolvare(Ec), ct cere algoritmul ecuaie. Exemplul C.6 Fie A un vector cu n ntregi strict pozitivi. S se sorteze elementele vectorului A. Algoritmul nedeterminist de sortare construiete permutrile elementelor din A, plasnd fiecare element ntr-un vector auxiliar B. Restricia Ai>0, i=1,n, ajut la determinarea uoar a poziiilor deja ocupate din B. La fiecare operaie choice, algoritmul i vectorul B sunt duplicate. n final, rezultatul sortrii este tiprit.N_sort(A,n) { for(i = 1; i n; i++) B[i] = 0; // Generare soluie potenial for(i = 1; i n; i++) { // Poziionare Ai n vectorul B. Ignorm construcia // mulimii 1..n care nu mrete complexitatea N_sort j = choice(1..n); if(Bj 0) fail; B j = A i; } // Test final sortare for(i= 1; i < n; i++) if(Bi > Bi+1) fail; print(B,n); success; }


3

A1 B1 Bj

Bn

Aj Bk

poziionare Aj n B

B1 success

Bn

An

fail

B1

Bm

Bn

verificare ordine B

success

Figura C.3 Execuia algoritmului nedeterminist N_sort Dei complexitatea temporal a algoritmului este (n), spaiul total consumat pare a fi proporional cu n!. Totui, considernd execuia unui algoritm nedeterminist ca proces de ghicire i execuie a unei ci cu complexitate minim din arborele execuiei algoritmului, complexitatea spaial a algoritmului se limiteaz la complexitatea spaial a acelei ci. De exemplu, pentru algoritmul de sortare nedeterminist complexitatea spaial este (n lg(n)). Exemplele date sugereaz c rezolvarea unei probleme cu un algoritm nedeterminst are dou faze: 1. Construcia concurent a soluiilor poteniale. O soluie potenial nu este n mod necesar o soluie a problemei. Construcia este efectuat fr a ine seama de proprietile impuse soluiilor i, de aceea, poate fi asemnat cu un proces de ghicire. 2. Verificarea serial a fiecrei soluii poteniale construite n faza (1). Se testeaz dac soluia potenial satisface proprietile cerute de problem, deci dac, ntr-adevr, este o soluie a problemei. Complexitatea verificrii influeneaz esenial complexitatea ntregului algoritm nedeterminist.

4


Similar cu caracterizarea algoritmilor din punctul de vedere al execuiei, putem clasifica problemele n raport cu natura algoritmilor de rezolvare. Prin convenie, spunem c natura unei probleme este: Determinist poate fi rezolvat printr-un complexitate polinomial (rezolvarea este tractabil). algoritm determinist cu

Nedeterminist dac poate fi rezolvat printr-un algoritm nedeterminist cu complexitate polinomial i nu exist un algoritm de rezolvare determinist cu aceeai proprietate. Deoarece algoritmii determiniti sunt cazuri particulare ale celor nedeterminiti, clasa problemelor nedeterministe include pe cea a problemelor deterministe. O perspectiv alternativ a problemelor deterministe i nedeterministe se bazeaz pe legtura intuitiv ce exist ntre natura algoritmilor de rezolvare i modul de calcul al predicatului de navigare n spaiul strilor problemei rezolvate. Definiia C.14 Fie GQ={S,E} spaiul strilor unei instane oarecare a unei probleme decizionale Q: GQ este un graf orientat cu nodurile (strile S) i arcele (tranziiile valide) E S S. Fie T: E{0,1} un predicat de navigare n spaiul strilor, iar MT = {xE | x duce spre o soluie a problemei} mulimea de adevr a lui T. Problema Q este determinist dac valoarea T(x) poate fi calculat fr a enumera elementele MT. Algoritmul care calculeaz T(x) nu folosete un generator al mulimii MT pentru a decide dac x este n MT. MT este tratat ca mulime recursiv. Problema Q este nedeterminist dac valoarea T(x) este calculabil prin enumerarea elementelor din MT, deci pe baza unui generator al lui MT. Pentru fiecare soluie generat a problemei se testeaz dac x face parte din soluie. MT este tratat ca mulime recursiv-numrabil. Imposibilitatea sau dificultatea calculului apriori (fr a investiga spaiul strilor problemei) al mulimii MT conduce la varianta, potenial mai eficient, a strbaterii n paralel a diverselor ci din spaiul strilor problemei (sau a ghicirii drumului celui mai scurt pn la soluie), deci la un algoritm nedeterminist. Pentru o problem rezolvabil mecanic, definiia (C.14) caracterizeaz, implicit, complexitatea rezolvrii problemei. Pe o main de calcul serial, care execut o singur operaie la un moment dat, navigarea n spaiul strilor unei probleme deterministe este mai rapid dect navigarea n spaiul strilor unei probleme nedeterministe. Pentru o problem determinist arcul curent ales pentru avans conduce cert la soluie. Nu sunt necesare reveniri i apoi noi avansuri. Pentru o problem nedeterminist, determinarea arcelor care pleac dintr-un nod i duc spre soluie se efectueaz prin ncercarea de a strbate arcele, ntr-o ordine oarecare sau o ordine aleas (n funcie de euristici de rezolvare). Eecul conduce la revenirea n nod i continuarea procesului de rezolvare cu alt arc.


5

De exemplu, s considerm spaiul strilor din figura C.4, unde soluia este un drum de la starea iniial s0 la o stare final sf. Dac problema este nedeterminist decizia "arcul (si,sj) face parte din soluie?" impune explorarea subgrafului Gj. Dac soluia este gsit, arcul (si,sj) este implicit marcat ca fiind n soluie. Altfel, are loc revenirea la si, urmat de parcurgerea altui arc. n cazul unei probleme deterministe, avansul pe arcul (si,sj) are loc doar dac el face parte din soluie.s0

si

(si,sj) face parte din soluie? Gj

sj

sf

Figura C.4 Spaiul strilor unei probleme Dac spaiul strilor este un arbore de ordin m cu nlimea h, iar problema este determinist, rezolvarea cere un timp (h). Dac problema este nedeterminist, atunci rezolvarea cu un algoritm serial (determinist) cere un timp (mh). n general, dac o problem este rezolvabil n timp t1 cu un algoritm nedeterminist Alg i n timp t2 cu un algoritm determinist rezultat din rescrierea lui Alg, atunci t1 t2. ntr-adevr, algoritmul determinist, simuleaz operaia choice prin avans i revenire (backtrack) pentru a strbate toate drumurile parcurse n paralel de algoritmul nedeterminist, deci lungimea total a drumului parcurs n spaiul strilor va fi, n cazul cel mai defavorabil, suma lungimilor drumurilor parcurse de algoritmul nedeterminist. Definiia (C.14) nu impune n mod necesar terminarea procesului de rezolvare, deci decidabilitatea problemei, ci doar terminarea ct mai rapid a algoritmului n cazul n care problema accept soluie pentru datele de intrare. Conceptele de determinism i nedeterminism nu trebuie confundate cu cele de decidabilitate i semidecidabilitate. Decidabilitatea i semi-decidabilitatea sunt proprieti intrinseci ale problemelor i caracterizeaz rezolvabilitatea lor mecanic. Determinismul i nedeterminismul caracterizeaz tehnica de rezolvare i, implicit, complexitatea problemelor rezolvabile mecanic. Un algoritm nedeterminist privete tranziiile (arcele) din spaiul strilor problemei rezolvate ca i cum ar fi valori ale unei mulimi recursiv-

6


numrabile, valori ce pot fi obinute prin generare (concurent). Considernd spaiul strilor problemei finit local (aa cum cere operaia choice) i fr drumuri de lungime infinit, atunci mulimea tranziiilor posibile este recursiv, deci problema, rezolvat nedeterminist pentru o dimensiune finit a datelor, este decidabil. Cu ce efort de calcul, este o alt problem discutat n urmtoarea seciune.

NP-completitudineClasificarea problemelor efectuat conform definiiilor de mai sus este calitativ. Ne intereseaz n ce msur o problem poate fi rezolvat cu efort acceptabil, cuantificabil cantitativ. Evident, ne intereseaz acest aspect pentru problemele care pot fi rezolvate efectiv cu calculatorul, deci din punctul de vedere al problemelor decidabile. n cele ce urmeaz, efortul de rezolvare este privit ca timp de rezolvare. Definiia C.15 O problem este: Tractabil (determinist) dac poate fi rezolvat folosind un algoritm determinist tractabil. Un algoritm tractabil are complexitate polinomial: dac n este dimensiunea problemei, timpul de rezolvare este (nk), unde k este o constant. Similar, spunem c problema este tractabil nedeteriminist dac poate fi rezolvat folosind un algoritm nedeterminist tractabil (cu complexitate angelic polinomial). Intractabil dac toi algoritmii determiniti de rezolvare au complexitate supra-polinomial (dac n este dimensiunea problemei, timpul de rezolvare este (kn), unde k este o constant). Noiunea de tractabilitate este discutabil. Astfel complexitatea n100 este uria, chiar pentru supercalculatoarele contemporane. Pentru o main cu 1010 operaii pe secund i pentru n=100 sunt necesare 10190 secunde. Tractabilitatea, aa cum este definit mai sus, este acceptabil comparativ i mai ales atunci cnd gradul polinomului este modest. Chiar i aa, exist probleme rezolvabile teoretic n timp supra-polinomial, dar care pentru aplicaiile practice uzuale accept soluii cu performane acceptabile. Un exemplu este problema sintezei de tip n limbajele funcionale, a crei complexitate este exponenial. Totui, n practic, algoritmii de sintez de tip se comport suficient de bine, cazurile "dificile" de sintez fiind rare n programarea funcional de rutin. Definiia C.16 n funcie de natura algoritmilor de rezolvare i complexitatea acestora, problemele de decizie (notate Dec) pot fi divizate n dou mari clase: P = {QDec | exist algoritmi determiniti tractabili care rezolv Q}. NP = {QDec | exist algoritmi nedeterminiti tractabili care rezolv Q}.

Intuitiv, clasa P (sau PTIME) corespunde problemelor deterministe tractabile, n timp ce clasa NP (sau NPTIME) include n plus problemele nedeterministe tractabile, rezolvabile determinist n timp supra-polinomial. Orice problem determinist poate fi privit i din perspectiv nedeterminist, de unde rezult urmtoarea teorem.

Cristian Giumale/ Note de curs Teorema C.2 P NP.

7

Fie QP, o problem rezolvabil printr-un algoritm determinist cu complexitate polinomial. nseamn c algoritmul strbate un drum de lungime polinomial n spaiul strilor problemei. Evident, se poate construi un algoritm nedeterminist care la execuie urmeaz, printre alte ci, i calea de lungime polinomial parcurs de algoritmul determinist. Deci algoritmul nedeterminist are complexitate polinomial.

iI1

F

F(i)I2 Q1

Q2

r{0,1}

Figura C.5 Reductibilitatea problemelor Definiia C.17 Fie Q1 i Q2 dou probleme abstracte de decizie. Se spune c problema Q1 este reductibil n timp polinomial la problema Q2 (relaie notat Q1 p Q2) dac exist un algoritm F, determinist i cu complexitate polinomial, care transform problema Q1 n Q2, aa cum se sugereaz n figura C.5. n fapt, F transform datele iI1 ale lui Q1 n date F(i)I2 pentru Q2 astfel nct:iI1 (Q1(i)=1 Q2(F(i))=1)

Lema C.1 Dac Q2P i Q1 p Q2 atunci Q1P. Dac Q2 P, iar m este dimensiunea datelor lui Q2, atunci exist un algoritm determinist A2 cu complexitate (mk) care rezolv Q2. S presupunem c n este dimensiunea datelor lui Q1, iar (nr) este complexitatea lui F, k i r fiind constante. Se poate construi algoritmul A1(i){return A2(F(i))} a crui complexitate este (nr)+ (mk) = (nr+nrk). ntr-adevr, F(i) nu poate produce date cu o dimensiune mai mare dect (nr) ntr-un timp (nr). Cu alte cuvinte, dimensiunea datelor primite de algoritmul A2 este m = (nr) Lema C.2 Relaia de reducere polinomial p este tranzitiv. Fie Q1, Q2 i Q3 probleme cu date de tip I1, I2 i, respectiv, I3 astfel nct s avem Q1 p Q2 i Q2 p QC.Q1 F23 F23(F12(i1)) Q3 r{0,1}

i1I1

F13 F12

Figura C.6 Tranzitivitatea relaiei p

8


a) Conform definiiei (C.17) exist un algoritm F12 care transform i1I1 n i2I2 n timpul polinomial (nr), unde n este dimensiunea datelor i1 ale lui Q1. De asemenea, exist un algoritm F23 care transform i2 n i3I3 n timpul polinomial (mk), unde m este dimensiunea datelor i2 ale lui Q2. Fiind determinist, algoritmul F12(i1) nu poate produce date i2 cu o dimensiune m mai mare dect (nr) ntr-un timp (nr). Rezult c algoritmul F13(i1) = F23(F12(i1)) transform i1 n i3 n timpul (nr)+ (mk) = (nr+nkr). Deci algoritmul F13 este determinist i tractabil. b) Din relaiile de reductibilitate Q1 p Q2 i Q2 p Q3 rezult proprietatea: iI1 (Q1(i1)=1 Q3(F13(i1))=1). n final, conform definiiei (C.17), din (a) i (b) rezult Q1 p Q3 Definiia C.18 O problem Q este: NP-dur dac pentru orice problem Q'NP avem Q'pQ. NP-complet dac Q este NP-dur i Q NP. Proprietatea de completitudine asociat unei probleme Q dintr-o clas de complexitate C arat c problema respectiv este dintre "cele mai complicate" probleme din C, astfel nct, dac Q ar face parte dintr-o clas de complexitate C' inferioar lui C, atunci toate problemele din C ar fi n C'. n particular, dac o problem NP-complet ar putea fi rezolvat folosind un algoritm determinist cu complexitate polinomial atunci P = NP. Teorema C.3 O problem Q2 este NP-dur dac i numai dac exist o problem NP-complet Q1 astfel nct Q1 p Q2. a) Fie Q1 NP-complet astfel nct Q1 p Q2. Q1NP i Q' p Q1 pentru orice Q'NP . Relaia p este tranzitiv, deci Q' p Q2. Q2 este NP-dur. b) Fie Q2 NP-dur. Deoarece pentru orice Q1NP avem Q1 p Q2 putem alege Q1 NP-complet. Teorema C.4 Problemele NP-complete formeaz o clas de echivalen n raport cu relaia p. Fie Q1 i Q2 probleme NP-complete. Conform definiiei (C.18), avem: a) Q'NP Q' p Q1. Dar Q2 NP, deci Q2 p Q1 b) Q'NP Q' p Q2. Dar Q1 NP, deci Q1 p Q2 Teorema C.5 Dac exist o problem NP-complet Q, Q P, atunci P = NP. Conform definiiei (C.18), QNP-complete impune ca pentru orice Q'NP s avem Q' p Q. Dac Q P atunci, prin lema (C.1), rezult Q'P. Obinem NP P i, prin teorema (C.2), P NP, deci P = NP.


9

Corolarul C.1 Dac exist o problem NP-complet Q, astfel nct Q P atunci toate problemele NP-complete sunt n P. Cu alte cuvinte, dac exist o problem NP-complet rezolvabil printr-un algoritm determinist tractabil, atunci toate problemele NP-complete pot fi rezolvate determinist n timp polinomial. Corolarul rezult direct din teoremele (C.4) i (C.5) Teorema C.6 Dac exist o problem Q NP-dur i Q P, atunci P = NP. Conform teoremei (C.3), exist Q' NP-complet astfel nct Q' p Q, iar prin lema (C.1) dac QP atunci Q'P. Deci, conform teoremei (C.5) NP = P. Corolarul C.2 Dac exist o problem NP-dur Q, astfel nct Q P atunci toate problemele NP-complete sunt n P. Dac exist o problem NP-dur QP, din teorema (C.6) avem P=NP. Conform definiiei (C.18), problemele NP-complete sunt n clasa NP i, n acest caz, sunt n P. Se observ c problemele NP-dure nu formeaz o clas de echivalen, aa cum se ntmpl n cazul problemelor NP-complete. Totui, o problem NP-dur poate fi util pentru stabilirea clasei de complexitate a altei probleme. Pentru a demonstra c o problem Q este NP-complet (sau doar NP-dur) este necesar s se arate c: a) Pentru orice problem Q'NP exist relaia Q'p Q. Un mod mai simplu de a verifica aceast proprietate const n construcia unui algoritm determinist i tractabil F care reduce o problem Q", deja cunoscut ca NP-dur sau NP-complet, la Q. Din relaia Q"p Q i din Q"NPC, adic Q'NP Q'p Q", prin tranzitivitatea relaiei p rezult c toate problemele din NP sunt reductibile n timp polinomial la Q. b) Exist un algoritm nedeterminist de rezolvare n timp polinomial a problemeiQ, deci QNP. Se construiete efectiv algoritmul nedeterminist.

Etapa (a) stabilete NP-duritatea problemei Q, conform teoremei (C.3), i impune cunoaterea unei probleme NP-dure sau NP-complete. Totodat, este cea mai complicat faz a demonstraiei. Etapa (b), n conjuncie cu etapa (a), stabilete NP-completitudinea problemei Q. n urma discuiei topologia teritoriului problemelor decizionale poate fi imaginat ca n figura C.7. Este doar o variant posibil. Se cunosc multe probleme NPcomplete i NP-dure (marea mas a celor cu aplicabilitate practic), dar - pn n prezent - pentru nici o problem NP-complet sau NP-dur nu s-a descoperit un algoritm de rezolvare determinist i tractabil. Totui, nu s-a demonstrat c asemenea algoritmi nu pot exista. Dei nu se poate afirma riguros dac P NP, se bnuiete c relaia este adevrat. Din acest punct de vedere, ncadrarea unei probleme Q n clasa NPC (NP-complete) sau NPD (NP-dure) evit cutarea unei rezolvri tractabile care ar exista doar dac P=NP. n asemenea cazuri, o cale spre tractabilitate const n

10


acceptarea unei soluii aproximative cu un factor de aproximare cert sau garantat cu o probabilitate acceptabil.NP-complete

NP P NPC

NPD

NP-dure

Figura C.7 O structur posibil a spaiului problemelor de decizie Clasificarea din aceast seciune s-a concentrat asupra complexitii temporale a algoritmilor, dar conceptele de compeltitudine i duritate sunt valabile i pentru complexitatea spaial i, de asemenea, pentru alte clase de complexitate aa cum sunt cele din ierarhiaLOGSPACE NLOGSPACE PTIME NPTIME PSPACE = NPSPACE


11

Verificarea duritii unei problemeConform teoremei (C.3) pentru a verifica dac o problem Q este NP-dur este suficient s artm reductibilitatea polinomial Q'pQ, unde Q' este o problem NPdur sau NP-complet. n plus, dac Q are un algoritm de rezolvare nedeterminist cu complexitate polinomial nseamn c Q este NP-complet. Esenial este probarea NP-duritii, care arat c problema nu are soluie determinist i tractabil cunoscut. Seciunea conine exemple de verificare a apartenenei unor probleme la clasele NP-complete i NP-dure. Primul exemplu trateaz un caz teoretic extrem, cel al problemei terminrii algoritmilor (programelor), problem nedecidabil. Celelalte exemple au importa practic, problemele analizate constituind ierarhia din figura C.8. n cadrul discuiei este interesant reducerea unei probleme la alt problem, mai ales atunci cnd problemele par foarte diferite, aa cum este cazul determinrii unei clici de dimensiune dat ntr-un graf neorientat versus problema SAT.2SATP

3SATNPC

SATNPC

k-ClicNPC

k-AcoperireNPC

Figura C.8 Ierarhia problemelor analizate

Problema k-clicii unui grafDefiniia C.20 Fie un graf neorientat G = (V,E) cu nodurile V i arcele E. O kclic a lui G (o clic de dimensiune k) este un subgraf G'=(V',E') complet al lui G astfel nct card(V')=k (G' este complet dac pentru orice uV'i vV', (u,v)E'). Exist o definiie echivalent a k-clicii: un subgraf cu k noduri i k(k-1)/2 arce. ntr-adevr, s numerotm cu v1,v2,...,vk nodurile din k-clic. Nodul v1 contribuie cu k-1 arce ctre cele k-1 noduri rmase; nodul v2 contribuie cu k-2 arce; n general, nodul vj contribuie cu k-j arce. Deci numrul total de arce din k-clic este 1+2+...+k-1 = k(k-1)/2. De exemplu, graful din figura C.9 are 5 clici cu un nod (nodurile), 6 clici cu dou noduri (arcele) i 2 clici de dimensiune 3 cu nodurile {a,b,c} i {b,c,e}.

12


a

c

d

b

e

Figura C.9 3-clici ntr-un graf Notm k-Clic problema: s se determine dac un graf G conine cel puin ok-clic.

Teorema C.8 Problema k-Clic este NP-complet. Demonstraia are dou etape: a) Artm c problema k-Clic este n NP, deci exist un algoritm nedeterminist de rezolvare n timp polinomial; b) Alegem o problem NP-complet, fie ea SAT, i demonstrm reductibilitatea polinomial SAT p k-Clic. a)k-Clic este n NP.

Construim algoritmul nedeterminist N_k-Clic. Complexitatea algoritmului este (k2). ntr-adevr, execuia algoritmului poate fi reprezentat ca un arbore n care secvena de verificare a k-clicii este pe nivelul k, complexitatea unei cii de la rdcin la nivelul k fiind (k2)1. Dac graful este reprezentat printr-o matrice de adiacen, operaia (u,v)E dureaz (1), iar complexitatea testului k-clicii este, de asemenea, (k2), atunci cnd exist soluie. Cum kn, n= card(V), complexitatea algoritmului este limitat la (n2).N_k-Clic(G,k){ fie V nodurile, iar E arcele grafului G; V' = ; // Nodurile k-clicii for(i=1; i k; i++) { u = choice(V); if(u V') fail; V' = V' {u}; } // V' formeaz o clic? for-each(u V') for-each(v V') if(u v (u,v) E) fail; success; }1 Se consider c testul u V' este secvenial.


13

Observaie. Folosind algoritmul decizional N_k-Clic putem rezolva problema max-Clic a clicii de dimensiune maxim dintr-un graf. Algoritmul nedeterminist N_max-Clic are complexitate (n3).N_max-Clic(G) { fie n numrul nodurilor din graful G; for(k=n; k > 0; k--) // Test existen k-clic n G if(N_k-Clic(G,k)) break; return k; }

b)

SAT p k-Clic.

Fie F = T1 T2 ... Tk o formul CNF. Considerm Var mulimea variabilelor din F, iar n = card(Var). Construim un graf neorientat GF=(V,E), echivalent formulei F, astfel: V = {,i | Ti, unde =x sau = x, cu xVar, este un literal din Ti} Nodurile grafului sunt dublei ,i, unde este un al formulei F (o variabil sau o variabil negat), iar i este indicele termenului din F n care apare . E = {(,i , ,j) | ,i V ,jV i j}

Prin convenie, notaia nseamn: literalii i nu pot fi unul x, iar cellalt x, pentru xVar. n schimb, i pot fi identici sau pot conine variabile diferite. Aadar, arcele grafului pot fi doar ntre noduri cu literali din termeni diferii i doar dac literalii sunt identici sau corespund unor variabile diferite. De exemplu, graful GF ilustrat n figura C.10 (i care are dou 3-clici: {a,1,b,2,a,3} i {a,3,b,1,b,2}) corespunde formulei:F = (a b) (a b) (a b) ______ _______ _______ T1 T2 T3

.a,1 a,2 a,3

b,1

b,2

b,3

Figura C.10 Graful asociat formulei F

14


S artm c graful GF poate fi construit cu un algoritm determinist n timp polinomial n raport cu numrul variabilelor din F. Fie algoritmul de conversie F -> GF:construcie_GF(F) { fie T = {T1,T2,...,Tk} termenii formulei F; V = ; // nodurile din GF E = ; // arcele din GF // Construcia nodurilor lui GF for(i=1; i k; i++) for-each(Ti) V = V {,i}; // Construcia arcelor lui GF for-each(,i V) for-each(,j V) if( i j) E = E {(,i,,j)}; return (V,E); }

Pentru c fiecare variabil din cele n poate s apar de cel mult dou ori ntr-un termen, numrul literalilor dintr-un termen este limitat2 la 2n. Rezult c ciclul de construcie a nodurilor lui GF are complexitatea (kn), iar construcia arcelor are complexitatea (k2n2). Rezult o complexitate a algoritmului polinomial n n i k. De asemenea, considernd numrul termenilor limitat polinomial n raport cu n, complexitatea algoritmului construcie_GF este polinomial n funcie de n. Putem arta acum c satisfiabilitatea formulei F este nrudit cu problema kClic.

Lema C.3 O formul CNF F cu k termeni este satisfiabil dac i numai dac graful GF are o k-clic.F este satisfiabil GF are o k-clic.

Dac F este satisfiabil atunci n fiecare termen Ti, i=1,k, exist cel puin un literal cu valoarea de adevr 1. Fie V'= U {,i | Ti =1} o submulime cuk noduri din GF, astfel nct V' s conin un singur element ,i pentru termenul Ti, i=1,k.i= 1 k

S alegem la ntmplare dou noduri distincte ,i i ,j din V'. n mod sigur i j i observm c . De exemplu, dac = i = x, xVar, atunci = 1 implic x = 1 i ar nsemna c = x = 0, ceea ce contrazice modul de construcie a lui V', pentru c trebuie s fie 1. Similar, dac = i = x, xVar, atunci = 1 implic x = 0 i ar nsemna c = x = 0.

2 n particular, problema 3SAT,

unde termenii din formul au cel mult cte trei literali

distinci, este NP-complet.


15

Rezult c arcul (,i, ,j) satisface i j i , deci este un arc din graful GF. Prin urmare, nodurile V' formeaz o k-clic n GF.GF are o k-clic F este satisfiabil.

Fie V' nodurile dintr-o k-clic a grafului GF. Pentru c arcele grafului nu pot fi dect ntre noduri ,i i ,j cu ij, fiecare termen din formula F este reprezentat n V' de ctre un singur nod din V i, implicit, de ctre cel puin un literal. De asemenea, pentru oricare dou noduri ,i i ,j din V' avem . S construim mulimea literalilor S = { | i1..k ,iV'}. Mulimea S respect restricia: pentru oricare literali distinci i din S exist proprietatea . Prin urmare, pentru orice variabil x prezent n literalii din nodurile V'i, implicit, n mulimea S exist un singur literal care conine variabila x: fie = x, fie = x. Pentru fiecare variabil x din formula F asociem o valoare de adevr conform regulilor: x = 1, dac x face parte dintr-un literal S i literalul are forma = x. Toi literalii din S care conin variabila x au valoarea de adevr 1. x = 0, dac x face parte dintr-un literal S i literalul are forma = x,. Toi literalii din S care conin variabila x au valoarea de adevr 1. x = orice valoare din {0,1}, dac x nu face parte din niciun literal din S.

Deoarece asocierile variabil-valoare conforme regulilor de mai sus satisfac toi literalii din S i fiecare termen din F are cel puin un literal n S, rezult c F este satisfiabil. Din lema (C.3) i din construcia algoritmului construcie_GF obinem imediat SAT p k-Clic. Deoarece k-Clic NP, rezult c problema este NP-complet.

Acoperirea unui graf neorientatDefiniia C.21 Fie G=(V,E) un graf neorientat cu nodurile V i arcele E, iar V' V o submulime de noduri din G. V' este o k-acoperire a grafului G dac: pentru orice arc (u,v)E avem {u,v} V' ; card(V') = k.

O k-acoperire este minim pentru k minim. n cazul grafului din figura C.11(b) o acoperire minim este {a,d}. S numim k-Acoperire problema decizional: fiind dat un graf neorientat G i un ntreg k >0 s se determine dac G are o k-acoperire.

16


a

c

a

c

d

b (a)

e

d

b (b)

e

Figura C.11 Un graf (a) i complementarul su (b) Teorema C.9 Problema k-Acoperire este NP-complet. a) S artm c problema k-Acoperire este n NP, deci exist un algoritm nedeterminist i tractabil de rezolvare.N_k-Acoperire(G,k) { fie V nodurile, iar E arcele grafului G; V' = ; // Nodurile k-acoperirii // Construcie k-acoperire potenial for(i=1; i k; i++) { u = choice(V); if(u V') fail; V' = V' {u}; } // V' conine k noduri diferite din V. Formeaz o acoperire? for-each(u V) for-each(v V) if((u,v)E uV' vV') fail; success; }

Este uor de observat c algoritmul N_k-Acoperire are complexitatea (k2)+(kn2) pentru cutare liniar uV', uV'i vV'. b) Alegem o problem NP-complet, fie ea k-Clic, i demonstrm reductibilitatea polinomial k-Clic p k-Acoperire. Definiia C.22 Fie G=(V,E) un graf neorientat, iar G =(V, E ) un graf cu arcele E = {uV,vV | (u,v)E (u,v)} (arcele unui graf complet cu nodurile V din care se elimin E). Graful G este complementarul lui G. n figura C.11 este reprezentat un graf i complementarul su. Reducem problema k-Clic pentru graful G=(V,E) la problema (n-k)Acoperire pentru graful G =(V, E ), unde n=card(V). Reducerea nseamn n primul rnd construcia grafului complementar.

Cristian Giumale/ Note de cursconstrucie_ G (G) { fie V nodurile grafului G; fie E arcele grafului G; E = ; for-each(u V) for-each(v V) if((u,v)E uv) E = E {(u,v)}; return (V, E ); }

17

Construcia este n timp polinomial n raport cu n=card(V). Pentru a finaliza demonstraia k-Clic p(n-k)-Acoperire trebuie s artm c cele dou probleme sunt echivalente. Lema C.4 Fie un graf neorientat G. G are o k-clic dac i numai dac G are o (n-k)-acoperire.G are o k-clic G are o (n-k)-acoperire.

Fie V' o k-clic a lui G. S alegem la ntmplare un arc (u,v) E . Atunci, conform definiiei (C.22) avem (u,v)E. Prin urmare u i v nu pot s fac parte simultan din k-clic, pentru c altfel ar fi conectate prin arcul (u,v) care nu este n E. nseamn c cel puin unul dintre nodurile u i v face parte din V-V'. Cu alte cuvinte, arcul (u,v) este acoperit de cel puin un nod din mulimea V-V'. Pentru c (u,v) a fost ales la ntmplare, rezult c orice arc din E este acoperit de cel puin un nod din mulimea V-V', mulime cu n-k noduri. Mulimea V-V' este o (n-k)acoperire a grafului G .G are o (n-k)-acoperire G are o k-clic.

Fie V' o acoperire cu (n-k) noduri a grafului G . S alegem la ntmplare dou noduri u i v din V-V'. Arcul (u,v) nu poate fi n E , pentru c nu este acoperit de u sau v. Prin urmare, (u,v)E. Rezult c ntre oricare pereche de noduri din V-V' exist un arc din E. Deci mulimea V-V' formeaz n G o clic cu k noduri. Deoarece k-Acoperire NP, k-Clic p (n-k)-Acoperire, conform lemei (C.4), i k-Clic NP-complete rezult k-Acoperire NP-complete

Problema 3SATProblema 3SAT const n verificarea satisfiabilitii unei formule CNF n care fiecare termen are cel mult 3 literali. La fel ca i SAT este folosit ca punct de plecare n verificarea NP-duritii multor probleme.

18 Teorema C.11 3SATNP-complete


1. 3SATNP. Algoritmul nedeterminist, cu complexitate polinomial, folosit pentru a verifica SATNP i, implicit 3SATNP, este simplu i este lsat ca exerciiu. 2. 3SATNP-dure. S construim o reducere SAT p 3SAT. Fie F= T1 T2 ... Tk o formul CNF cu n variabile. Construim transformarea f(F)= R(T1) R(T2) ... R(Tk), astfel nct pentru un termen T= 1 2 ... q format cu literalii i, i=1,q, algoritmul R(T) genereaz o formul CNF de forma:R(T)= (x1 1 2) (x2 x1 3) ... (xi-1 xi-2 i) ... (xq-3 q-1 q)

Formula R(T) are q-2 termeni cu cte cel mult 3 literali i conine, n afara literalilor i, i=1,q, variabilele suplimentare xi, i=1,q-C.R(T){ // T= 1 2 ... q if(q 3) return T; genereaz o nou variabil x; return (x 1 2) R(x 3 4 ... q); }

De exemplu, pentru T = 1 2 3 4 5 avem:R(1 2 = = = 3 (x1 (x1 (x1 4 1 1 1 5) 2) R(x1 3 4 5) 2) (x2 x1 3) R(x2 4 5) 2) (x2 x1 3) (x2 4 5)

Notm Cf(n) complexitatea transformrii f(F), n fiind numrul de variabile ce pot s apar n F, i CR(n) complexitatea transformrii R(T), unde T este un termen din F. Evident, Cf(n) = CR(n)k. Recurena de complexitate pentru algoritmul R este CR(m) = CR(m-1) + (1), 4m n, cu condiia la limit CR(3)= (1), iar complexitatea este CR(n)=(n). Rezult Cf(n)= (nk). Deci transformarea f este polinomial. Folosim notaia T satisfiabil[] R(T) satisfiabil[] pentru a spune c termenul T este satisfiabil dac i numai dac formula R(T) este satisfiabil, pentru aceeai legare a variabilelor din literalii i, i=1,q.T satisfiabil[] R(T) satisfiabil[]. T satisfiabil[] impune ca cel puin un literal din termenul T s fie adevrat. Fie j=1, 1jq un asemenea literal. Atunci pentru a satisface R(T) putem lega variabilele xi urmtoarele valori: xi=0, 1 i < j-1 i xi=1, max(1,j-1) i q-C.

Cristian Giumale/ Note de cursR(T) satisfiabil[] T satisfiabil[].

19

satisfiabilitatea formulei. Formula devine:

S presupunem exist o legare a variabilelor xi, i=1,q-3, din R(T) astfel nct R(T)=1, iar i=0, i=1,q. Atunci, putem elimina literalii i din R(T) fr a influenaR'(T)= x1 (x2 x1) ... (xi-1 xi-2) ... xq-3

Dar R'(T) nu este satisfiabil. ntr-adevr, parcurgnd formula de la stnga spre dreapta sunt impuse urmtoarele legri ale variabilelor: x1=0, x2=0,..., xq-3=0 i xq-3=1, ceea ce este imposibil. Prin urmare, trebuie s avem j=1 pentru cel puin un indice 1jq. nseamn c T=1. Din implicaiile de mai sus, rezult proprietatea: T satisfiabil[] R(T) satisfiabil[] i, implicit, F satisfiabil f(F) satisfiabil. Transformarea f(F) = R(T1) R(T2) ... R(Tk) este ntr-adevr o reducere SAT p 3SAT, deci 3SATNP-dure. Pentru c 3SATNP i 3SATNP-dure.

Problema 2SATProblema 2SAT const n verificarea satisfiabilitii unei formule CNF n care fiecare termen are cel mult 2 literali. Numim 2CNF mulimea unor asemenea formule. Spre deosebire de problema NSat, N3, care este NP-complet, 2SAT este rezolvabil determinist n timp polinomial, deci 2SATP. Ca demonstraie, vom arta c rezolvarea problemei se reduce la deciderea existenei unor drumuri ntr-un graf. Fie F2CNF o formul. Notm Trm mulimea termenilor i Var mulimea variabilelor din F, k=card(Trm) i n=card(Var). S construim graful orientat GF=(V,E) n felul urmtor:V= {xVar x} {xVar x} ( E= U arce T),TTrm

unde arce(T) este mulimea arcelor construite pentru termenul T aa cum se arat n tabelul (C.1). Tabelul C.1 Arce corespunztoare unui termen termen Tx x (xy) (xy) (xy) (xy)

formul echivalent pentruT (xx) (xx) (xy)(yx) (xy)(yx) (xy)(yx) (xy)(yx)

arce(T) {(x,x)} {(x,x)} {(x,y),(y,x)} {(x,y),(y,x)} {(x,y),(y,x)} {(x,y),(y,x)}

20


Avem, card(V)=2n, iar card(E)2k i observm c graful GF poate fi construit n timp polinomial n raport cu n i k. Un exemplu este ilustrat n figura C.1.

x

y

y

x

z

z

Figura C.1 Graful GF corespunztor formulei F=(xy)(xy)(zy)(zy) Lema C.6 F nu este satisfiabil xVar x..x n graful GF. exist drumuri x.. x i

xVar exist drumuri x.. x i x..x n GF F nu este satisfiabil.

Fie xVar astfel nct exist un drum d1=x..x i un drum d2=x..x. Fie (,) i (,), cu , i literali, dou arce consecutive dintr-un drum n GF. Arcele corespund implicaiilor i , care trebuie s fie adevrate pentru ca F s poat fi satisfcut. Folosind tautologia rezult c implicaia trebuie s fie adevrat pentru ca F s poat fi satisfcut. Implicaia corespunde unui arc (,), existent sau indus, n GF, arc ce poate substitui cele dou arce consecutive. Prin inducie, urmnd cile d1 i d2 obinem: pentru d1: trebuie s avem xx pentru ca F s poat fi satisfcut. pentru d2: trebuie s avem xx pentru ca F s poat fi satisfcut. Implicaia xx este adevrat pentru x=0, iar Implicaia xx este adevrat pentru x=1. Imposibil, pentru c variabila x trebuie legat la o valoare unic.F nu este satisfiabil xVar exist drumuri x.. x i x..x n GF

Dac F nu este satisfiabil, atunci exist cel puin o variabil, fie ea x, astfel nct x s nu poat fi legat la o unic valoare. nseamn c avem x=1 i x=0 simultan, iar din formula F se pot deduce implicaiile xx i xx . Cele dou implicaii corespund arcelor, existente sau induse, (x,x) i (x,x) din GF. nseamn c n GF exist drumuri x..x i x..x. Ca ilustrare a propoziiei (C.1), formula F din figura 1 nu este satisfiabil. Exist drumurile: z,y,x,y,z i z,y,x,y,z din care se deduc implicaiile zz i zz, adic echivalena imposibil zz.


21

Teorema C.11' 2SATP Fie Constr(F)=GF algoritmul determinist de construcie, n timp polinomial p(n,k), a grafului GF asociat unei formule F Putem construi urmtorul algoritm care rezolv problema 2SAT:2SAT(F){ GF= Constr(F); // complexitate polinomial n n i k Var= variabile(F); for-each(xVar) if(drum(GF,x,x) drum(GF,x,x)) return 0; return 1; }

Funcia drum(GF,u,v) testeaz dac n graful orientat GF exist un drum de la u la v i are complexitate polinomial n raport cu numrul de noduri din graf, cel mult 2n, n=card(Var). Testul se poate efectua printr-o simpl parcurgere n adncime a grafului GF pornind de la u. n concluzie, algoritmul 2Sat are complexitate polinomial n n, deci 2SATP.

NP Completitudine

Documents

Transcript of NP Completitudine