　読み込み中...

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完全ではない問題を「NP完全の例」として挙げる物が多々ある。

この理由の一つとしては、大抵のNP完全問題は別のNP困難な問題の特殊なケースであることが多いためである。例としてはハミルトン閉路問題は巡回セールスマン問題の特殊例として考えられるし、部分和問題はナップサック問題の特殊例である。

もう一つの理由としてはNP完全とNP困難は計算複雑性理論の研究者にとっては重要な違いではあるが、アルゴリズム論の研究者にはそれほど重要な違いではないためである。アルゴリズム論の研究者にとってはP≠NP予想が肯定されるなら、どちらも「多項式時間では解くことのできない問題」でしかなく、それらの問題に対してメタ・ヒューリスティックなどを適用することによってどこまで効率的に近似解を見つけられるか、多項式時間の内でどこまで小さな近似度の近似アルゴリズムを設計できるかなどが主な論点となり、両者の違いが大きく出るような状況にはならないからである。