NP完全問題について。。

質問

今、NP完全問題とSATについて勉強しています。
Wikiとかでも調べていて、一応自分なりに解釈をすすめて
いるところですが、言い回しが難しくて理解しきれません。

簡単に、NP完全問題とSATについてのご説明を
どなたかしていただけないでしょうか？
また良いサイトがあったら教えてください。

回答No.2

Tacosan

とりあえず「NP」とかはほかっておいて「決定問題 (判定問題)」がどのような問題かを確認してみます.
決定問題 P は問題例の集合 A と関数 φ: A → { 真, 偽 } が与えられたときに, A の任意の要素 α に対して φ(α) を求める問題です. 例えば SAT なら A は「論理式の集合」, φ は「論理式 α を真とするように α に含まれる変数に真理値を割り当てられるならば真, そうでなければ偽」という関数です. このようにみると, 決定問題 P を A と φ の組で表すことができます.
次に, 「帰着」というものを考えます. そのため, 2つの決定問題 P = (A, φ), Q = (B, ψ) を考えます. ここで, 次の性質を満たす関数 f: A → B が存在したとします:
・任意の α ∈ A に対し, φ(α) = 真であるとき, そしてそのときに限り ψ(f(α)) = 真.
このような関数 f が存在するときに, 「P から Q に帰着 (還元) 可能」といいます. イメージとしては「問題 Q が解ければ問題 P は簡単に解ける」ということです (ただし, このイメージはここでの「帰着」の定義とは異なります).
なお, 「どんな関数でもよい」としてしまうと (計算可能な問題同士が帰着可能になってしまい) 意味がないため, 関数 f の計算能力には制限をつけることが普通です. 「NP完全」とかを考える文脈では関数 f として「多項式時間で計算できるものに限る」のが普通で, このように制限した帰着を「多項式時間帰着」, あるいは単に「多項式帰着」と呼びます.
で, 「NP に属するあらゆる問題から多項式帰着可能な問題」の集合を「NP困難」, NP困難でかつ NP に属する問題を「NP完全」と呼びます.
う～ん, 結局 wikipedia に書いてあることとせいぜい同程度にしか説明できてないなぁ....

回答No.1

Tacosan

SAT は「変数を含む論理式が与えられたときに, その論理式を真とするように変数に真理値を割り当てられるかどうか」を答える問題です. 与える論理式の形によっていくつかのバージョンが存在します.
NP完全を説明しようとすると「NP」とか「帰着 (あるいは還元)」とかを出さないといけないんだけど.... この辺は理解できてますか?

補足

回答ありがとうございます。
「NP」は大丈夫ですが、「帰着」の方は理解できていません;;
数学という括りに入れているのですが、
私は情報授業の一環として学んでいるので
その辺もよろしくお願い致します。