NP（Nondeterministic Polynomial time）完全問題
→「問題を解くアルゴリズムは存在するが、時間がかかりすぎる。しかしもっと速く解くアルゴリズムは存在しないであろう」
（例）
オーダー：O(c^n)
NP完全問題
NP完全
計算不能、決定不能
（これを解くアルゴリズムは存在しない）
計算不能
ある定数 k が存在し、
ステップで解くアルゴリズムが存在する問題のクラスを決定性多項式時間（または多項式時間）といい、P で表す。
ある定数 k が存在し、
ステップで解くアルゴリズムが存在する問題のクラスを指数時間（exponential time）といい、EXPTIME で表す。
このとき P ⊂ EXPTIME である。
（例）
- n 個の自然数に対し、その部分和が奇数になるものがあるか？
→奇数が一つでも存在すればよく、O(n) でいける
- 与えられた有効グラフ G に対し、G は長さ 3 の閉路をもつか？
→一つの頂点に接続した２つの弧を選び（{n-1}_C_{2} = (n^2-3n+2)/2）、確かめていけばよいので O(n^3)
either A or B
→yes文を最も速く実行するために都合の良いほうを実行する。
（A を実行する計算モデル、B を実行する計算モデルの２つに計算モデルがコピーされるようなイメージ）
これを用いた計算モデルを非決定性の計算モデルという。
部分和問題、分割問題などは非決定性計算モデルなら O(n) ステップ、すなわち多項式時間で解ける。
このような問題のクラスを非決定性多項式時間といい、NP で表す。
明らかに P ⊂ NP である。
ナップサック問題は NP だが P であるかどうかはいまだ不明。（P≠NP予想）
非決定性計算モデルで O(n^k) ステップで解けるものは決定性計算モデルでは高々 O(2^{n^k}) ステップで解ける。
よって NP ⊂ EXPTIME である。
NP = EXPTIME であるかどうかは未解決。
問題 A が NP で解け、NP で解けるすべての問題が A に多項式時間帰着（多項式時間還元）可能であるとき、
A は NP 完全であるという。
NP 完全問題は非決定性計算モデルで多項式ステップより少ないステップ数では解けない。
この限界を計算量の下界という。
NP 完全問題 A が P で解けるとき、NP で解ける全ての問題が P で解けることになるので NP ⊂ P となり NP = P となる。
また、NP で解けるある問題 B が P で解けないことが示されれば、B ∈ NP - P より P ≠ NP となる。
このとき全ての NP 完全問題は P で解けないことになり、難しい問題であることが証明される。
L が NP 完全であることを証明するには、
（１）L が NP で解けること
（２）NP 完全であることがわかっている問題が L に多項式時間還元可能であること
を示せばよい。
NP 完全のいずれかの問題 L が問題 H に多項式時間還元可能であるとき、H は NP 困難のクラスに属するという。
（H は NP に属するとは限らない。）
つまり、NP に属するすべての問題が H に多項式時間で還元可能。
参考文献
「NP完全問題入門」－岩田茂樹
最終更新：2012年08月31日 03:12
