Klasa NP, koja označava "nedeterminističko polinomsko vrijeme", temeljni je koncept u teoriji računalne složenosti, potpolju teorijske računalne znanosti. Da bismo razumjeli NP, prvo moramo shvatiti pojam problema odlučivanja, a to su pitanja s 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). Potvrda (y) također je poznata kao "svjedok" ili "dokaz". Verifikator (V) provjerava potvrđuje li certifikat (y) da (x) pripada jeziku (L). Formalno, jezik (L) je u NP ako postoji polinomski vremenski algoritam (V) i polinom (p(n)) tako da za svaki niz (x u L), postoji niz (y) s ( |y|. leq p(|x|)) i (V(x, y) = 1). Obrnuto, za svaki niz (x ne u L), ne postoji niz (y) takav da je (V(x, y) = 1).
Kako bismo razjasnili ovaj koncept, razmotrimo dobro poznati problem "Boolean satisfiability" (SAT). SAT problem postavlja pitanje postoji li dodjela istinitih vrijednosti varijablama u danoj Booleovoj formuli tako da formula daje vrijednost true. SAT problem je u NP jer, s obzirom na Booleovu formulu ( phi ) i dodjelu ( alpha ) vrijednosti istine njenim varijablama, može se provjeriti u polinomijalnom vremenu zadovoljava li ( alpha ) ( phi ). Ovdje je instanca (x) Booleova formula (phi), a potvrda (y) je dodjela (alpha). Verifikator (V) provjerava da li (alfa) čini (phi) istinitim, što se može učiniti u polinomnom vremenu s obzirom na veličinu (phi).
Još jedan ilustrativan primjer je problem "Hamiltonovog puta". Ovaj problem postavlja pitanje postoji li put u danom grafu koji posjećuje svaki vrh točno jednom. Problem Hamiltonovog puta također je u NP jer se, s obzirom na graf (G) i niz vrhova (P), može provjeriti u polinomijalnom vremenu je li (P) Hamiltonov put u (G). U ovom slučaju, instanca (x) je graf (G), a potvrda (y) je niz vrhova (P). Verifikator (V) provjerava da li (P) tvori Hamiltonov put, što se može učiniti u polinomijalnom vremenu s obzirom na veličinu (G).
Koncept provjerljivosti u polinomnom vremenu je važan jer pruža način karakterizacije problema koji se mogu učinkovito provjeriti, čak i ako bi pronalaženje rješenja moglo biti računalno neizvedivo. To dovodi do poznatog pitanja je li ( P = NP ), koje postavlja pitanje može li se svaki problem čije se rješenje može provjeriti u polinomnom vremenu također riješiti u polinomnom vremenu. Klasa (P) se sastoji od problema odlučivanja koji se mogu riješiti u polinomnom vremenu determinističkim Turingovim strojem. Ako je ( P = NP ), to bi značilo da svaki problem s verifikatorom polinomnog vremena također ima rješavač polinomnog vremena. Ovo pitanje ostaje jedan od najvažnijih otvorenih problema u informatici.
Jedno od ključnih svojstava NP je da je zatvoren prema redukcijama polinomnog vremena. Redukcija polinomijalnog vremena s jezika ( L_1 ) na jezik ( L_2 ) je polinomijalno vremenska izračunljiva funkcija ( f ) takva da ( x u L_1 ) ako i samo ako ( f(x) u L_2 ). Ako postoji redukcija polinomskog vremena od (L_1) do (L_2) i (L_2) je u NP, tada je (L_1) također u NP. Ovo svojstvo je ključno u proučavanju NP-potpunosti, koja identificira "najteže" probleme u NP. Problem je NP-kompletan ako je u NP i svaki problem u NP može se svesti na njega u polinomnom vremenu. SAT problem je bio prvi problem za koji je dokazano da je NP-kompletan i služi kao osnova za dokazivanje NP-potpunosti drugih problema.
Za daljnju ilustraciju koncepta polinomske vremenske provjere, razmotrite problem "Zbroj podskupa". Ovaj problem postavlja pitanje postoji li podskup zadanog skupa cijelih brojeva koji zbraja određenu ciljnu vrijednost. Problem zbroja podskupa je u NP jer, s obzirom na skup cijelih brojeva ( S ), ciljnu vrijednost ( t ) i podskup ( S' ) od ( S ), može se u polinomijalnom vremenu provjeriti je li zbroj elemenata u ( S' ) jednako ( t ). Ovdje je instanca (x) par ((S, t)), a certifikat (y) je podskup (S'). Verifikator (V) provjerava je li zbroj elemenata u (S') jednak (t), što se može učiniti u polinomnom vremenu s obzirom na veličinu (S).
Važnost polinomske vremenske provjerljivosti nadilazi teorijska razmatranja. U praktičnom smislu, to znači da se za probleme u NP-u, ako je predloženo rješenje (certifikat), može učinkovito provjeriti. To ima značajne implikacije na kriptografske protokole, probleme optimizacije i različita polja u kojima je provjera ispravnosti rješenja važna.
Ukratko, klasa NP obuhvaća probleme odlučivanja za koje se predloženo rješenje može verificirati u polinomnom vremenu determinističkim algoritmom. Ovaj je koncept temeljni u teoriji računalne složenosti i ima duboke implikacije za teoretske i praktične aspekte računalne znanosti. Proučavanje NP, polinomske vremenske provjerljivosti i srodnih koncepata kao što je NP-potpunost i dalje je živahno i kritično područje istraživanja.
Ostala nedavna pitanja i odgovori u vezi Složenost:
- Nije li klasa PSPACE jednaka klasi EXPSPACE?
- Je li P klasa složenosti podskup PSPACE klase?
- Možemo li dokazati da su Np i P klasa iste pronalaženjem učinkovitog polinomskog rješenja za bilo koji NP potpuni problem na determinističkom TM?
- Može li klasa NP biti jednaka klasi EXPTIME?
- Postoje li problemi u PSPACE-u za koje ne postoji poznati NP algoritam?
- Može li problem SAT biti potpuni problem NP?
- Može li problem biti u klasi složenosti NP ako postoji nedeterministički turingov stroj koji će ga riješiti u polinomnom vremenu
- Jesu li P i NP zapravo ista klasa složenosti?
- Je li svaki kontekstno slobodni jezik u P klasi složenosti?
- Postoji li kontradikcija između definicije NP kao klase problema odlučivanja s verifikatorima polinomnog vremena i činjenice da problemi u klasi P također imaju verifikatore polinomnog vremena?
Više pitanja i odgovora pogledajte u Složenosti