Cookの定理 その2

Cookの定理の証明の手順2.の説明をここからは行います。今日は本当にまじめに話します。私だっていっぱいいっぱいなんです＞＜

手順２．　NTMで完全にランダムな入力をTMで処理するという部分が

　　　　　多項式時間内でSATに変換できる

でした。

そういうわけで、まず、クラスNPの言語Lとそれを処理するプログラムMLがあったとして、これに用いられる記号は、いつぞやのNTMの数理モデルの回（NTMの数理モデルとクラスPとNPの違い）で説明したモデルがあるとします。MLは当然、定義からして多項式時間で処理されます。（多項式時間以内でyesという答えを出すというのが定義でしたよね。）

NP完全とその数学的定義　その１の回でこういうのを書いたの覚えてますか？

「ここからは、竹内外史先生の「PとNP」p.8−9を引用します。そちらの方が読者も安心でしょうからね（笑い）

さて、まずL1からL2への変換する関数fの数学的表現としては、

　f　:Σ1*→Σ2*

で表わします。そして、これが成立する条件として、次のように定めます。

　１．　f を計算する多項式時間のTMのプログラムがあるとする

　２．　すべてのx∈Σ1*について、

　　　　　x∈L1  iff  f(x)∈L2

　　　ここでA iff B は‘AとBとが同等である’と言うことを表わす

　　　iffは if and only if の略である

とあります。」

この考え方を用いると、NTMをSATへというこの証明の部分は、このNTMで処理される入力文字列の集合をΣ*としたとき、多項式変換関数fLは入力x∈Σ*のすべてのxについて、

　　　　x∈L　iff　fL(x)∈SAT

という関数があるかどうかだと考えられます。

かなり内容が難しくなってきましたね。そういうわけで、今回は、あと一つだけ、処理回数の定義をして終わりたいと思います。

いま考えているNTMの入力x∈Σ*を処理する回数は、入力xの長さをn（これを絶対値の記号を使い|x|=nと書いたりもします）としたときに、上記のように多項式時間で処理されると言うことが前提ですから、処理時間と処理回数は元々TMの定義から比例の関係にあるので、つまりは処理回数も処理時間もnの多項式となります。

そこで、一般的に入力xの長さをnとしたときのNTMがyesという答えを出すときの処理時間の多項式をp(n)という具合に表現します。定義からしてTMがyesというときの答えを出す時間も同等ですよね。

そうすると、プログラムMLを処理する時間Tはこれもnの関数になり、表現はTML(n)と表せます。

つまりは、TML(n)は、適当なnの多項式p(n)に対して

　　　TML(n)≦p(n)

が成立するということになりますよね。