Izvorni kôd stranice NP (klasa kompleksnosti)

[[Datoteka:P_np_np-kompletno_np-teško.svg|mini|300px|desno|[[Euler dijagram]] za [[P (klasa kompleksnosti)|P]], NP, [[NP-kompletno|NP-kompletne]] i [[NP-teško|NP-teške]] skupove problema. Postojanje problema u klasi '''NP''' ali van '''P''' i '''NP-kompletne''' klase je pod ovom pretpostavkom [[Ladnerova teorema|osnovao Ladner]].<ref name="Ladner" />]]

U [[teorija kompleksnosti|teoriji kompleksnosti]], '''NP''' (''nedeterminističko polinomijalno'') je skup [[problem odluke|problema odluke]], rješivih u [[polinomijalno vrijeme|polinomijalnom vremenu]] na [[turingova mašina|nedeterminističkoj Turingovoj mašini]]. Ekvivalentno, to je skup problema čija rješenja mogu da se provjere na [[turingova mašina|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 | Co-NP-u]] (komplement '''NP'''-a).

== Formalna definicija ==
'''NP''' se može definisati sa pojmom [[NTIME]]<ref name="Penjić" /><ref name="Savage" />:

:<math>\mbox{NP} = \bigcup_{k\in\mathbb{N}} \mbox{NTIME}(n^k).</math>

Alternativna definicija se može stvoriti koristeći determinističke Turing mašine kao verifikatore. Nadalje, [[formalni jezik|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 [[vremenska složenost|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čunarstvo|računarstvu]], kao na primjer što su odlučne verzije problema [[problem pretrage|pretrage]] i [[problem optimizacije|optimizacije]].

{{Proširiti sekciju}}

=== Primjeri ===
Primjeri '''NP''' problema su:
* [[Problem izomorfizma grafova]]: odrediti da li su dva [[grafikon]]a [[izomorfizam|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 (klasa kompleksnosti)|P]].
* Svi [[NP-kompletno (klasa kompleksnosti)|NP-kompletni]] problemi kao:
** [[Problem trgovačkog putnika]]: gdje pokušavamo da utvrdimo da li postoji put određene dužine koji obilazi sve [[čvor (teorija grafikona)|čvorove]].
** [[Problem zadovoljivosti]]: gdje želimo da utvrdimo da li je neka formula, iskazana u [[bulovska algebra|bulovskim]] [[promjenljiva]]ma, 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 simbol}} [https://web.archive.org/web/20120703032755/http://qwiki.stanford.edu/index.php/Complexity_Zoo:N#np Complexity Zoo - Klasa NP]
* {{en simbol}} [http://www.cs.brown.edu/people/jes/book/pdfs/ModelsOfComputation_Chapter8.pdf Modeli računanja - Klase kompleksiteta ([[PDF]])]

== Literatura ==
* {{en simbol}} R. E. Ladner, ''On the structure of polynomial time reducibility'', J.ACM, 22, 1975. [[doi:10.1145/321864.321877]].
* {{bs simbol}} Penjić Safet, ''[https://web.archive.org/web/20111202155923/http://www.pf.unze.ba/nabokov/seminarskiRadovi/Teorija%20kompleksnosti/L%20i%20NL%20klase%20jezika.pdf Seminarski rad - Tema: L i NL klase jezika]'', Univerzitet Sarajevo.
* {{en simbol}} John E. Savage, ''[http://www.cs.brown.edu/people/jes/book/pdfs/ModelsOfComputation.pdf Models Of Computation - Exploring the Power of Computing]''. {{ISBN|978-0-201-89539-1}}.

== Reference ==
<references>
  <ref name="Ladner">Ladner, J.ACM, 22, str. 151&ndash;171, zaključak 1.1.</ref>.
  <ref name="Penjić">Penjić, str. 4.</ref>
  <ref name="Savage">John E. Savage, str. 335, definicija 8.5.2.</ref>
</references>

{{Klase Kompleksnosti}}

[[Kategorija:Klase kompleksnosti]]