NP-kompletni problemi

U teoriji kompleksnosti, NP-kompletni problemi su najteži problemi u klasi NP (nedeterministički, polinomijalno vreme) u smislu da su najmanja podklasa NP, koja bi eventualno mogla da ostane izvan klase P (još uvek se ne zna da li su klase P i NP jednake). Razlog je što bi determinističko rešenje bilo kog NP-kompletnog problema u polinomijalnom vremenu bilo takođe rešenje svakog problema iz klase NP. Klasa kompleksnosti koja se sastoji od svih NP-kompletnih problema se ponekad naziva NP-C. Formalnija definicija je data niže.

Jedan primer NP-kompletnog problema je problem zbira podskupa, koji glasi: ako je dat skup celih brojeva, odrediti da li postoji neprazan podskup ovog skupa sa zbirom elemenata nula. Ako imamo pretpostavljeni odgovor (podskup), vrlo je lako proveriti da li mu je zbir nula, ali nije poznat značajno brži algoritam za rešavanje ovog problema osim da se isproba svaki mogući podskup, što je vrlo sporo.

Formalna definicija NP-kompletnosti

Problem odlučivanja C je NP-kompletan, ako je kompletan za klasu NP, što znači da:

1. C je NP i
2. C je NP-težak problem, to jest, svaki problem iz NP se može svesti na njega.

Svesti u ovom kontekstu znači da za svaki problem L iz NP postoji deterministički algoritam polinomijalne složenosti, koji pretvara slučajeve l ∈ L u slučajeve c ∈ C, tako da je odgovor na c DA ako i samo ako je odgovor na l DA. Da se dokaže da je NP problem A NP-kompletan, dovoljno je pokazati da se neki već poznati NP-kompletan problem svodi na A.

Posledica ove definicije je da ako bismo imali polinomijalni algoritam (na univerzalnoj Tjuringovoj mašini), ili bilo kojoj Tjuring-ekvivalentnoj apstraktnoj mašini za C, mogli bismo da rešimo sve NP probleme u polinomijalnom vremenu.

Ovu definiciju je dao Stiven Kuk u radu pod naslovom 'Kompleksnost procedura za dokazivanje teorema' na stranama 151-158 Radova sa trećeg godišnjeg ACM simpozijuma o računarskoj teoriji 1971. godine, mada se izraz NP-kompletan nije javio u njegovom radu. Na toj računarskoj konferenciji je vođena žestoka debata među informatičarima oko pitanja da li NP-kompletni problemi mogu da se reše u polinomijalnom vremenu na determinističkoj Tjuringovoj mašini. Džon Hopkoft je uspeo da iznađe konsenzus predlogom da se pitanje da li su NP-kompletni problemi rešivi u polinomijalnom vremenu odloži za neko kasnije vreme, jer niko nije imao nikakav formalni dokaz za svoje stavove. Ovo je poznato kao pitanje da li je P=NP.

Još uvek niko nije uspeo da dokaže ili opovrgne da su NP-kompletni problemi rešivi u polinomijalnom vremenu, tako da je ovo jedan od velikih nerešenih problema u matematici. Klejov matematički institutnudi nagradu od 1.000.000 dolara onome ko pruži formalni dokaz da je P=NP ili da je P≠NP.

Prvobitno je izgledalo vrlo neočekivano da NP-kompletni problemi uopšte postoje, ali u čuvenoj Kuk-Levinovoj teoremi (koju je nezavisno dokazao i Leonid Levin), Kuk je dokazao da je SAT problem NP-kompletan (jednostavniji, ali ipak prilično zahtevan dokaz ovoga je dostupan). 1972. Ričard Karp je dokazao da je još nekoliko problema takođe NP-kompletno (vidi Karpov 21 NP-kompletan problem); i da stoga postoji klasa NP-kompletnih problema (i da SAT problem nije usamljen u njoj). Karpu je bilo znatno lakše da dokaže NP-kompletnost za ovaj 21 problem, jer ako je za neki skup problema već dokazano da su NP-kompletni, za novi problem je dovoljno dokazati da je iz klase NP, i da je neki NP kompletan problem moguće svesti na njega. Od Kukovog SAT problema, za hiljade drugih problema je pokazano da su NP-kompletni; mnoge od ovih problema su sakupili Geri i Džonson 1979. u knjizi Computers and Intractability: A Guide to NP-Completeness.

Problem koji zadovoljava drugi uslov (da je na njega moguće svesti neki NP-kompletan problem), ali ne obavezno i prvi (da je iz klase NP) se naziva NP-teškim problemom. Neformalno, NP-težak problem je barem onoliko težak kao i svaki NP-kompletan problem, ako ne i teži. Na primer, izbor savršenog poteza u određenim igrama na proizvoljno velikoj tabli je NP-težak ili čak strogo teži od NP-kompletnih problema.

Primeri problema

Neki NP-kompletni problemi, sa redukcijama koje se obično koriste da se dokaže njihova NP-kompletnost

Interesantan primer je problem izomorfizma grafova, problem iz teorije grafova, koji se sastoji u otkrivanju da li postoji izomorfizam grafova između dva grafa. Dva grafa su izomorfna ako se jedan može pretvoriti u drugi prostim preimenovavanjem čvorova. Posmatrajmo sledeća dva problema:

• Izomorfizam grafova: Da li je graf G₁ izomorfan grafu G₂?
• Izomorfizam podgrafova: Da li je graf G₁ izomorfan podgrafu grafa G₂?

Izomorfizam podgrafova je NP-kompletan problem. Za izomorfizam grafova se smatra da nije ni P, niti NP-kompletan, mada je očigledno u klasi NP. Ovo je primer problema za koji se smatra da je težak, ali ne dovoljno da bi bio NP-kompletan.

Najlakši način da se dokaže da je neki problem NP-kompletan je da se prvo dokaže da je NP, a zatm da se neki već poznati NP-kompletan problem svede na njega. Stoga je korisno poznavati razne NP-kompletne probleme. Sledeći spisak sadrži nekoliko poznatih problema koji su NP-kompletni kada se izraze u formi problema odlučivanja.

• SAT problem
• N-slagalica
• Problem ranca
• Problem Hamiltonovog ciklusa
• Problem trgovačkog putnika
• Priblem izomorfizma podgrafa
• Problem sume podskupa
• Problem klike
• Problem pokrivača grana
• Problem nezavisnog skupa
• Problem bojenja grafa

Za još primera NP-kompletnih problema pogledati spisak NP-kompletnih problema.

Desno je dijagram nekih problema i redukcija koje se obično koriste da se dokaže njihova NP-kompletnost. Na ovom dijagramu, strelica od jednog problema ka drugom označava smer redukcije. Ove strelice nisu pokazatelj matematičkih odnosa između ovih problema, jer se u polinomijalnom vremenu svaki od ovih problema može svesti na svaki drugi; strelice samo pokazuju najlakši put za svođenje sa jednog problema na drugi.

Često postoji vrlo mala razlika između P problema i NP-kompletnog problema. Na primer, 3-SAT problem je NP-kompletan, dok je njemu vrlo sličan 2-SAT problem iz klase P (preciznije, NL-kompletan problem), a malo opštiji problem, maksimalni 2-SAT problem je opet NP-kompletan. Provera da li se graf može obojiti pomoću 2 boje je P, a pomoću 3 boje je NP-kompletan problem, čak i kad se ograničimo na planarne grafove. Provera da li je graf cikličan ili bipartitan je vrlo laka (klase L), ali nalaženje maksimalnog bipartitnog ili maksimalnog cikličnog grafa je NP-kompletan problem. Rešavanje problema ranca unutar bilo kog fiksnog procentualnog opsega od optimalnog rešenja se može sprovesti u polinomijalnom vremenu, ali je pronalaženje optimalnog rešenja NP-kompletno.