NP
出典: フリー百科事典『ウィキペディア（Wikipedia）』
NPとは、計算複雑性理論における問題の複雑性クラスで、Non-deterministic Polynomial time（非決定性多項式時間）の略である。
[編集] 定義
NP の定義は次の3つである、ただしこれらはお互い同値であることが証明されている。
- 非決定性チューリングマシンによって多項式時間で解くことができる問題。
- yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題。
- 問題の探索状態を木で表したとき、yes にたどり着く最短距離が問題のサイズの多項式に比例する問題。
端的に説明するときは 2番目の定義（多項式時間で検算可能）が用いられることが多い。
なお NP はクラス P 同様、判定問題のクラスであり yes/no で答えることの出来ない問題は NP には属さない。
誤解されることが多いが、NP は多項式時間で解けない問題のクラスではない（Not P の略ではない)。上記の定義は全てのクラス P の問題にも当てはまるので、クラス P は クラス NP に含まれる。
