NP
ということは、素数であるという証拠は、 p-1 の素因数分解と原始根で足りるかというと厳密にはそうではない。 p-1 の素因数分解が本当にすべて素因数に分解されているか、ということを検証しなければならないからである。幸いにも、再帰的に素数判定の検証を行うことによって、全体として p が素数であることを多項式時間で検証できる。以上より、素数判定問題はNPに属する。合成数判定問題の結果と併せると NP ∩ co-NP {\displaystyle {\textsf {NP}}\cap {\textsf {co-NP}}} に属することが言える。なお、現在では素数判定問題は P に属することが証明されている。
NP に属するが、 P に属することが証明されていない問題の多くは NP完全であり、その例は「NP完全問題」の項に譲る。それ以外の、 P にも NP完全にも属さない問題の候補としてグラフ同型性判定問題(英語版)が挙げられる。
NP は、NTIMEを使って次のように定義される。
NP = ⋃ k ∈ N NTIME ( n k ) {\displaystyle {\textsf {NP}}=\bigcup _{k\in \mathbb {N} }{\textsf {NTIME}}(n^{k})}
つまり、非決定性チューリングマシンによって多項式時間で解ける決定問題のクラスであり、名称も Non-deterministic Polynomial time(非決定性多項式時間)の略である。また、多項式時間検証可能という同値な定義もある。言語 L が NP に属するとは、多項式時間決定性チューリングマシン M と多項式 p が存在し、次の性質を満たすことを言う。
x ∈ L {\displaystyle x\in L} ならば、ある証拠 w ∈ { 0 , 1 } p ( | x | ) {\displaystyle w\in \{0,1\}^{p(|x|)}} が存在し、 M ( x , w ) = 1 {\displaystyle M(x,w)=1}
x ∉ L {\displaystyle x\not \in L} ならば、どんな証拠 w ∈ { 0 , 1 } p ( | x | ) {\displaystyle w\in \{0,1\}^{p(|x|)}} でも、 M ( x , w ) = 0 {\displaystyle M(x,w)=0}