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.

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.[1]

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

uredi

NP se može definisati sa pojmom NTIME[2][3]:

 

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.

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

uredi

Primjeri NP problema su:

Zašto je teško određene NP probleme riješiti

uredi

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

uredi

Literatura

uredi

Reference

uredi
  1. ^ Ladner, J.ACM, 22, str. 151–171, zaključak 1.1.
  2. ^ Penjić, str. 4.
  3. ^ John E. Savage, str. 335, definicija 8.5.2.