NP (klasa kompleksnosti)

U teoriji kompleksnosti, NP (nedeterminističko polinomijalno) je skup problema odluke, rješivih u polinomijalnom vremenu na nedeterminističkoj Turingovoj mašini. Ekvivalentno, to je skup problema čija rješenja mogu da se provjere na determinističkoj Turingovoj mašini u polinomijalnom vremenu.

NP se može smatrati kao skup problema odluke (odgovor 'da' ili 'ne') za koji se 'da'-rješenje u polinomijalnom vremenu može provjeriti sa determinističkom Turingovom mašinom. Problemi odluka za koje se 'ne'-rješenje jednostavno može kontrolisati, pripada  Co-NP-u (komplement NP-a).

 Formalna definicija 
NP se može definisati sa pojmom NTIME:

Alternativna definicija se može stvoriti koristeći determinističke Turing mašine kao verifikatore. Nadalje, jezik L je u NP-u ako i samo ako postoje polinomi p i q, i deterministička Turing mašina M, tako da

 za sve x i y, mašina M ima algoritamsko trajanje procesa p(|x|) sa ulaznim podacima (x,y).
 za svaki x koji je u L-u, postoji niz y dužine q(|x|) tako da je M(x,y) = 1.
 za svaki x koji nije u L-u i za sve nizove y dužine q(|x|), M(x,y) = 0.

 Uvod 
Klasa NP obuhvata mnoge prirodne probleme koji se formalno mogu definisati u računarstvu, kao na primjer što su odlučne verzije problema pretrage i optimizacije.

 Primjeri 
Primjeri NP problema su:
 Problem izomorfizma grafova: odrediti da li su dva grafikona izomorfno identična.
 Problem faktorizacije cijelih brojeva: sa datim cijelim brojevima n i k, da li postoji faktor f tako da 1 < f < k i da je f djelioc broja n.
 Svi problemi u klasi P.
 Svi NP-kompletni problemi kao:
 Problem trgovačkog putnika: gdje pokušavamo da utvrdimo da li postoji put određene dužine koji obilazi sve čvorove.
 Problem zadovoljivosti: gdje želimo da utvrdimo da li je neka formula, iskazana u bulovskim promjenljivama, zadovoljiva ili ne.

 Zašto je teško određene NP probleme riješiti 
Pošto su mnogi važni problemi u ovoj klasi, ulagani su intenzivni napori da se nađu algoritmi u polinomijalnom vremenu za probleme u NP klasi. Međutim, veliki broj NP problema ostaje izazivajući ove pokušaje, koji dalje izgleda da zahtjevaju super-polinomijalno vrijeme. Da li ovi problemi stvarno nisu riješivi u polinomijalnom vremenu je jedno od najvećih otvorenih pitanja u računarstvu (P=NP problem).

Važan pojam u ovom kontekstu predstavlja skup NP-kompletnih problema odluke, koji su podskup klase NP, i neformalno se mogu opisati kao najteži NP problemi. Ako bi postojao algoritam u polinomijalnom vremenu za makar jedan od njih, onda bi postojao polinomijalni algoritam za sve probleme iz klase NP. Zbog ovoga, i zato što do sada (uprkos svim naporima) nije pronađen polinomijalni algoritam ni za jedan NP-kompletan problem, kada se za neki problem pokaže da je NP-kompletan, obično se smatra da nije vjerovatno da postoji polinomijalni algoritam za taj problem.

 Vanjski linkovi 
  Complexity Zoo - Klasa NP
  Modeli računanja - Klase kompleksiteta (PDF)

 Literatura 
  R. E. Ladner, On the structure of polynomial time reducibility, J.ACM, 22, 1975. doi:10.1145/321864.321877.
  Penjić Safet, Seminarski rad - Tema: L i NL klase jezika, Univerzitet Sarajevo.
  John E. Savage, Models Of Computation - Exploring the Power of Computing. .

 Reference 
  Ladner, J.ACM, 22, str. 151–171, zaključak 1.1..
  Penjić, str. 4.
  John E. Savage, str. 335, definicija 8.5.2.

Kategorija:Klase kompleksnosti