編集この項目では、計算量について説明しています。(曖昧さ回避)」をご覧ください。time)は、複雑性クラスのひとつであり、答えがyesとなるような問いに対して、多項式時間で検証できる証拠が存在する決定問題のクラスである。NTIMEを使って次のように定義される[1]。いう同値な定義もある。p}が存在し、次の性質を満たすことを言う。編集ハミルトン閉路問題は、「与えられたグラフについて、全ての頂点を一度だけ通る閉路(ハミルトン閉路)が存在するか」という問題である。証拠を具体的に求める計算量などを考える必要がなく、ただ「存在すること」が要求されることに注意する。noであった場合は、どんな証拠であっても検証時に間違ってハミルトン閉路であるとはならないことも重要である。合成数判定問題は因数が証拠となるため、NPに属することがすぐさま分かるが、その補問題の素数判定問題ではそのような直感的で分かりやすい証拠が知られていない。p}が素数であることを多項式時間で検証できる。p-1}の素因数分解と原始根で足りるかというと厳密にはそうではない。p-1}の素因数分解が本当にすべて素因数に分解されているか、ということを検証しなければならないからである。p}が素数であることを多項式時間で検証できる。以上より、素数判定問題はNPに属する。{co-NP}}}に属することが言える。属することが証明されている[2]。NP完全であり、その例は「NP完全問題」の項に譲る。NP完全にも属さない問題の候補としてグラフ同型性判定問題(英語版)が挙げられる。包含関係図Pは、決定性チューリングマシンを使って多項式時間で解ける問題のクラスである。{NP}}}かどうかは未解決問題である(P≠NP予想)。補問題のクラスである。{NP}}\}}というクラスである。多項式階層を構成する。