Cookの定理 その5

それでは、Cookの定理、手順2の４回目です。

NTMの状態を表わすブール変数Q[i,k],H[i,j],S[i,j,k]を定義して、次のような事を書いて前回は終わったのでした。

ある段階iでマシンMの状態が決まってるとしたときつまり、i番目の処理の時、マシンMの状態がquとなるuが存在して、それは以下のような集合のSATとして表わされると言うことになります。

　　{Q[i,0],Q[i,1],……,Q[i,r]}　,0≦i≦p(n)

　　{￢Q[i,j],￢Q[i,j’]}　,0≦i≦p(n),　0≦j<j’≦r

それでは、まず、あたらしい朝が来た♪ええ、前回のネタ引っ張りすぎですね、はい。自分でも面白くないの分かってますから突っ込まないように。

さて、ちょっとフェイントをかけてリラックスしてもらったところで説明しましょう。上記の記述で、

　　{Q[i,0],Q[i,1],……,Q[i,r]}　,0≦i≦p(n)

の部分はi番目の状態で、マシンMの状態はこのどれかである、という意味ですね。次が少し難しいかも知れません。

　　{￢Q[i,j],￢Q[i,j’]}　,0≦i≦p(n),　0≦j<j’≦r

ですが、これは、意味的に同じ論理式に形を変えると次のように変形できます。

￢Q[i,j]∨￢Q[i,j’]＝￢（Q[i,j]∧Q[i,j’]）

上記、論理式の左側はたんにSATの形式をそのまま論理式に置き換えただけです。右側は、ド・モルガンの法則(Wikipedia：http://ja.wikipedia.org/wiki/ド・モルガンの法則)を用いた変形です。ちょっと不思議に思う人は、真理値表を自分で書いてみれば同じになることが確認できます。要するにド・モルガンの法則というのは、ごく分かりやすくいうと、「論理式の２項演算子において、ばらばらだった否定をまとめるとANDがORにORがANDになって否定が括弧の外に出ます。また、逆もそうなります。」という法則です。すなわち、この論理式の意味は、Q[i,j]とQ[i,j’]が同時にTになることはないと言うことを表わしてる、ということですね。また、ド・モルガンさんみたいに法則に自分の姓がつけられるぐらい偉くなりましょうという教訓を表わしてもいます（嘘だけどちょっとだけ本当）。

つまりは、あのi番目の処理の時、マシンMの状態はQ[i,0],Q[i,1],……,Q[i,r]のどれかで表わされて、なおかつ、その中の一つだけである、という意味ですね。

さて、こんな具合にして、NTMをSATに変換していくわけです。それには、つぎのG1～G6の様に書けます。ちなみにG1はここまで説明した段階iでマシンMの状態です。竹内外史先生の「PとNP」p.13から引用しましょう。

という予定だったんですが、ここまでが思ったより長くなったのでそれは次の回で。ちょっと、切りが悪いですしね。