アルゴリズム

P、NP、NP完全、NP困難の違いは?[具体例で解説]

2021年12月14日

本記事の内容

本記事では、クラスP, クラスNP, NP完全, NP困難について解説しています。それぞれの違いを、具体的な問題の例と共に説明します。

  • クラスP
  • クラスNP
  • P対NP問題
  • NP完全
  • NP困難

クラスP

定義

クラスPとは、以下で定義されます。

クラスP
問題の大きさ \(n\) の多項式時間で解くことのできる判定問題の集合

ここで、判定問題とは、Yes/No で答えられる問題のことです。

端的に言えば、クラスPは「効率的なアルゴリズムが見つかっている判定問題全体」を意味します。

クラスPに属する問題の例

偶数の判定

与えられた整数 \(k\) が偶数か否か。

整数 \(k\) を \(2\) で割った余りが \(0\) ならば「Yes」、 \(1\) ならば「No」となります。

計算は1回だけしか行わないので、時間計算量は \(O(1)\) となります。

数列のソートの判定

長さ \(n\) の数列 \(\{a_i\}\) が小さい順にソートされているかどうか。

数列の先頭から隣合う要素の大小を順番に調べ、すべての組について先頭側が小さければ「Yes」、一つでも当てはまらないものがあれば「No」となります。

計算量は「Yes」の時が最も多く、\(n-1\) 回大小比較を行うことになります。

したがって、時間計算量は \(O(n)\) となります。

線形不等式の判定(実数)

\(A\in \mathbb{Z}^{m\times n}, \bm{b}\in \mathbb{Z}^m\) とします。
このとき、\(A\bm{x}\leq\bm{b}\) を満たす \(\bm{x}\in\mathbb{Q}^n\) が存在するかどうか。

L. G. Khachiyan[2] のアルゴリズムによって、多項式時間で解くことができます。

\(\mathbb{Z}, \mathbb{Q}\) はそれぞれ、整数全体の集合、有理数全体の集合を表します。

クラスNP

定義

クラスNPとは、以下で定義されます。

クラスNP(class nondeterministic polynomial)
非決定的計算機(後述)であれば、多項式時間で解くことのできる判定問題の集合。言い換えると、ある解があらかじめ与えられた場合、多項式時間で解くことができる判定問題の集合。

"NP" は "not polynomial time" ではないことに注意してください。"nondeterministic polynomial time"(非決定的計算機で多項式時間で解ける)という意味です。

端的に言えば、クラスNPは「効率的に解くアルゴリズムが見つかっていない判定問題の集合」であり、「その判定問題のYesとなる解が与えられたとき、それが本当に正しいのかを診断するのは多項式時間で済むような判定問題の集合」です。

クラスPの問題は、多項式時間で判定ができるので、クラスPはクラスNPに含まれます

PとNPの包含関係
$$ P\subseteq{NP} $$

非決定的計算機とは

非決定的計算機(Non-deterministic computer)は、端的に言えば、理想的な計算機のことです。

非決定性チューリングマシン(Non-deterministic turing machine: NTM)とも呼ばれます。

どのように「理想的」なのかということに関して、二通りの解釈があります。

  1. 処理の分岐のたびに都合の良い選択ができる、幸運な計算機
  2. 並列に計算するためのプロセッサをいくらでも用意できる、理想的な並列計算機

ここでは具体例として、NPに属する判定問題で有名な「ハミルトン閉路問題」を扱います。

与えられたグラフにおいて、全ての頂点を一度だけ通り、出発点に戻る閉路が存在するか否か(ハミルトン閉路問題)

左のグラフにおいて、全ての頂点を一度だけ通って元に戻る閉路を考えると、右のような閉路を考えることができるので、答えは「Yes」となります。

これがハミルトン閉路問題です。

この問題を実在する計算機(決定性チューリングマシン)に解かせるにはどうすればよいか、考えてみましょう。

グラフの頂点の数を \(n\) とすると、ハミルトン閉路の可能性がある経路は \(n!\) 通りあります。

しかし、\(n!\) は指数関数のオーダの計算量で、\(n\) が大きくなると、解くのに膨大な時間がかかります。

例えば、\(n=20\) のときを考えると、\(n!\sim 2.4\times 10^{18}\) であり、\(1\) ステップ \(1\,\mathrm{ns}\) の計算機を仮定すると、\(77\) 年近くかかることになります。

階乗の近似式として、 \(n!\sim\sqrt{2\pi n}\frac{n^n}{\mathrm{e}^n}\) というものがあります。これを「スターリングの近似」といいます。

では、非決定的計算機ではどうでしょうか。

まず、一つ目の解釈「幸運な計算機」で考えます。

この計算機は都合の良い選択をできるので、ハミルトン閉路が成り立っている道について、最初に調べることができます。

したがって、\(O(n)\) の計算量で「Yes」を出すことができます。

これは、予めハミルトン閉路が与えられていれば、それを多項式時間で診断できるのと同等です。

予め与えられた解は "certificate" とも呼ばれます(文献[3]より)。

次に、二つ目の解釈「理想的な並列計算機」で考えます。

\(n!\) 個のプロセッサを用意すれば、全ての経路を同時に調べることができます。

そして、あるプロセッサでハミルトン閉路が見つかれば、「Yes」と答えることができます。

この場合も、「Yes」を出すまでに \(O(n)\) の計算量で済みます。

これが非決定的計算機の解釈になります。

ハミルトン閉路がないグラフを与えられた場合、非決定的計算機を使ったとしても、多項式時間で「No」という判断を出すことはできません。「No」という判断は、全てのプロセッサから「No」を受け取って初めて判断できますが、\(n!\) 個のプロセッサから「No」を受け取るのには、\(O(n^n)\) の時間がかかってしまいます。

P対NP問題

P対NP問題とは、クラスNPに属し、かつクラスPに属さないような判定問題が存在するか否かが分かっていない、という問題です。

定式化すると、以下になります。

P対NP問題
$$ P=NP\hspace{3mm} \mathrm{or}\hspace{3mm} P\neq NP $$

先ほどの「ハミルトン閉路問題」について、クラスNPに属していることは分かっていますが、クラスPに属していない・・・ことは証明されていません。

現時点では、\(P\neq NP\) と予想する研究者が多数派のようです(文献[1]より)。

P対NP問題は、投稿日時点(2021年12月)で決着がついておらず、クレイ数学研究所(Clay Mathematics Institute)のミレニアム懸賞問題の一つになっています(クレイ研究所のページ:P vs NP problem)。

クラスNP完全

定義

クラスNP完全は、以下で定義されます。

クラスNP完全(class NP-complete)
判定問題 \(Q\) が以下の二条件を満たすとき、\(Q\) はクラスNP完全に属する。
  1. \(Q\) はクラスNPに属する
  2. もし\(Q\) がクラスPに属することが分かれば、クラスNPに属する任意の問題はクラスPになる(\(P=NP\))

ある判定問題 \(Q\) がクラスNP完全に属するとき、クラスNPの他の問題は、多項式時間で問題 \(Q\) に変換することができます。

クラスNP完全に属する問題は、数多く見つかっています。

クラスNP完全に属する問題の例

充足可能性問題

与えられた論理式が \(1\) となるような変数の割り当てが存在するか否か

充足可能性問題(Satisfiability problem: SAT)は、クックの定理(Cook's theorem)によってNP完全であることが証明されています。

例えば、以下の論理式 \(f(x_1,x_2,x_3)\) を考えてみましょう。

$$ f(x_1,x_2,x_3) = x_1(\bar{x}_1+\bar{x}_2)(x_2+\bar{x}_3) $$

ただし、論理和を \(+\)、論理積を変数の積で表しています。

この例では、\( (x_1,x_2,x_3) = (1,0,0)\) のとき、\(f(x_1,x_2,x_3)=1\) になります。よって、答えは「Yes」です。

ハミルトン閉路問題

与えられたグラフにおいて、全ての頂点を一度だけ通り、出発点に戻る閉路が存在するか否か

ハミルトン閉路問題は、NP完全であることが分かっています。

線形不等式の判定(整数)

\(A\in\mathbb{Z}^{m\times n}, \bm{b}\in \mathbb{Z}^m\) とします。
このとき、\(A\bm{x}\leq\bm{b}\) を満たす \(\bm{x}\in\mathbb{Z}^n\) が存在するかどうか。

クラスPに属する問題でも同様の問題を紹介しましたが、ベクトル \(\bm{x}\) に整数の制約をつけると、NP完全に属する問題になります。

頂点クリーク問題

与えられたグラフが、頂点数 \(k\) のクリークを持つか否か

頂点クリーク問題(vertex clique problem)も、クラスNP完全に属することが分かっています。

クリーク(clique)とは、全ての頂点が辺で結ばれている部分グラフのことです。

上図のグラフにおいて、頂点数 \(3\) のクリークを持つでしょうか。

答えは「Yes」です。赤で囲ったところは、頂点数 \(3\) のクリークになっています。

頂点彩色問題

与えられたグラフについて、辺の両端が同じ色にならないように頂点を \(k\) 色で塗分けることができるか

頂点彩色問題(vertex-colorability problem)も、クラスNP完全に属していることが分かっています。

上図のグラフについて、 \(3\) 色だけ使って、辺の両端の色が重複しないように塗分ける方法はあるでしょうか。

答えは「Yes」です。赤・青・緑の三色を図のように塗分けることができます。

クラスNP困難

定義

クラスNP困難とは、以下で定義されます。

クラスNP困難(class NP-hard)
判定問題以外も含む一般の問題 \(Q\) が、クラスNP完全に属する問題 \(Q'\) を含むとき、\(Q\) はクラスNP困難に属する。

クラスNP困難に属する問題の例

巡回セールスマン問題

各辺に非負実数のコストが定められたグラフにおけるハミルトン閉路のうち、コストの和が最小になる経路を求めよ。

巡回セールスマン問題(traveling salesman problem)が解けたとき、グラフにハミルトン閉路が存在することも判定できたことになります。

よって、巡回セールスマン問題はハミルトン閉路問題を部分問題として含んでおり、NP困難であるといえます。

ナップサック問題

価値と重量が定められた \(n\) 種類の品物を重量制限のある袋に詰める。このとき、重量制限を超えない範囲で袋に詰めた物の価値の総和を最大にするような組み合わせを求めよ。

ナップサック問題(knapsack problem)も、NP困難に属することが分かっています。

この問題は、整数計画問題(integer programming problem)として定式化でき、動的計画法(dynamic programming)などで解くことができます。

テトリス

4行以上、あるいは8列以上のテトリスをプレイする(文献[5])

S. Asif et al. [5] は、4行以上、あるいは8列以上のテトリスをクリアすることがNP困難に属することを示しました。

様々なゲーム

スーパーマリオブラザーズ、ドンキーコング、ゼルダの伝説、メトロイド、ポケモンなど(文献[6])

G. Aloupis et al. [6] は、任天堂の様々なゲームにおいて、NP困難な課題が含まれることを示しました。

参考文献など

  1. 杉原厚吉(2001)『データ構造とアルゴリズム』共立出版
  2. L. G. Khachiyan, ``A polynomial algorithm in linear programming,'' Doklady Akademii Nauk., Vol. 244, No. 5, Russian Academy of Sciences, 1979.
  3. B. Korte and J. Vygen, Combinatorial Optimization, 6th ed. Springer, 2018 <https://link.springer.com/book/10.1007%2F978-3-662-56039-6> (Accessed on 12 Dec. 2021)
  4. クレイ研究所公式ページ, <http://www.claymath.org/>(参照日:2021年12月12日)
  5. S. Asif, M. Coulombe, E. D. Demaine, M. K. Demaine, A. Hesterberg, J. Lynch, and M. Singhal,''Tetris is NP-hard even with O(1) Rows or Columns,'' Journal of Information Processing, vol. 28, pp. 942-958, 2020. doi: https://doi.org/10.2197/ipsjjip.28.942
  6. G. Aloupis, E.D. Demaine, A. Guo, and G. Viglietta, ''Classic Nintendo games are (computationally) hard,'' Theoretical Computer Science, vol. 586, pp.135-160, Jun. 2015.

-アルゴリズム