« 不完全世界の非共有性 | トップページ | 合理性と行為 »

NP

よくある間違いをここに書くことがけっこうあるなぁ。「よくある間違い」カテゴリでも作ろうかな。

クラスNPについて。
とりあえず前置きだが
P : (deterministic) Polynomial
NP : Nondeterministic Polynomial
である。
クラス P に属する問題とは、決定問題(decision problem: 答えがyes/noの問題)のうち、決定性計算(deterministic computation, 説明は後述)によって多項式時間(Polynomial time)で解が得られる問題のことである。
多項式時間とは、その問題の解を得るまでの計算時間が、問題サイズ(problem size)の多項式関数である、ということ。
ここでの(計算複雑性理論での)時間というのは、実際の物理的な時間をどうこう言うのではなく、問題サイズに相対的な計算ステップ数(PやNPに関しては最大時間計算量worst case time complexity)を考える(問題サイズが大きくなるにつれて解を得るのに必要な時間がどう変わるか、ということ)。
多項式とは、もちろん中学で習った 2x2+3x+5 とかいうアレである。多項式時間の定義においては最大次数はどうでもよい(多項式で表せれば何でもOK)。 1/(2x2 + 3) や 2x + 1 は多項式ではない。 初学者向けに念のため。
で、重要なのが問題サイズ(problem size)の定義なのだが、よく使われるのは入力のビット数である。理解するためのイメージとしてはこれでよいのではないかと思う。つまり、このPとかNPとかいう話は、決定問題に変項が含まれていて、それらを一般的に解くアルゴリズムが存在する場合、にしか通用しない。

さて、ここまではよいとして、NPのほうが間違えて説明されているのをよく見かける。
クラス NP に属する問題とは、決定問題のうち、非決定性計算(nondeterministic computation)において問題の答えがyesの場合に多項式時間でyesと出力して終了する分岐系列が1つ以上存在する、問題のことである。
非決定性計算というのは、非決定性チューリングマシンで行われる計算である(これじゃ説明になってないね)。決定性チューリングマシンは入力が与えられた時点で状態遷移が一意に決まっているのだけど(C言語のソースを見て、プログラムにある入力が与えられた時の制御の流れをずずーっとたどれるよね?それです)、非決定性チューリングマシンでは一意に決まらない。つまり、現在ある状態だとして、次にどの状態に遷移するかに複数の可能性があるということ。実際にどの状態に遷移するかはどうにかして選択される(まあサイコロと考えればよい)。だから非決定性。
プロセッサが1つでしらみつぶしに頑張るのか、任意の数のプロセッサを使えて分岐でそれらを同時に走らせるのか(ただしほかのプロセッサの計算結果を利用することはできない)の違いだとイメージするとわかりやすいかも(後者が非決定性)。で、たまたま1つ以上のプロセッサが多項式時間でyesに当たる、と。まあ、スーパーマシンを想像しているということですな。一方であなたのパソコンは決定性計算を黙々とこなしておる。
NPの定義はいろいろな言い換えがされているようだが、よく見かけるもので、「yesの具体的解が与えられたときにそれが正しいかどうかを確かめることが(決定性計算で)多項式時間でできる問題」というのがある。これはつまり、上述の非決定性計算での分岐のたまたま当たったやつをたどって行けよ、ということ。たしかに同じだわな。NPを理解しようと試みるときは部分和問題を例にとるとわかりやすいかもしれない。

よって、NPは(決定性計算において)「多項式時間で解けない」問題のクラスでもないし、「最悪時間計算量を多項式で表現できない」問題のクラスでもない。このような誤った説明がよく出てくる。
上記の説明からわかるように、非決定性チューリングマシンは決定性チューリングマシンを含むから、PはNPに含まれる(すなわち多項式時間で解ける決定問題はすべてNPにも属すのだ)。
でも、PがNPを含むかどうか(つまりP=NPかP≠NPか、もっと言えばNP完全な問題を1つでも多項式時間で解けるか)はまだ証明されていない。P≠NPだとみんな予想してるけど。今ならこれを証明すると100万ドルもらえます。(でも実際には論文投稿したり、事務手続きしたり、・・・ でいろいろコストがかかるからねぇ・・・)

|

« 不完全世界の非共有性 | トップページ | 合理性と行為 »

Η 数理の諸問題」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/26863/3689576

この記事へのトラックバック一覧です: NP:

« 不完全世界の非共有性 | トップページ | 合理性と行為 »