NP完全問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』

NP完全問題 (-かんぜんもんだい、NP-complete problem)は、クラスNP (Non-deterministic Polynomial) に属する問題でかつ、クラスNPのすべての問題から多項式時間帰着可能な問題である。すなわち、NPに属する問題のうちでNP困難なものである。クラスNPに含まれる問題で、あるNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の多くがこの定理によって充足可能性問題より導かれたものである。充足可能性問題がNP完全であることは1971年、スティーブン・クックによって証明された。

[編集] NP困難との違い

NP完全とNP困難の違いは、その問題自身がNPのクラスに属するかを問うか、問わないかである。このためNP完全に属する問題は全てNP困難にも属するが、NP困難の問題は必ずしもNP完全問題に属するとは限らない。

一般にNP完全とNP困難は極めて混同されやすく、特にアルゴリズムを扱う本などでは、NP完全と表記しながらもNP困難の説明をしていたり、本来はNP困難ではあってもNP完全ではない問題を「NP完全の例」として挙げる物が多々ある。

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

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