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

定義

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

\varphi\in NP

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

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

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

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

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

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

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

NP完全問題の例

証明 ref p.332

証明 ref p.344-

証明 ref p.351-