NP je klasa jezika koji imaju verifikatore polinomskog vremena
Klasa NP, koja je skraćenica za "nedeterminističko polinomsko vreme", je fundamentalni koncept u teoriji složenosti računara, podoblasti teorijske računarske nauke. Da bismo razumjeli NP, prvo moramo shvatiti pojam problema odlučivanja, koji su pitanja sa odgovorom da ili ne. Jezik se u ovom kontekstu odnosi na skup nizova preko neke abecede, gdje svaki niz kodira instancu problema odlučivanja.
Za jezik (L) se kaže da je u NP ako postoji verifikator polinomskog vremena za (L). Verifikator je deterministički algoritam (V) koji uzima dva ulaza: instancu (x) i certifikat (y). Certifikat (y) je također poznat kao "svjedok" ili "dokaz". Verifikator (V) proverava da li sertifikat (y) potvrđuje da (x) pripada jeziku (L). Formalno, jezik (L) je u NP ako postoji polinomski algoritam (V) i polinom (p(n)) takvi da za svaki niz (x u L), postoji niz (y) sa ( |y|. leq p(|x|)) i (V(x, y) = 1). Obrnuto, za svaki niz (x notin L), ne postoji niz (y) takav da je (V(x, y) = 1).
Da biste razjasnili ovaj koncept, razmotrite dobro poznati problem "Booleove zadovoljivosti" (SAT). SAT problem postavlja pitanje da li postoji dodjela istinitih vrijednosti varijablama u datoj Booleovoj formuli tako da formula procjenjuje istinito. SAT problem je u NP jer, datoj Booleovoj formuli ( phi ) i dodjeli ( alfa ) istinitih vrijednosti njenim varijablama, može se provjeriti u polinomskom vremenu da li ( alpha ) zadovoljava ( phi ). Ovdje je instanca (x) Bulova formula (phi), a certifikat (y) je dodjela (alfa). Verifikator ( V ) provjerava da li ( alpha ) čini ( phi ) istinitim, što se može učiniti u polinomskom vremenu u odnosu na veličinu ( phi ).
Još jedan ilustrativan primjer je problem "Hamiltonovog puta". Ovaj problem postavlja pitanje postoji li putanja u datom grafu koja posjećuje svaki vrh tačno jednom. Problem Hamiltonove putanje je također u NP jer, dat graf (G) i niz vrhova (P), može se provjeriti u polinomskom vremenu da li je (P) Hamiltonov put u (G). U ovom slučaju, instanca (x) je graf (G), a sertifikat (y) je niz vrhova (P). Verifikator (V) provjerava da li (P) formira Hamiltonovu putanju, što se može uraditi u polinomskom vremenu s obzirom na veličinu (G).
Koncept provjerljivosti u polinomskom vremenu je važan jer pruža način za karakterizaciju problema koji se efikasno mogu provjeriti, čak i ako bi pronalaženje rješenja moglo biti računski neizvodljivo. Ovo dovodi do poznatog pitanja da li ( P = NP ), koje postavlja pitanje da li se svaki problem čije se rješenje može provjeriti u polinomskom vremenu također može riješiti u polinomskom vremenu. Klasa (P) se sastoji od problema odlučivanja koji se mogu riješiti u polinomskom vremenu pomoću determinističke Turingove mašine. Ako je ( P = NP ), to bi značilo da svaki problem sa verifikatorom polinomskog vremena također ima rješavač polinomskog vremena. Ovo pitanje ostaje jedan od najvažnijih otvorenih problema u informatici.
Jedno od ključnih svojstava NP je da je zatvoren pod polinomskim redukcijama. Redukcija u polinomskom vremenu sa jezika ( L_1 ) na jezik ( L_2 ) je računljiva funkcija u polinomskom vremenu ( f ) takva da ( x u L_1 ) ako i samo ako ( f(x) u L_2 ). Ako postoji redukcija polinomskog vremena sa ( L_1 ) na ( L_2 ) i ( L_2 ) je u NP, tada je ( L_1 ) također u NP. Ovo svojstvo je instrumentalno u proučavanju NP-potpunosti, koje identifikuje "najteže" probleme u NP. Problem je NP-potpun ako je u NP i svaki problem u NP se može svesti na njega u polinomskom vremenu. SAT problem je bio prvi problem za koji je dokazano da je NP-kompletan, a služi kao osnova za dokazivanje NP-potpunosti ostalih problema.
Da biste dalje ilustrirali koncept provjerljivosti polinomskog vremena, razmotrite problem "Subset Sum". Ovaj problem postavlja pitanje da li postoji podskup datog skupa cijelih brojeva koji zbraja određenu ciljnu vrijednost. Problem sume podskupa je u NP jer, dat skup cijelih brojeva ( S ), ciljnu vrijednost ( t ) i podskup ( S' ) od ( S ), može se provjeriti u polinomskom vremenu da li je zbir elemenata u (S') jednako (t). Ovdje je instanca (x) par ((S, t)), a certifikat (y) je podskup (S'). Verifikator (V) provjerava da li je zbir elemenata u (S') jednak (t), što se može uraditi u polinomskom vremenu u odnosu na veličinu (S).
Važnost provjerljivosti polinomskog vremena proteže se dalje od teorijskih razmatranja. U praktičnom smislu, to znači da se za probleme u NP, ukoliko je predloženo rješenje (sertifikat), može efikasno provjeriti. Ovo ima značajne implikacije za kriptografske protokole, probleme optimizacije i različita polja u kojima je provjera ispravnosti rješenja važna.
Da rezimiramo, klasa NP obuhvata probleme odlučivanja za koje se predloženo rješenje može verificirati u polinomskom vremenu pomoću determinističkog algoritma. Ovaj koncept je temelj u teoriji računske složenosti i ima duboke implikacije kako za teorijske tako i za praktične aspekte računarske nauke. Proučavanje NP-a, provjerljivosti u polinomskom vremenu i srodnih koncepata kao što je NP-potpunost i dalje je živo i kritično područje istraživanja.
Ostala nedavna pitanja i odgovori u vezi složenost:
- Zar PSPACE klasa nije jednaka klasi EXPSPACE?
- Da li je P klasa složenosti podskup klase PSPACE?
- Možemo li dokazati da su Np i P klasa iste pronalaženjem efikasnog polinomskog rješenja za bilo koji NP kompletan problem na determinističkom TM?
- Može li NP klasa biti jednaka klasi EXPTIME?
- Postoje li problemi u PSPACE-u za koje ne postoji poznati NP algoritam?
- Može li SAT problem biti NP potpuni problem?
- Može li problem biti u klasi složenosti NP ako postoji nedeterministička Turingova mašina koja će ga riješiti u polinomskom vremenu
- Da li su P i NP zapravo ista klasa složenosti?
- Da li je svaki jezik bez konteksta u P klasi složenosti?
- Postoji li kontradikcija između definicije NP kao klase problema odlučivanja s verifikatorima polinomskog vremena i činjenice da problemi u klasi P također imaju verifikatore polinomskog vremena?
Pogledajte više pitanja i odgovora u Complexity