NP完全
NP-complete
NP完全は、クラスNPの中で最も難しい問題のクラス クラスNPに属するいずれかの問題を多項式時間で解くアルゴリズムが存在するならば、クラスNPに属するその他の問題も全て多項式時間で解くことができる NP完全性の定義
次の条件を満たす言語$ BをNP完全という
$ \mathrm{B}\in\mathrm{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完全という性質が成立する裏付けを知りたい
参考