NP完全とかNP困難とか

基礎知識

友人からNP完全とNP困難について分かりやすく説明してくれと言われたので、頑張ってまとめました。
時間計算量に関しては↓のエントリ参照。
時間計算量に関して-- http://d.hatena.ne.jp/nsasaki/20110426/1303807572

そもそもNPって何？って話から。
Wikipediaより

NPとは、計算複雑性理論における問題の複雑性クラスで、Non-deterministic Polynomial time（非決定性多項式時間）の略である。
定義
NP の定義は次の3つである、ただしこれらはお互い同値であることが証明されている。

  1. 非決定性チューリングマシンによって多項式時間で解くことができる問題。
  2. yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題。
  3. 問題の探索状態を木で表したとき、yes にたどり着く最短距離が問題のサイズの多項式に比例する問題。

端的に説明するときは 2番目の定義（多項式時間で検算可能）が用いられることが多い。
なお NP はクラス P 同様、判定問題のクラスであり yes/no で答えることの出来ない問題は NP には属さない。
誤解されることが多いが、NP は多項式時間で解けない問題のクラスではない（Not P の略ではない)。上記の定義は全てのクラス P の問題にも当てはまるので、クラス P は クラス NP に含まれる。

と書いてあるけど分かりませんよね。。
専門知識がない人(と言っても高校数学レベルは必要ですが)には2.が一番分かりやすいかと。。
有名な例は3-SAT。

3-SAT

3-SATを理解するためにまず、論理演算の話を。

論理演算とは、x_{i}に関して、

  • x_{i}のとりうる値は1か0
  • \overline{x_{i}}はx_{i}の値を反転させたもの。
  • x_{i}+x_{j}はx_{i},x_{j}のいずれかが1ならば1。それ以外なら0となる。論理和。
  • x_{i}x_{j}はx_{i},x_{j}の両方が1ならば1。それ以外なら0となる。 論理積。

という演算体系のこと。

3-SATとは
(x_{1}+\overline{x_{3}}+\overline_{x_{2}})(x_{2}+x_{3}+\overline_{x_{1}})
のように3個の論理和と任意個の論理積で構成され、その値が1になるような組み合わせが存在するか。という問題。
ここでは(x_{1},x_{2},x_{3})=(1,1,0)が答えの一つ。

変数がn個存在するときについて考えると、一般的な解き方が判明していないので総当たりで調べることになる。
この場合、問題を解くのに最悪のケースで2^{n}回トライすることになる。
また、各トライでは論理積の数がm個のとき3mn回の計算で答えが出る。(各xについて調べるため)
これはwikipediaさんの2.の定義で言うところのyesとなる証拠が与えられればそれが正しいのかどうか多項式時間で判定できる例である。

NPについて

くだけた言い方をすると、

なんか証拠が与えられた時にそれを確かめるのは変数に対して、確かめるのにかかる時間はその変数の多項式で調べられる。
しかし、何も証拠がないとどれくらいかかるかは分からないかもしれないよ。

っていう感じ。

ちなみにクラスPというのは

何も証拠がなくても多項式で解ける問題。

だからPはNPに含まれると。
で、クラスPとクラスNPは等しくないだろうという予想されている。
この予想はP≠NP予想と呼ばれている。
これが正しいのかそれとも間違っているのかという証明はされていない。
また、クレイ数学研究所のミレニアム懸賞問題の一つとして、この問題に対して100万ドルの懸賞金がかけられている。

このP≠NP予想を証明するのに1971年にスティーブン・クックが定式化した概念がNP完全。

NP完全とは
  • クラスNPに属し、
  • クラスNPに属する他の全問題が多項式時間帰着

される問題のことである。

  • クラスNPであることが証明されていて
  • かつクラスNPに属する他の全問題,たとえばあるクラスNPと証明されている問題でn個の変数がある。それに対して、nの多項式時間で何らかの操作(例えば式変形)を行い、前者の問題と同等に変換できる。

ということである。
NP完全な問題がP≠NPを満たすならば、他のすべてのクラスNPに関して、P≠NPが証明されたということになる。
これによってすべての研究をNP完全に集中させようということ。
なお例で出した3-SAT問題は有名なNP完全問題！

一方、

NP困難とは
  • クラスNPに属しているか分からない
  • クラスNPに属する他の全問題が多項式時間帰着される問題(i.e.NP完全から多項式時間で帰着される)

を満たす問題のことである。