NP (klasa kompleksnosti)

U teoriji kompleksnosti, NP (nedeterminističko polinomijalno vreme) je skup problema odlučivanja rešivih u polinomijalnom vremenu na nedeterminističkoj Tjuringovoj mašini. Ekvivalentno, to je skup problema čija rešenja mogu da se provere na determinističkoj Tjuringovoj mašini u polinomijalnom vremenu.

Uvod i primene

Važnost ove klase problema odlučivanja je u tome što sadrži mnoge interesantne probleme pretrage i optimizacije, gde želimo da utvrdimo da li postoji određeno rešenje za određeni problem.

Posmatrajmo na primer problem utvrđivanja da li je n složen broj. Za ovaj problem znamo (mada tek od 2002) da je rešiv u polinomijalnom vremenu. Međutim, algoritam koji ga rešava (AKS test prostosti) je i dalje vrlo težak. Sa druge strane, ako smo našli broj za koji verujemo da može biti delilac za n, sledeća funkcija nam vrlo brzo može reći da li je taj broj stvarno delilac, što bi značilo da je n složen:

 boolean isNontrivialFactor(n, d)
     if n is divisible by d and
        d ≠ 1 and d ≠ n
         return true
     else
         return false

Ako je n složen, ova funkcija će vratiti true za neki ulaz d. Međutim, ako je n prost, ova funkcija će uvek vratiti false, koji god ulaz d da joj prosledimo. Svi problemi u klasi NP imaju deterministički algoritam u polinomijalnom vremenu, koji, kao i ovaj, vraća true samo kada mu se proslede ulaz i dokaz da je ulaz unutar jezika. Ovakvi algoritmi proveravaju potencijalna rešenja problema.

Stoga, izazov kod NP problema jeste da se odgovor nađe na efikasan način, jer je efikasan način da se proveri rešenje već nađen.

Sa druge starne, za opštiji problem nalaženja broja između 1 i m koji deli n (problem faktorizacije) nije poznato da li je u klasi NP, jer još uvek ne postoji način da se on reši deterministički u polinomijalnom vremenu.

Među dodatnim primerima problema iz klase NP su:

• Problem izomorfizma grafova, određivanje da li se od jednog grafa može napraviti drugi prostim preimenovavanjem čvorova
• Problem trgovačkog putnika, gde pokušavamo da utvrdimo da li postoji put određene dužine koji prolazi kroz sve čvorove nekog grafa
• SAT problem, gde želimo da utvrdimo da li je neka formula iskazana u bulovskim promenljivim zadovoljiva ili ne

Vidi članak NP-kompletni problemi za više važnih problema iz klase NP.

Zašto je neke NP probleme teško reš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 je odoleo ovim naporima, i izgleda da oni zahtevaju superpolinomijalno vreme. Da li ovi problemi stvarno nisu rešivi u polinomijalnom vremenu je jedno od najvećih otvornih pitanja u računarstvu (vidi klase kompleksnosti P i NP za dublje objašnjenje).

Važan pojam u ovom kontekstu predstavlja skup NP-kompletnih problema odlučivanja, 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 verovatno da postoji polinomijalni algoritam za taj problem.

Primer

Problem trgovačkog putnika u verziji problema odlučivanja je u klasi NP. Ako je data matrica u kojoj su navedene razdaljine između N problem se sastoji u utvrđivanju da li postoji putanja koja povezuje sve gradove, ukupne dužine manje od k. Nedeterministička Tjuringova mašina može da pronađe takvu putanju na sledeći način:

• U svakom gradu ona pogađa koji sledeći grad da poseti, dok ne poseti svaki grad. Ako se zaglavi, odmah staje.
• Na kraju proverava da li je dužina putanje manja od k za vreme O (n).

Svako pogađanje se može posmatrati kao pravljenje nove kopije Tjuringove mašine kako bi se pratio svaki mogući put napred, i ako barem jedna mašina nađe putanju dužine manje od k, ta mašina prihvata ulaz. (Ekvivalentno, ovo se može posmatrati kao jedna Tjuringova mašina koja uvek pogađa ispravno.)

Ako bismo mogli ovaj problem (verzija problema odlučivanja) da rešimo brzo, mogli bismo da koristimo binarnu pretragu da rešimo i originalni problem optimizacije (nalaženje putanje i njene tačne dužine).

Literatura

• Complexity Zoo: NP
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill. 2001. ISBN 978-0-262-03293-3.. Section 34.2: Polynomial-time verification, pp. 979-983.
• Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 978-0-534-94728-6.  Sections 7.3-7.5 (The Class NP, NP-completeness, Additional NP-complete Problems), pp. 241-271.
• David Harel, Yishai Feldman. Algorithmics: The Spirit of Computing, Addison-Wesley, Reading, MA, 3rd edition, 2004.