Primene računara (4. godina/ R smer)

NP-kompletnost

Postoje problemi koji se ne mogu rešiti algoritmom čija vremenska složenost je O(P(n)), gde P(n) jeste polinom od dimenzije ulaza n. Važno je znati prepoznati takve probleme i za njih naći približna rešenja.

Tema ovog poglavlja su problemi za koje se ne zna da li su klasi P, specijalnije fokus je na tzv. NP-kompletnim problemima.

Neformalno rečeno, NP klasa je klasa svih problema odlučivanja koji mogu biti rešeni Nedeterminističkim algoritmom za Polinomijalno vreme.

Za sada niko nije uspeo da pronađe NP problem koji nije u klasi P. Sam problem utvrđivanja odnosa klasa P i NP poznat je u literaturi kao "problem P=NP " .

Za problem X se kaže da je NP-težak ako je svaki problem iz klase NP polinomijalno svodljiv na X.

Za problem X se kaže da je NP-kompletan ako je

Kako je S.A.Cook 1971. godine dokazao da postoje NP-kompletni problemi, to kriterijum NP kompletnosti (a koji se češće koristi u ovom kursu) za problem X glasi:

Za problem X se kaže da je NP-kompletan ako je

    Primeri problema Y (sa predavanja, knjige):
  1. pokrivač grana
  2. dominirajući skup
  3. 3 SAT
  4. problem klike
  5. 3-obojivost

Korisni termini:

klika
kompletan podgraf; za graf G=(V,E), klika je podgraf H u kome su svi čvorovi povezani među sobom granama iz E.
pokrivač grana
za graf G=(V,E), pokrivač grana je skup čvorova takvih da svaka grana iz E je susedna bar jednom čvoru iz skupa
problem klika
za dati neusmeren graf G=(V,E) i prirodan broj k ustanoviti da li G sadrži kliku veličine bar k
SAT problem
za dati Bulov izraz S ustanoviti da li je zadovoljiv (tj. ustanoviti da li postoji dodeljivanje nula i jedinica promenljivama izraza tako da izraz ima vrednost 1)
3 SAT problem
uprošćenje SAT problema; Bulov izraz u KNF se sastoji od klauza u kojoj svaka klauza ima tačno tri literala
3-obojivost
za neismereni graf G=(V,E) ustanoviti da li se G može obojiti sa 3 boje (pridruživanje boja čvorovima ima pravilo da se svakom čvoru pridruži neka boja, a da su susednim čvorovima uvek pridružene različite boje)

 

 

NP1
Da li sledeći algoritam za utvrđivanje da li graf ima kliku veličine k jest polinomijalne vremenske složenosti:

 

REŠENJE:
Klasa O(nk) je polinomijalne slozenosti po n , ali ne i po vrednosti k (koja nije fiksirana vrednost i koja je, takođe, ulazni parametar algoritma; npr. moze k=n/2),
te ovo nije algoritam polinomijalne slozenosti, jer eksponencijalno zavisi od k

 

NP2
Zadat je regularni graf (graf čiji svi čvorovi imaju isti stepen) i prirodan broj k. Dokazati NP-kompletnost problema koji utvrđuje da li ovaj graf sadrži kliku veličine k.

 

REŠENJE:
Moze se svesti opšti klika problem na klika problem za regularne grafove.
Neka je G=(V,E) proizvoljan graf i k proizvoljan broj.
Kontruise se pravilan graf H takav da graf G ima kliku velicine vecu ili jednaku k ako i samo ako H ima kliku velicine vecu ili jednaku k.
Neka je n broj cvorova grafa G .
Neka je d maksimalni stepen grafa G ako je taj broj paran, inace maksimalni stepen grafa G plus jedan (tj. vrednost d je uvek parna).
Za svaki cvor v grafa G stepena d(v)<d dodaje se d-d(v) novih cvorova i povezuju se sa v . Ukupan broj novih cvorova je

∑i=1..n(d -d(v i )) =dn - ∑i=1..nd(v i) =dn - 2|E|

Ovaj broj je paran, jer je broj d paran.
Cilj nam je da povezemo nove cvorove tako da svi imaju stepen d.

Nove klike za sada nisu napravljene (zasto?). Skup novih cvorova se, dalje, deli na dva dela sa jednakim brojem cvorova (zasto je to moguce?). Svaki cvor iz jedne grupe povezimo sa tacno d-1 cvorova iz druge.

Tako dobijen graf je regularan i on ima kliku velicine veću ili jednaku k ako i samo ako graf G ima kliku velicine veću ili jednaku k .

Time je klika problem sveden na klika problem za regularnene grafove. Kako je klika problem NP-kompletan problem, sledi da je i klika problem za regularne grafove NP-kompletan.

 

Jelena Hadži-Purić Primene računara