ノート:NP完全問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』
この項目のNP完全問題の例に上げられている問題のほとんどはNP完全に属していないのですが…
属しているのは充足可能性問題とハミルトン閉路問題だけです(ピンパッキング問題と一般化割り当て問題というのはよく知らないですが)。
NP困難のクラスに属する問題のうち、その問題自身もNPに属する問題をNP完全問題と言います。なのでNPに属さない(NP完全ではない)NP困難な問題というのも存在します。
NPの定義である「非決定性チューリングマシンによって多項式時間で解ける問題」だと解りづらいですが、非決定性チューリングマシンは答えが Yes か No （正確には受理か排出）の２択しかない問題しかあつかえません、これはチューリングマシンの概念が有限オートマトン(非決定性有限オートマトン)の拡張から来ていて、受理状態の到達可能性を論じるからです（到達できる、到達できないしか論じない）。
このため最小値や最大値を求める類の問題は厳密にはNPに属しません。
誤解を招く原因として「クラスNPのすべての問題から多項式時間帰着可能な問題である。」という部分をNP-完全性を満たすと表記することがあるためだと思われます（厳密にはこれは誤用）。
もうひとつの理由としてあるNP困難な問題とよく似たNP完全問題がたいてい存在するためです。例えば最大クリーク問題は「あるグラフが含む最大のクリークを求める」という問題で、これはNP完全問題ではありませんが、少し問題を変更して「あるグラフに頂点の数がk個以上のクリークを含むかどうかを求める」問題はNP完全問題になります（含んでいる場合 Yes と答えられるから）。
NP完全と困難の違いは実際にはあまり重要なことではないのですが、NP完全問題のことを「NPに属する問題のうちで、NP困難のクラスに属するものである。」と明記していますので、この例はまずいと思います。
長々と書きましたがつまりは「NP完全問題の例」の部分を大幅に変更（というか削除）しようと思うのですが、意見があったら言ってください（もしかしたら理解していることと違う場合もあるので）無いようでしたら実行します。
--U-ichi 2006年7月28日 (金) 18:40 (UTC)
とりあえず、意見がないので実行します（暫定措置としてコメントアウト）。 あれから少し調べて、少しだけ間違えていたので説明しときます。
--U-ichi 2006年8月3日 (木) 06:00 (UTC)
