NとかNPとか困難とか完全とか

いろいろ知識がついてきたので理解できるかなと思ったので、勉強しなおした。

まず、クラスNとNPについて。

　ともに判定問題の複雑性クラスである。つまり対象となる問題は、「Yes」、「No」で答えられる問題のみ。
判定問題の例は、ある条件を満たす整数（a,b）の組はあるか？第n番目のフィボナッチ数はm以上か？など。

よく、NPが「Not P」の略と勘違いしてしまいがちだが、これは大きな間違い。

P = deterministic Polynomial time

NP = Polynomial time

の略である。

　どっちのクラスも多項式時間で解けるが、「何を使って多項式時間で解けるか」が違う。
クラスPの問題は、決定性チューリングマシンを使って多項式時間で解ける。
一方、クラスNPの問題は、非決定性チューリングマシンを使って多項式時間で解ける。

決定性チューリングマシン(TM)とは？

　計算機を数学的に扱うために、単純化されたモデル。TMは、

・テープ

・テープの情報を読むヘッド
・機械の内部状態を記憶するメモリ

から成り立つ。"決定性"の意味は、テープから読みとった情報がxで、メモリに記憶された状態がyの場合は、毎回決まったことを実行するということ。

非決定性チューリングマシン(NTM)とは？

　テープから読みとった情報、メモリの内部状態が同じでも「毎回同じことを実行しない。次の遷移が決定されない。」

決定されないなら、どういう風に動くの？

与えられた情報から、実行しうる処理のうち、最も効率的な処理を毎回選ぶことができる。

例えば、組み合わせ最適化問題などで、今の状態から進むことのできる状態がK個ある場合、NTMは、最も早く最適解に到達できる状態へ遷移する。

ということで、分岐K、深さLの木データを探索する場合、TMの場合は、k^Lの計算が必要だが、NTMの場合は、LでOKということになる。

　ここで、注目すべきは、TMで多項式時間で解ける問題は、明らかにNTMでも多項式時間で解けるので、クラスPはクラスNPの部分集合ということである。

NP困難とNP完全

　wikipediaによると、

問題 H がNP困難のクラスに属するとは、

「NP完全問題に属するいずれかの問題 L が H へ多項式時間チューリング還元可能である」

NP困難はNP完全と同等以上に難しい。

んー、意味わからん。

ので具体例を見てみる。例として、ナップサック問題と部分和問題を取り上げる。

ナップサック問題（NP hard）
{p1, p2, ...., pn}

{c1, c2, ...., cn}

C

が与えられる。c_{i1} + c_{i2} + , ..., c_{im} <= Cとなるように{i1, i2, ..., im}を選ぶ。{p_{i1}, p_{i2}, ..., p_{im}}が最大となるような{i1, i2, ..., im}の選び方を求める。

部分和問題（NP complete）
{x1, x2, x3,.... xn}の中から任意の数字を選び、その和をyにすることができるか？

　C := y, pi := xi、ci := xiとし、ナップサック問題を解く。

もし、最大値がCならば、部分和でyが構成できる。最大値がC以下ならば、部分和でyが構成出来ない。

という手順で、部分和問題がナップサック問題へ変換できそうだ。

問題の変換は、O(n)なので、TMを用いて多項式時間でできる。

つまり、部分和問題は、ナップサック問題へ多項式時間チューリング還元可能。

　なるほど、ここまでやると「NP-hard」の定義の意味が分かった。
こうやって見ると、問題Lは問題Hの特殊形であることが分かる。問題Hが一般形の問題なので、問題Hは問題Lと同等以上に難しいという点についても納得がいく。

　ここでNP-hardはクラスNPの部分集合と誤解されがちだが、これは間違い。NP-hardの問題は、必ずしもクラスNPに属さなくてもよい。

それじゃ、次にNP-completeの定義を見てみる。

NP完全問題とは、クラスNPに属する問題でかつ、クラスNPのすべての問題から多項式時間帰着可能な問題である。

　うーん、つまりNP-completeは判定問題でなければならないと。

先ほどのNP-hardの例から分かるように、NP-completeは、すべてのNPクラスの問題の一般系と考えられる。そんな超汎用的なNP-completeは、当然NPクラスの中で一番難しいはずである。

ちょっとアバウトな議論なので、数学的に証明してみます。

NP-completeより難しい、クラスNPの問題hが存在すると仮定する。

定義より、NP-completeな問題を解くことで、問題hを解くことができる。

これは問題hがNP-copmpleteより難しいという仮定に矛盾。

よって、NP-completeはクラスNPで一番難しい。□

なんか、分かってきた気がする。

おー、そうか。

最後にwikipediaのベン図を見て、いろいろ考察する。

P!=NP予想の関係により2種類のベン図が書かれています。

・PはNPの部分集合

・NP-completeはNP-hardの部分集合(NP-completeの問題は、他の任意のNP-copmlete問題から帰着可能なため)

・クラスNPに属し、かつ、NP-hardである問題は、NP-complete

・N=NPが成り立てば、NP-complete = N(=NP)となる。

これはちょっと式を書けば分かる。（厳密な数学的証明にはなってない気はするけど。。）

NP-complete >= NP

NP-complete >= P

NP = Pより

NP-complete >= (P = NP) <= NP-complete

より、P(=NP)に含まれる問題はすべてNP-complete。　□

なんか、すっきりしたー。すっきり～～。

が、気になることが出てきた。動的計画と擬多項式時間について次のブログに書きます。