クラスNPと非決定性チューリングマシン

今回は、非決定性チューリングマシンを説明することで、クラスNPについて説明します。これで、P=NP?問題がどういう問題か分かる、と思ったら大間違いです。世の中そんなに甘くはないんです。しかし、まぁ、だいたいのことは分かるんじゃないかなぁ、多分だけど。

では、非決定性チューリングマシン。まず、図2を見ていただきましょう。

元々のチューリングマシンに試行コントロールと試行ヘッドというものが付け加わりました。しかし、基本的にはチューリングマシンであることには変わりありません。違うのは、試行コントロールと試行ヘッドによって入力文字列がまったく適当にテープに書き込まれ、元々のチューリングマシンに相当する部分はその入力に従って、その入力が決定問題としてYesかNoかということを判定します。

これを非決定性チューリングマシン（nondeterministic Turing machine）と言います。頭文字を取ってNTMとも言います。ここでも、いちいち非決定性チューリングマシンと書くのは面倒なので、かっこよくNTMと書きます。でも、私も良くNTMって何だったっけ、と思い出すのに苦労しますけど。（ぉぃ）ちなみに竹内外史先生は、非決定論的マシンとご著書では書いておられるので覚えておくように。

この非決定論的チューリングマシンで多項式時間内に解けるような問題のことをクラスNPと言います。NPはNonditerminisitic Polynomial timeの最初の二つの単語の頭文字を取っています。つまりNTMのNとクラスNPのNは同じnonditerminisiticから取られてるということです。