1970年初頭にStephen CookとLeonid Levinが独立に見つけた

NP完全は、クラスNPの中で最も難しい問題のクラス

NP完全な問題のことをNP完全問題という

クラスNPに属するいずれかの問題を多項式時間で解くアルゴリズムが存在するならば、クラスNPに属するその他の問題も全て多項式時間で解くことができる

これなんで #??

NP完全性の定義

次の条件を満たす言語BをNP完全という

\mathrm{B}\in\mathrm{NP}

NPに属する全てのAが、Bに多項式時間還元である

この性質のことをNP困難という

定理

もし、BがNP完全であり、かつ、B\in PならばP=NP

もし、BがNP完全であり、かつ、NPに属するCに対してB\le_p Cならば、CはNP完全である

NP完全の嬉しいこと

理論方面

P\neq \mathrm{NP}を示そうとする場合、NP完全に焦点を絞ればいい

NP完全は、NPの中で一番むずかしいものなので。

P=\mathrm{NP}を示そうとする場合は、NP完全問題の一つが、多項式時間で解けることを示せばいい

実用方面

NP完全な問題を解くために、多項式時間で解くアルゴリズムを探す時間を節約できる

P\neq\mathrm{NP}であることが前提だが

何も知らない状態だとホンマにこれ成り立つんか？？ってなるな

NP完全という性質が成立する裏付けを知りたい

クラスNPに属すが、NP完全でない、と証明された問題とかってあるの？

参考