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は特別に空白というわけです。

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