Az NP osztály egy nagyon fontos osztálya a komplexitás elmélet . Az NP rövidítés jelentése „ nemdeterminisztikus polinomiális idő ”. A döntési probléma van NP ha úgy döntenek, egy nem-determinisztikus Turing-gép a polinomiális időben képest a méret a bemenet. Intuitíven ez azt jelenti, hogy azt mondjuk, hogy „gyorsan” ( polinomiális komplexitás ) ellenőrizhetjük, hogy a jelölt megoldás valóban megoldás-e. Vegyük például a döntési probléma az utazó ügynöki , aki adott egy egész k és egy sor városban elválasztott távolságok, meghatározza, hogy van egy kör hossza kisebb, mint k , hogy a bérletek csak egyszer végig városok. „Gyorsan” ellenőrizzük, hogy a jelölt megoldás, itt bármilyen út, valóban megoldás, vagyis azt, hogy ez valóban egy k- nál kisebb hosszúságú áramkör, és valóban egyszer és egyszer halad át az összes városon.
Az elméleti számítástechnika egyik nagy nyitott problémája a P ≟ NP probléma .
Hívjuk NTIME ( t ( n )) osztályába döntési problémák amelyeket meg lehet oldani az időben a nagyságrendben t ( n ) egy nem-determinisztikus Turing-gép (ahol n a bemenet mérete).
Ekkor NP = NTIME ( ).
Ábécére , a nyelv van NP , ha létezik egy polinom és a determinisztikus Turing-gép polinomiális időben , mint egy szó méretű : (ahol azt jelenti, hogy a gép elfogadja a bemeneti ( x , u )).
Más szavakkal, van egy "nyom", az úgynevezett tanúsítvány , amely gyorsan be tudja bizonyítani, hogy a szó a nyelven van.
Az NP-teljes problémák NP-problémák is NP-nehézek. Ezek az osztály legnehezebb problémái abban az értelemben, hogy az NP bármely problémája ezekre a problémákra redukálható bizonyos redukciókkal , különösen a polinom redukciókkal .
Sok problémát azonosítottak NP-teljesnek, beleértve a SAT problémát vagy a Hamilton-kört
Megvan a P NP befogadása, de az elméleti számítástechnika egyik legnagyobb nyitott kérdése az a probléma, hogy tudjuk-e, hogy P = NP .
A szokásos órákon idézhetünk egy frissítést is: NP PSPACE .
Az NP lehetővé teszi a ko-NP , a komplementer osztály definiálását is . Ez a két osztály alkotja a polinomiális hierarchia első szintjét . A Karp-Lipton-tétel kimondja, hogy ha az NP beengedi a polinomméretű áramköröket, akkor a polinomhierarchia összeomlik a 2. szintre.