NP完全とその数学的定義 その１

まず、NP完全(NP complete)という概念について、数学的にきちんと定義しましょう。ちなみに、竹内外史先生はNP−完備とご著書に書かれていますが、私の知ってる範囲ではNP完全のほうが一般的なようです。

さて、まず、定義しておきたい記号があります。それは、多項式時間で変換できるという記号についてです。これを、以下、

　∝

と言う記号で表わします。例えば、言語L1⊆Σ1*とL2⊆Σ2*があったとします。Σはブランク抜きの入力記号の集合を表わし、Σ*はその入力記号による任意の有限の長さの文字列の集合全体を表わしたのでしたね。

このとき、L1からL2へ多項式変換があるときに

　L1∝L２

と表わします。∝は比例という記号だったのを思い出してもらうと余計ややこしくなってよろしいかと思います。（笑い）

さらに、そのまえに、実は定義しておく必要があったことがらを忘れてました。（ぉぃ）

どういうことかというと、L1からL2へ変更するための関数の定義という奴です。これがないと、数学じゃありません。この話はあくまで集合論を基礎においた数学の話だということを、読者は忘れないでください。私も忘れないように心がけたいと思います。 （えっへん）

さて、ここからは、竹内外史先生の「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 の略である

とあります。上記２を解説しておくと有限な入力文字列のすべての集合Σ1のすべての元xについて、xが言語L1の元であればf によってL2へ1対1で多項式時間以内に変換され、xと変換後のf(x)の意味は意味的にはまったく同じ意味であるということになるでしょうか。

これらがきちんとされた上で、

　L1∝L２

が定義されるのでした。あぶなかった。忘れてた。

これが定義されると、NP完全を定義するための次の第一の補題が成立することが言えます。

補題1.1

　

補題1.1の解説をしておくと、まず、2行目は1行目の対偶を取っているだけなので、1行目だけを証明すればいいでしょう。

証明としては、関数f  を計算するTMプログラムをMfとし、さらにL1，L2を決定するTMプログラムをそれぞれ、M1，M2とするとします。

まず、x∈L1からf で変換すると、多項式時間内に言語L2の入力f(x)に変換されます。

つぎに、言語L2に変換された入力f(x)をM2で処理すると多項式時間内にyesとの結論が得らるのは、まさにL1でxがM1で多項式時間内にyesとの結論を得られるときのみです。言い換えると、言語L1がクラスPに属するときのみです。

以上、ややこしいですが、これが論理的な思考という奴です。数学は几帳面ですね、本当に。次回はもう一つの補題を説明して、NP完全について定義します。