NP- klassen er en meget vigtig klasse af kompleksitetsteori . Forkortelsen NP står for ” ikke-deterministisk polynomisk tid ”. Et beslutningsproblem er i NP, hvis det besluttes af en ikke-deterministisk Turing-maskine i polynomisk tid med hensyn til størrelsen af input. Intuitivt svarer dette til at sige, at vi ”hurtigt” ( polynomial kompleksitet ) kan verificere , om en kandidatløsning virkelig er en løsning. Overvej for eksempel beslutningsproblemet for den rejsende sælgerder, givet et heltal k og et sæt byer adskilt af afstande, bestemmer om der er et kredsløb med en længde på mindre end k, der passerer en gang og kun en gang gennem alle byerne. Vi kontrollerer “hurtigt”, at en kandidatløsning, her en hvilken som helst sti, virkelig er en løsning, det vil sige, at det faktisk er et kredsløb med en længde på mindre end k, og at det faktisk passerer en og kun en gang gennem alle byerne.
Et af de store åbne problemer inden for teoretisk datalogi er P ≟ NP-problemet .
Vi kalder NTIME ( t ( n )) klassen af beslutningsproblemer, der kan løses i tid af størrelsesordenen t ( n ) på en ikke-deterministisk Turing-maskine (hvor n er størrelsen på input).
Derefter NP = NTIME ( ).
På et alfabet er et sprog i NP, hvis der findes et polynomium og en deterministisk Turing-maskine i polynomisk tid , f.eks. For et ord med størrelse : (hvor betyder, at maskinen accepterer input ( x , u )).
Med andre ord er der en "ledetråd", kaldet et certifikat , som hurtigt kan bevise, at ordet findes på sproget.
De NP-komplet problemer er NP problemer er også NP-hårdt. Dette er klassens vanskeligste problemer i den forstand, at ethvert NP-problem kan reduceres til disse problemer ved visse reduktioner , især polynomreduktioner .
Mange problemer er blevet identificeret som NP-komplette, herunder SAT-problemet eller Hamiltonian Circuit
Vi har inkluderingen P NP, men et af de store åbne spørgsmål inden for teoretisk datalogi er problemet med at vide, om P = NP eller ej .
I de sædvanlige klasser kan vi også citere en opgradering: NP PSPACE .
NP tillader også at definere co-NP , den komplementære klasse. Disse to klasser udgør det første niveau i polynomhierarkiet . Den Karp-Lipton sætning , at hvis NP indrømmer kredsløb af polynomielle størrelser, så polynomiet hierarki kollapser til niveau 2.