Klasa NP, skraćenica za nedeterminističko polinomsko vrijeme, ključna je za teoriju složenosti računanja i obuhvaća probleme odlučivanja koji imaju verifikatore polinomskog vremena. Problem odlučivanja je onaj koji zahtijeva odgovor da ili ne, a verifikator u ovom kontekstu je algoritam koji provjerava ispravnost zadanog rješenja.
Važno je razlikovati rješavanje problema (izračun) i provjeru rješenja (provjera). U NP, fokus je na tome postoji li verifikator polinomskog vremena koji može potvrditi točnost rješenja.
Klasa P, koja predstavlja polinomijalno vrijeme, uključuje probleme odlučivanja koji su rješivi determinističkim Turingovim strojem unutar polinomijalnog vremena. Dakle, za svaki problem u P, ne samo da postoji algoritam polinomnog vremena za pronalaženje rješenja, već postoji i algoritam polinomnog vremena za provjeru rješenja.
Prividna kontradikcija leži u zapažanju da svaki problem u P, koji inherentno ima algoritam rješavanja polinomnog vremena, također posjeduje verifikator polinomnog vremena. Međutim, to nije u suprotnosti s definicijom NP. Definirajuća značajka NP-a je postojanje verifikatora polinomskog vremena, bez obzira na to koliko bi vremena trebalo da se pronađe rješenje. To znači da su svi problemi u P također i u NP, budući da se njihova rješenja mogu provjeriti u polinomnom vremenu.
Na primjer, razmotrite problem testiranja prostih brojeva. Ovaj se problem može postaviti na dva načina: generiranje prostih brojeva i provjera je li dati broj prost. Eratostenovo sito je algoritam za generiranje svih prostih brojeva do određene granice i to čini učinkovito, ali njegova vremenska složenost nije polinomijalna u strogom smislu koji se koristi u teoriji računalne složenosti; često se označava kao O(n log log n), što je bolje od linearnog, ali nije striktno polinomijalno prema definiciji P. S druge strane, problem provjere je li dati broj prost (testiranje prostih brojeva) je drugačiji zadatak. Učinkoviti algoritmi kao što je AKS test primarnosti omogućuju verifikaciju primarnog broja u polinomnom vremenu. Stoga problem testiranja prostih brojeva, u kontekstu provjere, spada u klasu P, kao i NP, jer se rješenje (je li broj prost) može provjeriti u polinomnom vremenu. Ovo pokazuje da iako su generiranje prostih brojeva i testiranje prostih brojeva povezani, oni uključuju različita razmatranja u smislu računske složenosti.
U zaključku, definicija NP-a kao polinomskog vremenskog verifikatora usklađena je s prirodom P. Razlika nije u koraku verifikacije, već u procesu pronalaženja rješenja: P problemi su rješivi i provjerljivi u polinomnom vremenu, dok NP problemi mogu se provjeriti u polinomijalnom vremenu, ali nije uvijek poznato mogu li se riješiti u polinomijalnom vremenu.
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
- NP je klasa jezika koji imaju polinomske verifikatore vremena
- Jesu li P i NP zapravo ista klasa složenosti?
- Je li svaki kontekstno slobodni jezik u P klasi složenosti?
Više pitanja i odgovora pogledajte u Složenosti