NP

出典: フリー百科事典『ウィキペディア(Wikipedia)』
2013年3月9日 (土) 07:55時点におけるAddbot (トーク)による版 (ボット: 言語間リンク 25 件をウィキデータ上の d:q628036 に転記)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内検索

NPとは、計算量理論における問題の集まりで、Non-deterministic Polynomial time(非決定性多項式時間)の略である。

定義

NP の定義は次の2つである、ただしこれらはお互い同値であることが証明されている。

  1. 非決定性チューリングマシンによって多項式時間で解くことができる問題。
  2. yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題。

端的に説明するときは 2番目の定義(多項式時間で検算可能)が用いられることが多い。

なお NP はクラス P 同様、判定問題のクラスであり yes/no で答えることの出来ない問題は NP には属さない。

誤解されることが多いが、NP は多項式時間で解けない問題のクラスではない(Not P の略ではない)。上記の定義は全てのクラス P の問題にも当てはまるので、クラス P は クラス NP に含まれる。

NPはPよりも大きいと予想されているが、証明されていない。P≠NP予想という。

NPに属する任意の問題と少なくとも同じくらい難しい問題をNP困難であるといい、そのうちNPに属するものをNP完全問題という。これらの概念は正確には多項式時間帰着を使って定義する。

関連項目