NP完全問題のソースを表示

'''NP完全（な）問題'''（エヌピーかんぜん（な）もんだい、{{Lang-en-short|NP-complete problem}}）とは、(1) クラス[[NP]]（{{Lang-en-short|Non-deterministic Polynomial}}）に属する決定問題（言語）で、かつ (2) クラスNPに属する任意の問題から[[多項式時間変換|多項式時間還元（帰着）]]可能なもののことである。条件 (2) を満たす場合は、問題の定義が条件 (1) を満たさない場合にも、[[NP困難|NP困難な問題]]とよびその計算量的な困難性を特徴づけている。多項式時間還元の推移性から、クラスNPに属する問題で、ある一つのNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の証明の多くはこの推移性によって[[充足可能性問題]]などから導かれている。[[充足可能性問題]]がNP完全であることは[[1971年]]、[[スティーブン・クック]]によって証明され<ref>（Stephen Cook (1971). "The Complexity of Theorem Proving Procedures". Proceedings of the third annual ACM symposium on Theory of computing. pp. 151–158.）</ref>、R. M. カープの定義した多項式時間還元<ref>（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.）</ref>によって多くの計算量的に困難な問題が NP 完全であることが示された。

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

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

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

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

; [[充足可能性問題]] 
: 変数の集合<math>X=\{ x_1, \ldots , x_n \}</math>上のクローズ<math>C_1, \ldots , C_k</math>の集合が与えられる。これらすべてを充足する変数への真偽割り当ては存在するか？という問題。英語表記の最初の三文字をとってSATともいう。クローズの長さを3に制限した3-SATもNP完全であることが知られている。ある問題がNP完全であることを示そうとするとき、リダクションによく使われる問題である。<ref>J.Kleinberg・E.Tardos『アルゴリズムデザイン』浅野孝夫ほか訳, 共立出版, 2008, 455ページ</ref>
; [[頂点被覆問題]] 
: 点カバー問題ともいう。グラフ<math>G</math>と整数<math>k</math>が与えられる。このときGにサイズが高々<math>k</math>の点カバーが存在するか？という問題。この問題の最適化版（できるだけ少ない頂点数の点カバーを求める）は2-近似アルゴリズムを持ち、この近似比はP≠NPとユニークゲーム問題のNP困難性を仮定すれば最善である。<ref>David P.Williamson・Daivid B.Shmoys『近似アルゴリズムデザイン』浅野孝夫訳, 共立出版, 2015,21ページ</ref>
; [[ハミルトン閉路問題]] 
: 有向グラフ<math>G</math>が与えられる。このとき<math>G</math>に[[ハミルトン路|ハミルトン閉路]]が存在するか？という問題。この問題の最適化版(できるだけ最大次数が小さな全点木を求める)は、最小次数全点木問題と呼ばれる。
; [[部分和問題|部分集合和問題]] 
: 部分和問題ともいう。整数<math>w_1, \ldots , w_n</math>と目標値<math>W</math>が与えられる。このとき<math>\{ w_1, \ldots , w_n \}</math>の部分集合<math>U </math>であって合計がちょうど<math>W</math>となるものは存在するか？という問題。
; [[巡回セールスマン問題]] 
: 英語の頭文字をとってTSPともいう。<math>n</math>個の点をもつ完全グラフ<math>G</math>と、<math>G</math>の任意の辺<math>e</math>に対する非負の重み<math>w_e</math>と上限<math>D</math>が与えられる。このとき重みの総和が高々<math>D</math>であるような<math>G</math>のハミルトン閉路は存在するか？という問題。この問題の最適化版(できるだけ重みが小さなハミルトン路を求める)は、P=NPでない限りいかなる定数近似アルゴリズムも持たないことが知られている。辺重みが三角不等式を満たしているような特別な場合には、1.5-近似アルゴリズム(Christofidesのアルゴリズム)が知られている。<ref>David P.Williamson・Daivid B.Shmoys『近似アルゴリズムデザイン』浅野孝夫訳, 共立出版, 2015, 43ページ</ref>
; [[ナップサック問題]] 
: 品物の集合<math>J = \{ j_1, \ldots , j_n \}</math>とその価値<math>p_j \; (j \in J)</math>と重み<math>w_j \; (j \in J)</math>とナップサックの容量<math>W</math>と要求量<math>D</math>が与えられる。<math>J</math>の部分集合<math>U</math>はそのなかの品物の重みの総和が<math>W</math>以下であるとき許容できると言われる。このとき、許容できる集合<math>U</math>であって、そのなかの品物の価値の総和が<math>D</math>以上になるようなものは存在するか？という問題。この問題の最適化版（できるだけ価値が大きな許容できる部分集合を求める）は、[[多項式時間近似スキーム]](PTAS)を持つ。つまり任意の正の数<math>0 < \epsilon \leq 1</math>に対して、<math>(1 - \epsilon)</math>-近似アルゴリズムが存在する。<ref>David P.Williamson・Daivid B.Shmoys『近似アルゴリズムデザイン』浅野孝夫訳, 共立出版, 2015,67ページ</ref>
; [[グラフ彩色|点彩色問題]] 
: グラフ<math>G</math>と３以上の上界<math>k</math>が与えられる。このとき、<math>G</math>はk-点彩色を持つか？という問題。<math>k=2</math>のときはこれはグラフが二部グラフかどうか決定する問題と同じになる。
; 時間割問題
: 時間枠数、講義リスト、受講生リストが与えられたときに、学生が受講する講義がぶつからないように講義の時間割を組む問題<ref>{{Cite book|和書 |title=チューリングの計算理論入門 |date=2014/2/20 |year=2014 |publisher=講談社 |page=189}}</ref>。
; そのほか 
: [[テトリス]]をはじめとした様々なパズルゲーム<ref>{{citation|title=Tetris is Hard, Even to Approximate|first=Erik D. last=Demaine|coauthors= Susan Hohenberger, David Liben-Nowell|id=Technical Report MIT-LCS-TR-865}}、 {{Citation|first1=Nobuhisa|last1=Ueda|first2=Tadaaki|last2=Nagao|title=NP-completeness results for NONOGRAM via Parsimonious Reductions|year=1996|place=Technical Report, Department of Computer Science, Tokyo Institute of Technology|id=TR96-0008}}、{{citation|title=ぷよぷよはNP完全|author=牟田 秀俊|journal=IEICE technical report. Theoretical foundations of Computing|volume=105|number=72|pages=39-44|year=2005}}、{{citation|title=I.Q Intelligent QubeのNP完全性の証明|author=水野 秀一|coauthors=田中 哲朗|journal=情報処理学会研究報告. GI, [ゲーム情報学] |year=2008|volume=28|pages=53-59}}</ref>もNP困難であることが知られている。

== 脚注 ==
{{reflist}}

== 参考文献 ==
* J.Kleinberg・E.Tardos『アルゴリズムデザイン』浅野孝夫ほか訳, 共立出版, 2008

* David P.Williamson・Daivid B.Shmoys『近似アルゴリズムデザイン』浅野孝夫訳, 共立出版, 2015

{{複雑性クラス}}

{{DEFAULTSORT:えぬひいかんせんもんたい}}
[[Category:NP完全問題|*]]
[[Category:計算問題]]
[[Category:数学の問題]]
[[Category:数学に関する記事|NPえぬひいかんせんもんたい]]