NP完全な問題の例
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/13 06:02 UTC 版)
以下の問題は、NP完全である。NP完全な問題はすべて同じ難しさというわけではなく、最適化問題に直したときに問題によって近似可能性が大きく異なることがある。 充足可能性問題 変数の集合 X = { x 1 , … , x n } {\displaystyle X=\{x_{1},\ldots ,x_{n}\}} 上のクローズ C 1 , … , C k {\displaystyle C_{1},\ldots ,C_{k}} の集合が与えられる。これらすべてを充足する変数への真偽割り当ては存在するか？という問題。英語表記の最初の三文字をとってSATともいう。クローズの長さを3に制限した3-SATもNP完全であることが知られている。ある問題がNP完全であることを示そうとするとき、リダクションによく使われる問題である。 頂点被覆問題 点カバー問題ともいう。グラフ G {\displaystyle G} と整数 k {\displaystyle k} が与えられる。このときGにサイズが高々 k {\displaystyle k} の点カバーが存在するか？という問題。この問題の最適化版（できるだけ少ない頂点数の点カバーを求める）は2-近似アルゴリズムを持ち、この近似比はP≠NPとユニークゲーム問題のNP困難性を仮定すれば最善である。 ハミルトン閉路問題 有向グラフ G {\displaystyle G} が与えられる。このとき G {\displaystyle G} にハミルトン閉路が存在するか？という問題。この問題の最適化版(できるだけ最大次数が小さな全点木を求める)は、最小次数全点木問題と呼ばれる。 部分集合和問題 部分和問題ともいう。整数 w 1 , … , w n {\displaystyle w_{1},\ldots ,w_{n}} と目標値 W {\displaystyle W} が与えられる。このとき { w 1 , … , w n } {\displaystyle \{w_{1},\ldots ,w_{n}\}} の部分集合 U {\displaystyle U} であって合計がちょうど W {\displaystyle W} となるものは存在するか？という問題。 巡回セールスマン問題 英語の頭文字をとってTSPともいう。 n {\displaystyle n} 個の点をもつ完全グラフ G {\displaystyle G} と、 G {\displaystyle G} の任意の辺 e {\displaystyle e} に対する非負の重み w e {\displaystyle w_{e}} と上限 D {\displaystyle D} が与えられる。このとき重みの総和が高々 D {\displaystyle D} であるような G {\displaystyle G} のハミルトン閉路は存在するか？という問題。この問題の最適化版(できるだけ重みが小さなハミルトン路を求める)は、P=NPでない限りいかなる定数近似アルゴリズムも持たないことが知られている。辺重みが三角不等式を満たしているような特別な場合には、1.5-近似アルゴリズム(Christofidesのアルゴリズム)が知られている。 ナップサック問題 品物の集合 J = { j 1 , … , j n } {\displaystyle J=\{j_{1},\ldots ,j_{n}\}} とその価値 p j ( j ∈ J ) {\displaystyle p_{j}\;(j\in J)} と重み w j ( j ∈ J ) {\displaystyle w_{j}\;(j\in J)} とナップサックの容量 W {\displaystyle W} と要求量 D {\displaystyle D} が与えられる。 J {\displaystyle J} の部分集合 U {\displaystyle U} はそのなかの品物の重みの総和が W {\displaystyle W} 以下であるとき許容できると言われる。このとき、許容できる集合 U {\displaystyle U} であって、そのなかの品物の価値の総和が D {\displaystyle D} 以上になるようなものは存在するか？という問題。この問題の最適化版（できるだけ価値が大きな許容できる部分集合を求める）は、多項式時間近似スキーム(PTAS)を持つ。つまり任意の正の数 0 < ϵ ≤ 1 {\displaystyle 0<\epsilon \leq 1} に対して、 ( 1 − ϵ ) {\displaystyle (1-\epsilon )} -近似アルゴリズムが存在する。 点彩色問題 グラフ G {\displaystyle G} と３以上の上界 k {\displaystyle k} が与えられる。このとき、 G {\displaystyle G} はk-点彩色を持つか？という問題。 k = 2 {\displaystyle k=2} のときはこれはグラフが二部グラフかどうか決定する問題と同じになる。 そのほか テトリスをはじめとした様々なパズルゲームもNP困難であることが知られている。
※この「NP完全な問題の例」の解説は、「NP完全問題」の解説の一部です。
「NP完全な問題の例」を含む「NP完全問題」の記事については、「NP完全問題」の概要を参照ください。
- NP完全な問題の例のページへのリンク
