NTMの数理モデルとクラスPとNPの違い

NTM（非決定性チューリングマシン）についても一応の数理モデルを出しておきます。面倒なんだよね、これ。ブログに投稿するときに、いろいろと（笑い）

記号の説明をしましょう。試行コントロールというものを説明しているのでこれはまったくTMと同じになります。

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

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

　b：空白記号 

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

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

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

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

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

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

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

　 　　　　　F＝｛qy，qn｝

　　　　数学的に書くと、

　　　　　　F⊆Q

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

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

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

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

　　　ここでは、 

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

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

　　　　　  0 ： ヘッドはそのまま  

　　とする 

　δ：チューリングマシンの状態遷移関数。定義は次の通り

　　　　δ：（Q－F）×Γ　→　Q×Γ×Δ 

　　意味的には現在の状態は（Q－F）のある元で表わされ、入力はΓの元。 

　　これが関数δによって、

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

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

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

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

　　例えば、 

　　　　δ(q0，ｓ）＝（q’，s’，+1） 

　　というのは、現在の状態がq0，

　　ヘッドの置かれているテープからの入力s（s∈Γ）のとき、 

　　チューリングマシンの状態はq0からq'へ変わり、 

　　現在ヘッドの置かれているテープの状態はsからs'へ変わり

　　そのあとヘッドはテープの一つ一つ右側の入力へ移る

　　ということ 

試行コントロールという考えを抜きにする場合は関数δが異なります。関数δに状態遷移よる遷移後の状態は、遷移可能な状態全体の集合から適当な元が取られるとして、考えられます。つまり、

　δ：チューリングマシンの状態遷移関数。定義は次の通り

　　　　δ：（Q－F）×Γ　→　P（Q×Γ×Δ ）

　　　　ここで、P(S）は集合Sの部分集合全体からなる集合です

という書き方が可能、という意味です。

ただTMと言うと面倒なのでTMのことをこれからは決定性チューリングマシンと呼びます。NTMが非決定性チューリングマシンと呼ぶのと対照させるためにでもあります。

さて、ここでクラスPとクラスNPのちがいを改めて考えてみたいと思います。イメージ的にですけどね。

クラスPというのはTMで多項式時間に解ける問題の集合です。言い方を変えれば、いろんな問題をTMで解いてそれが多項式時間以内に解ける問題だけを選んだ集合です。TMの最終状態はYesやNoのどちらでもかまいません。つまり、あらかじめTMで多項式時間内に解けるように設計されている問題、と言って良いでしょう。

クラスNPは、適当な文字列が入力されたときに、これが多項式時間で解けるかどうか、ということが問題になり、結果として多項式時間で解けた問題となります。ややこしいですね。

これらの違いは初めにで説明した通りです。

しかし、様々な本や資料では、クラスNPの問題の例として、ある数mが与えられてこれが素数かどうかを判定するときに、mが何か他の素数で割れるならばmが素数でない、ということが分かる、ということが書かれています。言い方を変えれば、ある訳の分からない解き方が良く分からない問題が与えられて、解き方さえ分かってしまえば、TMで多項式時間で解けるような問題と言っても良いでしょう。ま、数学の学者さんたちの書く本ですからね。われわれには、よく分からないように書いてあるんです（笑い）