NP完全問題

NP完全問題とは

NP完全問題（NP-complete problem）は、計算複雑性理論における重要な概念です。これは以下の2つの条件を満たす決定問題（Yes/Noで答えられる問題）を指します。

1. クラスNPに属する: 問題の答えが与えられたとき、それが正しいかどうかを多項式時間（問題のサイズに対して多項式で表せる時間）で検証できる。
2. NP困難である: クラスNPに属する任意の問題から、多項式時間で変換（帰着）できる。つまり、もしNP完全問題を多項式時間で解くアルゴリズムが見つかれば、すべてのNP問題を多項式時間で解けることになる。

この定義から、NP完全問題はNPに属する問題の中で最も難しい部類に位置づけられます。

NP困難との違い

NP困難（NP-hard）とは、「NP完全問題と同等か、それ以上に難しい」という意味です。NP困難な問題は必ずしもNPに属する必要はなく、検証可能性の条件がありません。この点がNP完全問題との大きな違いです。しばしば、NP完全とNP困難は混同されがちですが、正確な理解が重要です。

NP完全問題の例

以下に代表的なNP完全問題の例を挙げます。これらの問題は、一見すると単純に見えるかもしれませんが、効率的な解法を見つけるのが非常に難しいことが知られています。

1. 充足可能性問題 (SAT)
- 与えられたブール変数の集合と、それらの変数を含むいくつかの節（OR演算で繋がれたリテラル）があるとき、すべての節を真にするような変数の真偽値の割り当てが存在するかを問う問題。
- 特に、各節のリテラル数が3つに制限された3-SATもNP完全。
- NP完全性の証明において、リダクションの基準としてよく使われる。

2. 頂点被覆問題 (Vertex Cover)
- グラフとその中の頂点数 k が与えられたとき、グラフのすべての辺が少なくとも一つの頂点に含まれるような頂点の集合で、その大きさが k 以下であるものが存在するかを問う問題。
- 最適化版は、近似アルゴリズムで解くことが可能だが、厳密解を効率的に求めるのは難しい。

3. ハミルトン閉路問題 (Hamiltonian Cycle)
- 与えられた有向グラフ内に、すべての頂点を一度ずつ通る閉路（ハミルトン閉路）が存在するかを問う問題。
- 最適化版は、最小次数全点木問題を求める問題につながる。

4. 部分集合和問題 (Subset Sum)
- 与えられた整数の集合と目標値 W があるとき、その集合の部分集合で、要素の合計がちょうど W となるものが存在するかを問う問題。

5. 巡回セールスマン問題 (Traveling Salesman Problem, TSP)
- 与えられた都市の集合と、都市間の距離が与えられたとき、すべての都市を一度ずつ訪問して出発点に戻る経路で、総距離が与えられた上限 D 以下であるものが存在するかを問う問題。
- 最適化版は、総距離が最小となる経路を求める問題。
- 一般の場合、定数近似アルゴリズムが存在しないことが知られているが、特別な条件を満たす場合には近似解法が存在する。

6. ナップサック問題 (Knapsack Problem)
- 品物の集合と、それぞれの価値、重さ、ナップサックの容量が与えられたとき、容量を超えない範囲で、価値の合計が与えられた値 D 以上になるように品物を選ぶことができるかを問う問題。
- 最適化版は、ナップサックに入れる品物の価値の合計を最大化する問題。[多項式時間近似スキーム]を持つ。

7. 点彩色問題(Graph Coloring)
- 与えられたグラフと色数kが与えられたときに、隣接する頂点が同じ色にならないようにk色以内で頂点を塗り分けられるかどうかを判定する問題
- k=2のときはグラフが二部グラフかどうかを判定する問題と同じになる。

8. 時間割問題
- 時間枠数、講義リスト、受講生リストが与えられたときに、学生が受講する講義がぶつからないように講義の時間割を組む問題。

その他のNP困難問題

テトリスなどのパズルゲームもNP困難であることが知られています。これは、ゲームの複雑さや難易度を理解する上で興味深い事実です。

まとめ

NP完全問題は、計算機科学において非常に重要な概念です。これらの問題を効率的に解く方法が見つかっていないため、その解決は理論的なブレークスルーにつながる可能性があります。同時に、現実の問題がNP完全であることを知ることは、近似解法やヒューリスティックアルゴリズムなどのアプローチを検討する上で重要な指針となります。

参考文献

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

もう一度検索