Cookの定理 その8

それでは、Cookの定理、手続き２の7回目です。

さて、前回から、なんとチリの鉱山事故の救出劇で33人全員が救出されるというすばらしいニュースがありました。（執筆当時：今回はこの記事を再掲し始めてここまで東北・関東大震災一週間を迎えました）時間というのは、ちゃんと把握してるようで、なんだか夢を見ているような、そんな感覚ですね。そして、このCookの定理の説明もようやく最後の回を迎えました。

では、そろそろCookの定理の説明ですけど、NTMをSATに変換する項目G6の説明の続きです。

G6は簡単に言うと、マシンMLのi番目の状態をi+1番目の状態へ遷移する状態遷移関数δについてということになるでしょう。前回は、ヘッドのないテープのi+1番目の状態はi番目の状態と同じ、ということについて説明しました。残りは、i+1番目のヘッド、ヘッドのある部分のテープの状態、およびマシンの状態です。

これは、もういちど、状態遷移関数の定義（NTMの数理モデルとクラスPとNPの違いの回を参照）から、論理式でまず考えてみましょう。でも、更にその前に、論理式を考える前に、文章で、この問題を考えてみることにします。われわれの思考をまずはっきりさせとかないとですね。

では、ヘッドのある場所で、i番目の状態からi+1番目の状態で変化するのは、ヘッドの位置、マシンの状態、テープの状態を表わす、ブール変数、H[i,j],Q[i,k],S[i,j,l]はすべて変化するでしょう。つまり、ヘッドの位置jはj+Δとなり、そのときのマシンの状態はqkからqk’へと変化し、テープの状態slはsl’と変化します。では、前回やったA⇒Bという論理式を使って、この状態遷移を考えてみるとどうなるか？そう難しくないので、自分で考えたい人は、以下を見ないでしばらく自分で考えても良いと思います。

さて、まず、問題になるのは、前提条件Aの部分ですね。結論となるBの方はそのまま表わせばいいでしょう。ここはちょっと迷うところですが、要するに、すべての条件がそろっていることを、それぞれのブール変数でその状態遷移を別々の論理式で書けば良いという分かったような分からないような日本語を論理式として表わすと次のようになります。

H[i,j]∧Q[i,k]∧S[i,j,k]⇒H[i+1,j+Δ]　

H[i,j]∧Q[i,k]∧S[i,j,k]⇒Q[i+1,k’]

H[i,j]∧Q[i,k]∧S[i,j,k]⇒S[i+1,j,l]

0≦i≦p(n),　-p(n)≦j≦p(n)+1,　0≦k≦r,　0≦l≦ν

テープのj番地の状態が変わることだけに注意すればこの論理式もそう問題なく分かると思います。H[i,j]∧Q[i,k]∧S[i,j,k]という条件とはブール変数H[i,j],Q[i,k],S[i,j,k]がすべてTのとき、という意味ですよね。このときに、それぞれが、H[i+1,j+Δ],Q[i+1,k’],S[i+1,j,l]へと状態遷移するという意味です。

SATへ変形するには、これを、論理式ORで結ぶように変形すると良いのでした。一つだけやれば、後は同様ですからH[i,j]の部分だけやると、

H[i,j]∧Q[i,k]∧S[i,j,k]⇒H[i+1,j+Δ]

＝￢(H[i,j]∧Q[i,k]∧S[i,j,k])∨H[i+1,j+Δ]

＝￢H[i,j]∨￢Q[i,k]∨￢S[i,j,k]∨H[i+1,j+Δ]　（ド・モルガンの法則を用いてます）

というわけで、最終的には以下のような三つのSATの形式に直せるわけです。

{￢H[i,j],￢Q[i,k],￢S[i,j,k],H[i+1,j+Δ]}　

{￢H[i,j],￢Q[i,k],￢S[i,j,k],Q[i+1,k’]}　

{￢H[i,j],￢Q[i,k],￢S[i,j,k],S[i+1,j,l]}　

0≦i≦p(n),　-p(n)≦j≦p(n)+1,　0≦k≦r,　0≦l≦ν

となります。

あとは、このマシンMLが結論qy,もしくはqnを出すまでの計算中は、

δ(qk,ql)=(qk’,sl’,Δ)

でqk’,sl’,Δが表わされ、結論が出た場合つまりqk∈{qy,qn}のときは、

qk＝qk’,sl＝sl’,Δ＝0

となるわけです。

これで、NTMをSAT変換するG1～G6のすべての説明が終わりました。最終的には節C＝G1∪G2∪G3∪G4∪G5∪G6というSATがプログラムMLが入力xを受容する計算になっているということになります。あとは、この変換が多項式時間内に終わる、ということがNP完全の条件ですが、それぞれのステップが数回であることと、入力xの長さがn、プログラムMLの長さ有限で固定されている（つまり定数）、プログラムの状態遷移のステップ数も最大でp(n)であるなどを考えると、多項式時間でこの変換は済むという事は自明ですので、Cookの定理は証明されたということになります。

今回は、ちょっとだけ内容が濃いかったですけどどうだったでしょうか。わたしのここまでついてきて頂いたことに本当に感謝します。また、こっそり誤りを指摘して頂いた米国PBSのかたがた、ありがとうございました。こっそり修正しました。もしかして、もしかするとですか？いや、考えないようにしてるので、何も言わないで下さいね。もし私の考えてる通りならしびれすぎです。恥をさらしまくってますしねぇ。

ちょっとおしゃべりでした。では、また次回、できればすぐにでも（笑い）