NP完全問題
NP完全問題（エヌピーかんぜんもんだい、NP-complete problem）は、クラスNP（Non-deterministic Polynomial）に属する問題でかつ、クラスNPのすべての問題から多項式時間帰着可能な問題である。すなわち、NPに属する問題のうちでNP困難なものである。クラスNPに含まれる問題で、あるNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の多くがこの定理によって充足可能性問題より導かれたものである。充足可能性問題がNP完全であることは1971年、スティーブン・クックによって証明された。
NP困難との違い
NP困難(NP-hard)は「NPに属する問題と比べ、同等以上に難しい」という意味である。一方、NP完全はあくまでNPに属する最も難しい問題なので、NP困難はNP完全と同等以上に難しい。定義上、NP困難である問題は必ずしもNPに属さなくても良いが、たまたまNPにも属する場合はNP完全と一致する。
一般にNP完全とNP困難は極めて混同されやすく、特にアルゴリズムを扱う本などでは、NP完全と表記しながらもNP困難の説明をしていたり、本来はNP困難ではあってもNP完全ではない問題を「NP完全の例」として挙げる物が多々ある。
この理由の一つとしては、大抵のNP完全問題は別のNP困難な問題の特殊なケースであることが多いためである。
もう一つの理由としてはNP完全とNP困難は計算量理論の研究者にとっては重要な違いではあるが、アルゴリズム論の研究者にはそれほど重要な違いではないためである。アルゴリズム論の研究者にとってはP≠NP予想が肯定されるなら、どちらも「多項式時間では解くことのできない問題」でしかなく、それらの問題に対してメタ・ヒューリスティックなどを適用することによってどこまで効率的に近似解を見つけられるか、多項式時間の内でどこまで小さな近似度の近似アルゴリズムを設計できるかなどが主な論点となり、両者の違いが大きく出るような状況にはならないからである。
NP完全問題の例
以下の問題は、適当に判定問題の形にして考えると、NP完全である。
