NP完全性のメモ（１）
0. まとめ
0.1 P, NP, NP完全
計算複雑度のクラスP (complexity class P)とは、多項式時間で解ける問題の集合である。
計算複雑度のクラスNP (complexity class NP)とは、多項式時間で検証可能な問題の集合である。
問題を解くより検証の方が簡単なので、 まはた
のどちらかである（が多くの研究者は
だと信じている）。
問題が以下の全てを満たすならば、NP完全 (NP-complete)であるという。
- その問題がNPに属する。かつ、
- NPに属するすべての問題に対し、多項式時間でその問題に帰着可能である場合。
NPに属する問題の中で、最も難しい問題からなる集合(NPの部分集合) がNP完全な問題である。
NP完全な問題はNPに属する他のどの問題よりも同じかより難しいので、もしもNP完全な問題の一つについて多項式時間で解ける（クラスPに属する）ことが証明できれば、NPに属するすべての問題が多項式時間で解ける (である) ことが証明されるという強力なものである（だからこそ、
であると信じられている）。
0.2 NP完全性の証明
すでにNP完全であることが証明された問題があるので、それを利用して以下の2つを確かめることにより行う。
一つ目は対象の問題の難しさの上限を確認するもの（少なくとも検証は多項式時間でできる）、二つ目は対象の問題の難しさの下限を確認するもの（少なくともNP完全な問題よりは同じか難しい）である。
1. はじめに
NP完全性についての理解が怪しかったので、学生時代の教科書を（年末年始休暇に）引っ張り出して読み直しました。 以下の本「アルゴリズムイントロダクション 第3巻 精選トピックス」の第36章がNP完全性の章です。
上記の本は分冊版（全3巻）ですが、現在は原著第3版の翻訳（統合版）が出ており、こちらの第34章が該当の内容のようです（未確認）。
以降は主に本の説明の流れに沿って用語の定義などをまとめています。見出しのタイトルは私がつけたものです。 元の第36章の各節のタイトルは以下です。
修正中…
