Cookの定理 その1

では、Cookの定理を説明しましょう。 

ピタゴラスの定理は知ってますか？

Cookの定理じゃなかったの？と思いになったあなたは正解です。しかし、まず、定理に名前がつくということを説明したいのです。

ピタゴラスの定理は、別名三平方の定理とも言って、直角三角形においては、

（長辺の長さの二乗）＝（短辺の長さの二乗）＋（もう一つの短辺の長さの二乗）

ということでした。

（参照：Wikipedia：http://ja.wikipedia.org/wiki/ピタゴラスの定理）

ピタゴラスはWikipedia（http://ja.wikipedia.org/wiki/ピタゴラス）によると、生没年は、紀元前582年 - 紀元前496年ですから、約2500年ぐらい前にこの定理を発見したわけですね。それが現代にまで受け継がれ、これからずっとおそらく人類の文明が続く限りピタゴラスの名前は定理として残るわけです。

つまり、それくらい定理に名前がつくというのはすごいことなんですね。

Cookの定理も、Cook先生（Wikipedia：http://ja.wikipedia.org/wiki/スティーブン・クック）が発見した定理で、これも人類が続く限り永遠に受け継がれていくことでしょう。

では、Cookの定理です

【Cookの定理】

　　SAT（充足問題）はNP完全である。

[証明のあらすじ]

まず、証明のあらすじを述べます。

NP完全であるという定義は、 

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

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

　　　　　L’ ∝ L 

でした。 （NP完全とその数学的定義　その２を参照）

そこでまず、

手順１．　SATがクラスNPである

と言うことを証明します。つぎに、

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

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

ということを証明します。

おっほん。 

では証明に入りますが、その前に、簡単に手順を説明します。証明は数回に分けて説明しますが、今回は、手順１ を説明します。後の、手順２　は、ほぼ機械的な作業です。例によって例のごとく数学ですから厳密にきちんと説明します。やれやれですね（笑い）

手順１のSATがクラスNPであることは、意外と簡単ですので、自分で考えてみようという方は、今回の証明の部分を見ないようにして下さいね。

［証明］

手順１．SATがクラスNPである

SATがクラスNPであることは以下のように考えるとわかります。 

まず、m個のブール変数集合U上の節集合CがありCはr個の節を持っているとします。 

節集合Cを充足する、という問題をここではSATとしましょう。 

ところで、節集合Cを充足するためのリテラルの組を探すためのプログラムMのTM上の計算時間はどれくらいでしょう。 

ブール変数の取りうる値はT,Fの2値。これがm個あるので2をm個掛け合わせた数、つまり、O（2＾m）の時間が最大で時間がかかります。解がない、つまりSATがnoの場合もあるから、最悪の場合、総当たりの必要があるのです。 

しかし、このSATをyesとするリテラルの組がたまたま入力されていたとすると、TMで節集合Cを充足することがわかるためにかかる時間は最大でリテラルの数すなわち集合Uのブール変数の数mの2倍に、節集合Cの節の数rをかけた数、オーダーで言えばO（mr）ですから多項式時間で解けることがわかります。 

したがって、SATはクラスNPであるということが示されました。

（手順１終わり）

次回は、いよいよ本格的にCookの定理を説明し、そのことで、SATがNP完全であるということ示します。敢然に完全に（となればいいなぁ。とほほ ）！