NP完全問題 - mrsekut-p

NP完全問題

クラスNPに属し、かつNP困難であるような問題のこと

定義

以下の2条件を満たす問題$ \varphi

$ \varphi\in NP

$ \forall\alpha\in NPに対して、$ \alpha\le^p_m \varphi

NP困難mrsekut.icon

ある問題がNP完全であることを証明するためには、以下の2つを示さないといけない

その問題がクラスNPに属していることと、

任意のクラスNPに属する問題から多項式時間還元可能だということ

こちらは、3SAT問題から多項式時間還元であることを言えばいいらしい

なんでそれで必要十分になるのか #??

というよりも3SAT問題でなくても、何か一つのNP完全問題から多項式時間還元を示せばよいのかな #??

NP完全問題の例

証明 ref 『計算理論の基礎 3』.icon p.332

証明 ref 『計算理論の基礎 3』.icon p.344-

証明 ref 『計算理論の基礎 3』.icon p.351-