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
- X pripada klasi NP
- X je NP-težak .
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
- X pripada klasi NP
- postoji NP-kompletan problem Y koji je polinomijalno svodljiv na X.
Primeri problema Y (sa predavanja, knjige):
- pokrivač grana
- dominirajući skup
- 3 SAT
- problem klike
- 3-obojivost
Korisni termini:
- klika
- kompletan podgraf; za graf G=(V,E), klika je podgraf H u kome su svičvorovo 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 promenljiv 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:
- generisati skup od po tačno k čvorova (ima ih
O(nk) )
- proveriti kompletnost svakog podgrafa indukovanog tim podskupom
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), pa ovo nije algoritam polinomijalne slozenosti, jer eksponencijalno zavisi od k
NP2
Zadat je regularni graf G (graf čiji svi čvorovi imaju isti stepen) i prirodan broj k. Dokazati NP-kompletnost problema koji utvrđuje da li G 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. Treba povezati nove cvorove tako da svi imaju stepen d.
Nove klike za sada nisu napravljene. Skup novih cvorova se, dalje, deli na dva dela sa jednakim brojem cvorova. 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.
