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のかたがた、ありがとうございました。こっそり修正しました。もしかして、もしかするとですか？いや、考えないようにしてるので、何も言わないで下さいね。もし私の考えてる通りならしびれすぎです。恥をさらしまくってますしねぇ。

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

Cookの定理 その7

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

カニは静かに

今回は、今日テレビで見た駄洒落をぱくりました。白いワニが見える（(c)江口寿史）

おっほん。さて、静かになったところで、そろそろCookの定理の説明も大詰めです。前回はNTMをSATに変換するためにはG1～G6を行えば良いということと、そのうちG1～G５にあたっては具体的なSAT形式を説明しました。

今回はG6のSAT形式での表現を説明します。まず、G6を再掲しましょう

　　G6　：i番目の段階(ただし、0≦i<p(n))において,

　　　　　マシンMLのi+1番目の状態は、

　　　　　i番目の状態からチューリングマシンの状態遷移関数δ

　　　　　によって決定される　　　

でした。

チューリングマシンの状態遷移関数δにかんしては、NTMの数理モデルとクラスPとNPの違いの回を参照して下さい。

最初に一番ややこしいところを説明しましょう。

実は、G6をSATに変換するときに一番ややこしいのは、ヘッドのないところのテープの状態は、次もそのままであるという、われわれにとっては一番当たり前に思えるところだったりします。

テープの番地は以下のブール変数で表せるのでした。

　　S[i,j,k]　（0≦i≦p(n),　-p(n)≦j≦p(n)+1,　0≦k≦ν）

　　　i番目の処理の段階でテープのj番地のデータはskである

そういうわけで、i番目にヘッドのないテープの番地kのデータlは、i+1番目もそのままである、というのをちょっと考えてみてみましょう。

われわれがいきなりSAT形式で考えるのは難しいので、比較的考えやすい論理式から入ることにしましょう。自分で考えたい人は、ここからしばらくは飛ばしても良いと思います。

では、まず、i番目にテープの番地kにヘッドがないというブール変数を考えます。これは簡単で、

¬H[i,k]

がTになればいいのですね。

つぎにi番目のテープの番地kのデータlは、i+1番目もそのままであると言うのは、次のように表わします。

S[i,k,l]⇒S[i+1,k,l]　（S[i,k,l]ならばS[i+1,k,l]）

これは、次のような式に置換されると言うことが分かっています。

S[i,k,l]⇒S[i+1,k,l]＝￢S[i,k,l]∨S[i+1,k,l]

真理値表をつけておきましょうか。

　　　　　　

と、なります。こういう定義なので、こういうもんだと思って下さい。つまり、AがTならばBを判定しますが、AがFであれば、この式事態は、判定せずにTとしておくという意味になります。こういう定義です。まぁ、AがFであればこの式はFとしてもいいのですが、たくさんの計算が必要な論理式においてTにしておいた方が計算がうまくいくようです。納得いかない方はネットで調べてみて下さい。分かりやすく説明してあるところがあります。これは、ある種の経験則といって良いでしょう。わたしも、大学の卒業論文でプロダクションシステムというのをやったので、だいぶこの論理式にはお世話になったのですが、確かにこれで問題はありませんでした。

さて、まとめましょう。

¬H[i,k]⇒(S[i,k,l]⇒S[i+1,k,l])

という三段論法の論理式で表わされるわけですね。変形していくと、

¬H[i,k]⇒(S[i,k,l]⇒S[i+1,k,l])＝H[i,k]∨(S[i,k,l]⇒S[i+1,k,l])

＝H[i,k]∨(￢S[i,k,l]∨S[i+1,k,l])

最後の式は括弧をとっても問題ないので、最終的に、i番目にヘッドのないテープの番地kのデータlは、i+1番目もそのままである、という事はつぎのSATの表現で表わされることになります

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

というわけです。われわれにとって一番簡単にみえることががけっこう難しいという変な感じですが、まぁこういうことです。

今回はカニもAB（エビ）もでてきたというわけで、お後がよろしいようで。

という論理式を最後に書いて終わります（笑い）

Cookの定理 その6

布団が吹っ飛んだってね、へぇ

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

今回はちょっとクイック攻撃で攻めてみました。どんどんバレーボールのようになってきてますね。でも、つまんない？そうですか、もしかしたらもしかすると、そうかもしれません、へぇ。

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

では、G1～G6です。G1～G5には、下に対応するSAT形式での表現も書いておきます。G6に関しては、ちょっと説明が長くなるので、これについては、次の回にします。Q[i,k],H[i,j],S[i,j,k]に関しては、Cookの定理　その4を参考にして下さい。ちなみに、そこから引用しておくと、次のようになります。

　　Q[i,k]　(0≦i≦p(n),　0≦k≦r)

　　　i番目の処理の段階でプログラムML(=現在の処理中のNTMの

　　　マシンML）は、状態qkとなるブール変数

　　　　（注：プログラムM即ちマシンMというと言うことは、

　　　　　　チューリングマシンの数理モデルの回の終わりの方で

　　　　　　軽く触れました）

　　H[i,j]　（0≦i≦p(n),　-p(n)≦j≦p(n)+1）

　　　i番目の処理の段階でヘッドはテープのj番地の場所を見ている

　　S[i,j,k]　（0≦i≦p(n),　-p(n)≦j≦p(n)+1,　0≦k≦ν）

　　　i番目の処理の段階でテープのj番地のデータはskである

では、NTMからSATへ変換、G1～G6です。

　　G1　：i番目の段階において、Mの状態qはただ一通りに定まる

　　　　　　{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

　　G2　：i番目の段階において、ヘッドは、

　　　　　テープ上のただ一つだけのデータを見ている

　　　　　{H[i,-p(n)],H[i,-p(n)+1],……,H[i,p(n)+1]}　,0≦i≦p(n)

　　　　　{￢H[i,j],￢H[i,j’]}　,0≦i≦p(n), -p(n)≦j<j’≦p(n)+1

　　G3　：i番目の段階において、テープ上の各データは、

　　　　　ただ一つだけに定まっている

　　　　　{S[i,j,0],S[i,j,1],……,S[i,j,ν]}　,0≦i≦p(n),　-p(n)≦j≦p(n)+1

　　　　　{￢S[i,j,k],￢S[i,j,k’]}　,0≦i≦p(n), -p(n)≦j<≦p(n)+1, 0≦k<k’≦ν

　　G4　：0番目の段階すなわち初めには、テープには、

　　　　　試行ヘッドによるインプットxが入っており、

　　　　　実行を始めるときである。

　　　　　(ただし、ここでは、x=sk1sk2…sknとする場合)

　　　　　{Q[0,0]},{H[0,1]},{S[0,0,0]},

　　　　　{S[0,1,k1]},{S[0,2,k2]},…,{S[0,n,kn]}

　　　　　{S[0,n+1,0]},{S[0,n+2,0]},…,{S[0,p(n)+1,0]},

　　　　　{S[0,-1,0]},{S[0,-2,0]},…,{S[0,-p(n),0]}

　　　　　{S[0,j,k]}の部分を説明しておくと、

　　　　　　0≦j≦nでは、xが入っており

　　　　　　その他の部分は空白が入っている、

　　　　　という意味です。

　　　　　　（s0=bということをCookの定理　その3の終わりの方で

　　　　　　　説明しています。参考にしてみて下さい）

　　　　　H[0,1]となっているのは、入力xが、

　　　　　テープの１番目から始まるためです

　　G5　：p(n)番目の段階にではMはqyの状態でxが受容されている

　　　　　{Q[P(n),1]}

　　G6　：i番目の段階(ただし、0≦i<p(n))において、

　　　　　マシンMLのi+1番目の状態は、

　　　　　i番目の状態からチューリングマシンの状態遷移関数δ

　　　　　によって決定される　　　

ということになります。

今回は以上です。次回はG6をSAT形式で表現するにはどうするかについて説明します。

それでは。

隣の客は良く柿食う客なんだってねぇ、へぇ。

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から引用しましょう。

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

Cookの定理 その4

それでは、Cookの定理、手順2の続きです。

その前に、鈴木先生、根岸先生　ノーベル賞受賞おめでとうございます。先生方に力を頂いてこのブログも復活です。

さて、とぼけた持ち味でおそらくノーベル賞受賞の先生方もしかしたら読んでおられて、なおかつ、もしかしてもしかするとご好評頂いているかも知れないこのブログですが、まず、リラックスしましょう。ラジオ体操第二ぃよぉぃ。えぇ、はしゃぎすぎですね、はい。すいません。だって根岸先生、朝のTV番組で、化学は陽子と電子と中性子の組み合わせでものを考えるんだなどと仰ってたから、つい（笑い）

さて、前回、状態遷移の記述をするための準備として、SATの節がいろいろな状態やデータに１対１で対応している（節の中の各元のブール変数は原則そのうちの一つしかTの値を取らないので）ということを説明しました。今回は、NTMのいろいろな状態を表わすブール変数について説明します。

NTMの状態を表わすブール変数を以下のように定義します。

　Q[i,k]　(0≦i≦p(n),　0≦k≦r)

　　i番目の処理の段階でプログラムML(=現在の処理中のNTMの

　　マシンML）は、状態qkとなるブール変数

　　　（注：プログラムM即ちマシンMというと言うことは、

　　　　　チューリングマシンの数理モデルの回の終わりの方で

　　　　　軽く触れました）

　H[i,j]　（0≦i≦p(n),　-p(n)≦j≦p(n)+1）

　　i番目の処理の段階でヘッドはテープのj番地の場所を見ている

　S[i,j,k]　（0≦i≦p(n),　-p(n)≦j≦p(n)+1,　0≦k≦ν）

　　i番目の処理の段階でテープのj番地のデータはskである

こうやって状態遷移に関するブール変数をようやく導入できました。プログラムMLはこのブール変数の真理値を満たします。当たり前ですが。何が言いたいかというと、プログラムMLがyesかnoを出すというのは、言語Lに対する真理関数（クラスPの問題とチューリングマシン　その１の決定問題の部分を参照して下さい）があるとして、その真理関数は、計算の途中で、 Q[i,k],H[i,j],S[i,j,k]に対して真理値を与えますよね、ということです。適正な真理関数はプログラムMLでの計算を満たす、すなわち、計算の途中ですべての Q[i,k],H[i,j],S[i,j,k]に対して真理値を与えるはずだよね、ということです。（この辺の話は、竹内外史先生のPとNPのｐ.12に書かれています。というよりこの記事自体そこを参照しています）

もう一つ言っておくとプログラムMLの計算は最高でp(n)回行われます。それ以前に終わることも当然ある訳なので、その場合は、 Q[i,k],H[i,j],S[i,j,k]は答えが出たと同じ状態とします。SATに変換するための便宜上です。

では、どうやってSATにしていくのか。それは次回で。

でも、ちょっとだけ書いておくと、ある段階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

これはある状態iの時に成り立つ、って事ですからね、念のため。

Cookの定理 その3

Cookの定理の手順２の続きです。あといくつ、「Cookの定理の手順２の続きです。」と書けば終わるかちょっと分からないぐらい続きそうですが。いけない、いけない。こんなこと書いちゃ読者が逃げちゃう。

さて、今度はテープの長さを考えます。いま考えているNTMのプログラムMLの入力x∈Σ*は、長さ|x|=nとなるとき処理回数をnの多項式で表せる、ということを前回述べました。今回、その処理回数をp(n)とすると、従ってテープの長さも＋側にp(n)、－側にも同じくp(n)あれば、どちらに行っても大丈夫な気がします。あとは、初めにヘッドがある部分を確保します。これも＋側に入れれば、最終的にはテープの長さは＋側にp(n)+１、－側にも同じくp(n)あると考えます。図に書くとこんな感じ。

え？前回の記事ではp(n)は処理時間じゃなかったの？どうでも良いんです、そんな細かいことは。どっちみちnの多項式って意味だし。(笑い）というか、本当にそうなんですよ。比例の関係なので、O(p(n))と考えても良いですが、多項式時間という考え方は言外にその意味を含んでいるって事なんです。この分野は数学の割にはこういうところはおおらかです。元々が、多項式時間という考え方自体がおおざっぱと言えばおおざっぱですからね。

さて、こういう準備をしておいて、状態遷移を考えるための準備をします。

まず、状態Qについてのブール変数を定義しておきましょう。

　Q：チューリングマシンの状態。有限集合。 

　　　状態q0を特に初期状態という。 

　　　数学的な書き方をすれば、 

　　　　　　q0∈Q（元q0は集合Qに属すると読む） 

と、以前数理モデル（NTMの数理モデルとクラスPとNPの違い）のところで定義しました。

状態Qの元のブール変数を改めて次のように定義します。

　　　q0,q1=qy,q2=qn,q3,…,qr

　　　　r=|Q|-1

つまり状態Qは次のようなブール変数で状態を定義されているということですね。

　　　Q={q0,q1,,…,qr}

qy,qnはそれぞれ、NTMがyesとnoを返したときの状態Qの値で定数です。SATがベースですからここがq1=qy,となっていれば、状態Qはyesの状態、q2=qnとなっていれば状態Qはnoの状態です。同時には満たされないのは、暗黙の約束です。当たり前ですが。

ついでに、データΓについても同様に定義しておきましょう。

　　Γ：テープにあるデータ。Σに空白記号を加えたもの。有限 

というのが定義でしたね。

同じようにデータΓの元をブール変数で以下のように定義します。

　　　s0=b,s1,…,sν

　　　　ν=|Γ|-1

s0=bのbは空白(blank）を表わしています。

状態Qと同様にデータΓも以下のような集合で表わされる、ということになります。

　　　Γ={s0,s1,…,sν}

つまり、すべてのデータに対して１対１で対応するブール変数があり、添え字がそのデータを示すという意味になります。0は特別に空白というわけです。

なかなか、見慣れない考え方ですけど、とにかくこうやるったらこうやるんです(>_<)。なれて下さいね。