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

では、早速前回の記事の続きに入りましょう。と思ったけど、前回の証明分かりましたか？もうちょっとだけ説明しておくと、あの証明はその前の定義をそのまま持ってきてるだけなんですよね。クラスPの友達はクラスPただそれのみというだけのことです。

さて、こんどは、友達の友達は皆友達、世界に広げよう友達の輪、輪ぁ。的な補題です。（何のことか分からない人はお父さんお母さんに聞いてみましょう。）

というのも、クラスNPの問題はその核となるNP完全な問題に多項式時間で変換できて、それが多項式時間で変換できたものがクラスPと同じか、もしくはクラスPと同じになるためには多項式時間に変換できるか、というのがP=NP?という問題を解く大筋になってるわけだからですね。

補題1.2

　L1∝L2，　L2∝L3，　ならば　L1∝L3

証明必要でしょうか？かんたんですから、今回の記事では書かずにおきます。

ところで、このような証明を一般的には三段論法とかいいますよね。たとえば、カラスは鳥である。鳥は空を飛ぶ。だからカラスは空を飛ぶ、みたいな。間違ってもカラスの代わりにペンギンとしてはだめですよ、がちょーん（笑い）（谷啓さんには心よりご冥福を申し上げます）

そういう、上記の例のように三段論法が常に正しいわけではないわけです。正しくするには正しくするなりの手続きが要りますよね。そういう手続きをきっちりとやるのが数学です。言い換えれば、論理思考は、きっちりと分かるものとその他で考えます。その他に入ったものは、その中でまたきっちりと定義できるものだけで考える。そうやって、問題を分かるもの、きちんと定義できるものとして、どんどん分けて考えていこう、というのが論理的な考え方なのだと私は思います。

つまり、白か黒か、ではなく、真っ白か、その他。というのが論理思考の本来のあり方だと私は思うのですよ。

さて、少し話はわき道に入りましたけれど、準備はできました。NP完全の定義をしましょう。実は簡単なんですが、ここまで手間がかかるんですね、数学って奴は本当に（笑い）

【NP完全の定義】

　１．L∈NP　（言語LがクラスNPに属する）

　２．すべてのクラスNPに属する言語L’について

　　　　L’ ∝ L 

　この定義を日本語に直しておくと、

　　「NP完全とは、クラスNPに属するすべての言語L’が

　　　多項式時間でクラスNPに属するある言語Lに変換できる場合、

　　　その言語LのことをNP完全な言語という」

といったところでしょうか

こうなると、前にも言いましたが、P=NP?の問題は、NP完全な言語があるか？そして、NP完全な言語を多項式時間に変換してクラスPに属するか、という問題に分けられるわけです。

さて、NP完全な言語があるかという前に、NP完全な言語が別のNP完全な言語に多項式時間で変換できる、ということをきちんと数学的に証明しておきましょう。補題1.1と同様の証明ですから難しくはありません。いやぁしかし、数学は本当に几帳面だ（笑い）

補題1.3

　L1∈NP, L2∈NP,言語L1はNP完全でさらにL1∝L2ならば言語L2もNP完全である

というわけです。

さて、今回はここまでにしておきましょう。つぎは、Cookの定理の証明です。Cookの定理を簡単に説明しておくと、クラスNPに属する充足問題というものがNP完全であるということを証明するというものです。つぎぐらいから、また難易度が上がりますから、覚悟をしておいてください。一応、私のつまらないギャグは逃げ道を与えてるだけなんですからね、そういう人に。ギャグが面白くないから読まないようにしたってｗ。決して、本当につまらないギャグしか書けないわけではありませんから、間違えないように（笑い）