P, NP, NP-complete, NP-hard
何が知りたいって，包含関係だろう．ようやくわかった気がする．
P問題,NP問題
- P問題
P (計算複雑性理論) - Wikipedia
- NP問題
NP困難 - Wikipedia
- Nondeterministic Polynomial Problem
- 次の3つの定義は同値である．すなわち，判定問題のうち，
P問題とNP問題に(非)決定性チューリングマシンが出てくるのでそちらの定義も．
- 決定性チューリングマシン
チューリングの仮想機械は、
- 無限に長いテープ
- その中に格納された情報を読み書きするヘッド
- 機械の内部状態を記憶するメモリ
で構成され、内部状態とヘッドから読み出した情報の組み合わせに応じて、次の動作を実行する。
- ヘッドの位置の情報を読みとる
- ヘッドの位置に情報を書き込む
- 機械の内部状態を変える
- ヘッドを右か左に一つ移動する
上の動作を、機械は内部状態が停止状態になるまで反復して実行し続ける。
チューリングマシン - Wikipedia
次の説明が分かりやすいか．
決定性チューリングマシンは入力が与えられた時点で状態遷移が一意に決まっているのだけど（C言語のソースを見て、プログラムにある入力が与えられた時の制御の流れをずずーっとたどれるよね？それです）
NP: アンドロイドはしあわせか
つまり現在存在するPCはすべて決定性チューリングマシンであると．
- 非決定性チューリングマシン
理論計算機科学において、非決定性有限オートマトンのように働く制御機構を持つチューリング機械である。
非決定性チューリングマシン - Wikipedia
この説明ではよく分からない．まあ決定性チューリングマシンとは違い，3,4番がランダムだったり確率等で決まっていたりするのだろう．しかし量子コンピュータは非決定性チューリングマシンより弱いらしい．よくわからんが．
また，非決定性チューリングマシンは決定性チューリングマシンを含む．よってP問題はNP問題に含まれる．
P＝NPかP≠NPか，というのはまだ証明されていない．P≠NPという予想が大半らしいんだけど．
量子アルゴリズムの一つ，Shorの素因数分解アルゴリズムはNP完全かどうか分かっていないらしい．
良くある間違い
NPは（決定性計算において）「多項式時間で解けない」問題のクラスでもないし、「最悪時間計算量を多項式で表現できない」問題のクラスでもない。
NP: アンドロイドはしあわせか
俺はこれで覚えてた．違うんだな．何となくNPはNon-Polynomialだと思ってたし．
混同しやすいNP困難とNP完全．
- NP困難問題
クラスNPのすべての問題から多項式時間帰着可能な問題
NP困難 - Wikipedia
クラスNPに属する問題でかつ、クラスNPのすべての問題から多項式時間帰着可能な問題
NP完全問題 - Wikipedia
NP困難とNP完全の違いは赤字部があるかないかだ．だからもちろん，NP完全な問題はNP困難な問題である．そして逆は必ずしも成り立たない．
- 多項式時間変換
この概念は計算理論において問題の「難しさ」の度合いとしてよく使われる。 すなわち、A が B に多項式時間変換可能なら A を解くアルゴリズムがあってもそれ用いて B を解くことができるか分からないが、 B を解くアルゴリズムがあれば、その変換を用いれば A は自動的に解ける。つまり B は A と同等かそれより難しいと結論することができるからである。
多項式時間変換 - Wikipedia
つまり，NP困難の問題は，どんなNP問題よりも難しい(厳密には易しくない)と言える．だから「困難」とかついてるのだろう．
NP完全の「完全」は，NP完全性に基づいている．NP完全の定義より，NP完全問題とは，全てのNP問題から多項式時間で帰着される問題であるので，NPの中で最も難しい問題といえる．よって，あるNP完全問題(Cとしよう)から多項式時間で帰着可能なNP問題(Dとする)は，Cと同程度の難しさとなる．つまりDもNP完全な問題となる．これがNP完全性なんかな？
また，多項式時間での帰着先の問題とは，先ほどの問題A,Bで言うなら，BはAを一般化した問題といえる(恐らく)．また，AはBの特殊な問題である．だからBを解くアルゴリズムがあれば，Aを解くことが出来るのは自明だ．逆は一般に正しくない．
よってNP完全問題を1問でも多項式時間で解くことができれば，NP問題を全て多項式時間で解くことが可能になる．つまりNP＝Pとなる．
NP困難問題を1問でも多項式時間で解くことがでれば，やはりNP問題を全て多項式時間で解くことができる．このときはNP=Pは言えないのか．か？
ということでイメージ図
予想だけど．こんな感じだろ．
