Search on the blog

2011年6月11日土曜日

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。 □

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

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

0 件のコメント:

コメントを投稿