OTMの数理モデルと計算量およびそのクラス

ところで、OTM（オラクルチューリングマシン）の計算量のクラスは一体どうなっているのでしょう。そして、その計算量のクラスとP=NP?問題との関連はどうなっているのか。今回はそういうことを述べます。決してギャグを言ってるわけではないので間違わないように(笑い)

まずは、お約束の数理モデルの方から。OTMはオラクルテープを持っているのでその入力はTMと空白文字がないだけで同じである（つまり下の記号ではΣ）のですが、それに対するマシンの状態が増えます。また状態遷移関数も若干異なります。（青い文字の部分が異なる部分）

　Σ：入力。専門的にいうと入力記号の有限集合 

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

　b：空白記号 

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

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

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

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

　　　ここまではTM同じだが、追加される項目として、

　　　　　オラクルを読み出すために停止の状態qh

　　　　　　　オラクルの状態qc

　　　　　再活動の状態qr

　　　があります。いずれも集合Qに属する元

　F：チューリングマシンの終了状態の集合

　　　　たとえば、結果が2値の場合は結果yesを表わすqyと、

　　　　結果noを表わすqnとしたときは

　 　　　　　F＝｛qy，qn｝

　　　　数学的に書くと、

　　　　　　F⊆Q

　　　（FはQの部分集合と読む。でもイメージ的には４≦５。

　　　　カントールの集合論を思い出してください）

　Δ：ヘッドを移動させる命令の集合。

　　　テープの入力データの中に付記されている 

　　　ここでは、 

　　　　　-1 ： ヘッドをテープの一つ左の入力へ移動

　　　　　+1 ： ヘッドをテープの一つ右

　　　　　  0 ： ヘッドはそのまま  

　　とする 

　δ：OTMの状態遷移関数。定義は次の通り

　　　　δ：（Q－F－｛qh，qy｝)×Γ×Σ　→　Q×Γ×Δ ×Δ 

　　意味的には現在の状態は（Q－F－｛qh，qy｝）のある元で表わされ、

　　入力はΓの元とオラクルの入力のΣ。 

　　これが関数δによって、

　　　次の状態の集合はQの元、

　　　次のテープの状態はΓの元、 

　　　これに加えて、ヘッドの移動の命令Δと

　　　オラクル用テープヘッドの文の移動の命令Δ

　　によって表現されます、ということ 

さて、TMにNTMがあるように、OTMにもNOTM（非決定性オラクルチューリングマシン）があります。

OTMで多項式時間以内で解ける問題、多項式時間OTMプログラムのクラスをPAやPBのように表わします。（本来はAやBはPの右肩にあるがここではWebでのテキスト表現の便宜上右下に書く）PAはオラクルAを使った多項式OTMプログラムのクラスという意味です。

一方、NOTMで多項式時間以内で解ける問題、多項式時間NOTMプログラムのクラスをNPAやNPBのように表わします。

クラスPAとクラスNPAの関係は、クラスPとクラスNPに似ていますしかし、これらクラスについての関係性についてはすでに解明が終わっていて、

　　　PA＝NPA   かつ　PB≠NPB

つまり、オラクルによってどちらにもなりうる、ということが分かっています。

（T.Baker,J.Gill,R.Solovay,Relativizaions of the P=?NP question, SIAM Journal on Computing 4,431-442,1975.)

竹内外史先生のご本（「PとNP」p.32)によると、もともとP=NPは機能関数論から発生しており、オラクルを用いて一般的な問題クラスCをCAの形にすることを相対化と言うらしい。私も良く知らんので、覚えておくように（笑い）

しかし、この結果によって、次のことが言えるようである。引き続き竹内先生のご本から引用しよう。

「上のT.Baker,J.Gill,R.Solovayの結果は、われわれの問題とする計算量の問題は機能的関数論とは本質的に異なる問題であって、機能関数論のアナロジーはもはや、P≠NPのような本質的な問題に役に立たないことを意味してるといって良い」

この定理の証明はここでは示しません。理由は、煩雑にも成るし、第一その証明ぐらいは自分で読んで分かるようになることがこのブログの目的だからでもあるからです。めんどうくさい訳じゃないし、ギャグを言っているわけでもないので間違わないように（笑い）