NP完全問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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完全である。

[編集]

  1. ^ Tetris is Hard, Even to Approximate, Technical Report MIT-LCS-TR-865 
  2. ^ Ueda, Nobuhisa; Nagao, Tadaaki (1996), NP-completeness results for NONOGRAM via Parsimonious Reductions, Technical Report, Department of Computer Science, Tokyo Institute of Technology, TR96-0008 
  3. ^ 牟田 秀俊 (2005), “ぷよぷよはNP完全”, IEICE technical report. Theoretical foundations of Computing 105 (72): 39-44 
  4. ^ 水野 秀一; 田中 哲朗 (2008), “I.Q Intelligent QubeのNP完全性の証明”, 情報処理学会研究報告. GI, [ゲーム情報学] 28: 53-59