NP (klasa kompleksnosti)

Euler dijagram za P, NP, NP-kompletne i NP-teške skupove problema. Postojanje problema u klasi NP ali van P i NP-kompletne klase je pod ovom pretpostavkom osnovao Ladner.

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:

${\mbox{NP}}=\bigcup _{k\in \mathbb {N} }{\mbox{NTIME}}(n^{k}).$

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

• (en) Complexity Zoo - Klasa NP
• (en) Modeli računanja - Klase kompleksiteta (PDF)

Literatura

• (en) R. E. Ladner, On the structure of polynomial time reducibility, J.ACM, 22, 1975. doi:10.1145/321864.321877.
• (bs) Penjić Safet, Seminarski rad - Tema: L i NL klase jezika, Univerzitet Sarajevo.
• (en) John E. Savage, Models Of Computation - Exploring the Power of Computing. ISBN 978-0-201-89539-1.