NP完全問題

NP完全(な)問題(エヌピーかんぜん(な)もんだい、: NP-complete problem)とは、(1) クラスNP: Non-deterministic Polynomial)に属する決定問題(言語)で、かつ (2) クラスNPに属する任意の問題から多項式時間還元(帰着)可能なもののことである。条件 (2) を満たす場合は、問題の定義が条件 (1) を満たさない場合にも、NP困難な問題とよびその計算量的な困難性を特徴づけている。多項式時間還元の推移性から、クラスNPに属する問題で、ある一つのNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の証明の多くはこの推移性によって充足可能性問題などから導かれている。充足可能性問題がNP完全であることは1971年スティーブン・クックによって証明され[1]、R. M. カープの定義した多項式時間還元[2]によって多くの計算量的に困難な問題が NP 完全であることが示された。

NP困難との違い

[編集]

NP困難 (: NP-hard) は「NP完全な問題と比べ、同等またはそれ以上に難しい」という意味である。一方、NP完全はあくまでNPに属する問題で、NP困難である問題は必ずしもNPに属さなくてもよいという違いがある。

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

これは定義をよく理解せずに議論していることが主な理由だが、多くのNP完全な問題は、組合せ最適化問題の問題例にコスト/ゲインの閾値を与えた決定問題として定義されていることも一因であろう。

NP完全な問題の例

[編集]

以下の問題は、NP完全である。NP完全な問題はすべて同じ難しさというわけではなく、最適化問題に直したときに問題によって近似可能性が大きく異なることがある。

充足可能性問題
変数の集合上のクローズの集合が与えられる。これらすべてを充足する変数への真偽割り当ては存在するか?という問題。英語表記の最初の三文字をとってSATともいう。クローズの長さを3に制限した3-SATもNP完全であることが知られている。ある問題がNP完全であることを示そうとするとき、リダクションによく使われる問題である。[3]
頂点被覆問題
点カバー問題ともいう。グラフと整数が与えられる。このときGにサイズが高々の点カバーが存在するか?という問題。この問題の最適化版(できるだけ少ない頂点数の点カバーを求める)は2-近似アルゴリズムを持ち、この近似比はP≠NPとユニークゲーム問題のNP困難性を仮定すれば最善である。[4]
ハミルトン閉路問題
有向グラフが与えられる。このときハミルトン閉路が存在するか?という問題。この問題の最適化版(できるだけ最大次数が小さな全点木を求める)は、最小次数全点木問題と呼ばれる。
部分集合和問題
部分和問題ともいう。整数と目標値が与えられる。このときの部分集合であって合計がちょうどとなるものは存在するか?という問題。
巡回セールスマン問題
英語の頭文字をとってTSPともいう。個の点をもつ完全グラフと、の任意の辺に対する非負の重みと上限が与えられる。このとき重みの総和が高々であるようなのハミルトン閉路は存在するか?という問題。この問題の最適化版(できるだけ重みが小さなハミルトン路を求める)は、P=NPでない限りいかなる定数近似アルゴリズムも持たないことが知られている。辺重みが三角不等式を満たしているような特別な場合には、1.5-近似アルゴリズム(Christofidesのアルゴリズム)が知られている。[5]
ナップサック問題
品物の集合とその価値と重みとナップサックの容量と要求量が与えられる。の部分集合はそのなかの品物の重みの総和が以下であるとき許容できると言われる。このとき、許容できる集合であって、そのなかの品物の価値の総和が以上になるようなものは存在するか?という問題。この問題の最適化版(できるだけ価値が大きな許容できる部分集合を求める)は、多項式時間近似スキーム(PTAS)を持つ。つまり任意の正の数に対して、-近似アルゴリズムが存在する。[6]
点彩色問題
グラフと3以上の上界が与えられる。このとき、はk-点彩色を持つか?という問題。のときはこれはグラフが二部グラフかどうか決定する問題と同じになる。
時間割問題
時間枠数、講義リスト、受講生リストが与えられたときに、学生が受講する講義がぶつからないように講義の時間割を組む問題[7]
そのほか
テトリスをはじめとした様々なパズルゲーム[8]もNP困難であることが知られている。

脚注

[編集]
  1. ^ (Stephen Cook (1971). "The Complexity of Theorem Proving Procedures". Proceedings of the third annual ACM symposium on Theory of computing. pp. 151–158.)
  2. ^ (Richard M. Karp (1972). "Reducibility Among Combinatorial Problems" (PDF). In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103.)
  3. ^ J.Kleinberg・E.Tardos『アルゴリズムデザイン』浅野孝夫ほか訳, 共立出版, 2008, 455ページ
  4. ^ David P.Williamson・Daivid B.Shmoys『近似アルゴリズムデザイン』浅野孝夫訳, 共立出版, 2015,21ページ
  5. ^ David P.Williamson・Daivid B.Shmoys『近似アルゴリズムデザイン』浅野孝夫訳, 共立出版, 2015, 43ページ
  6. ^ David P.Williamson・Daivid B.Shmoys『近似アルゴリズムデザイン』浅野孝夫訳, 共立出版, 2015,67ページ
  7. ^ 『チューリングの計算理論入門』講談社、2014年2月20日、189頁。 
  8. ^ Tetris is Hard, Even to Approximate, Technical Report MIT-LCS-TR-865 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 牟田 秀俊 (2005), “ぷよぷよはNP完全”, IEICE technical report. Theoretical foundations of Computing 105 (72): 39-44 水野 秀一; 田中 哲朗 (2008), “I.Q Intelligent QubeのNP完全性の証明”, 情報処理学会研究報告. GI, [ゲーム情報学] 28: 53-59 

参考文献

[編集]
  • J.Kleinberg・E.Tardos『アルゴリズムデザイン』浅野孝夫ほか訳, 共立出版, 2008
  • David P.Williamson・Daivid B.Shmoys『近似アルゴリズムデザイン』浅野孝夫訳, 共立出版, 2015