お久しぶりです。以前、Cookの定理を説明してから随分経ちました。いろいろありましたが、ようやくこの「P=NP?問題についての覚え書き」を再開する事ができそうです。もっとも、私の能力不足のせいなので本当に読者の皆様にはご迷惑をおかけして申し訳ありませんでした。まずは、お詫びを申し上げます。
再開するに当たって、これからの進め方について、まず一通り説明していきたいと思っています。
ここまで、P=NP?問題はNP完全な問題であるSATが多項式時間で解けるか？という問題に帰着できる事を説明してきました。
あ、そこ、もう眠くなってませんか？だめですよ。もう面白い事言わないつもりなんでがんばって下さいね。
で、何言ってたんでしたっけ？というギャクはもう使ったっけ？あ、そうですね、先進めなきゃ。
いやね、私だって、逃避したくな、あ、ダメ、痛い、やめて.........
おっほん。
で、では、先に進めましょう。
これからの事に必要な分だけ、これまでの復習を簡単にすると、一般的にある論理式が答えを持つかどうか、という問題がNP完全であるということは、充足問題（SAT)として与えられ、Cookの定理によってSATがNP完全と言う事から、NP完全であるという事が証明されました。
それで、先にも述べたように一般的な論理式が多項式時間で解ける事が分かれば、それはすなわちクラスPということなので、P=NPという事が証明されます。逆に、多項式時間で解けないことが証明されれば、P≠NPという事が分かるわけです。これが、P=NP?問題のごく大まかな証明の流れになります。
ところで、一般的な論理式は、この分野では『サーキット』と呼ばれる、グラフ（この場合特に木構造）として表せる事は何となく分かりますよね？たとえば、下に例を挙げておきました。
こうして、すなわち、ある複雑な論理式を表わしたサーキットが、多項式時間で解ける近似解を持ち、その近似解から正解までたどり着くまでの時間も多項式時間であるならば、そのサーキットは多項式時間で解けるという事になります、よね？
このことが一般的に言えれば、P=NPという事が証明されたと言う事になるわけです。
というわけで、これからの説明の流れとしては、大きく次のようになると現在のところ考えています。
１．一般的なサーキットがNP完全である事を証明する
１－１. サーキットがNP完全である事を証明するためにSATを変形した３SATがNP完全である事を証明する
１－２. 一般的なサーキットの問題のうちVC（頂点カバー）問題、独立セット問題、
クリーク(clique)の問題が本質的に同じ問題である事を示す
１－３. 上記の三つの問題のうちVC問題がNP完全ということ３SATを使って示す
２．一般的なサーキットの計算量を求める
２－１. 論理式がサーキットで表せる事を示す
２－２．サーキットの計算量の様々なクラスを考察する
２－３．ユニフォームという概念
３．モノトーン（否定のリテラルがない論理式）のサーキットが多項式時間以内で解けない問題である事を証明する
３．を不思議に思われると思いますが、否定のリテラルがあると複雑な論理式の計算量が減る場合があるのです。なので、否定のリテラルないサーキットの計算量をまず計算するわけですが、これはすでに多項式時間以内で解けない問題である事が分かっています。このブログのゴールはそこです。
でも、ちょっと私が考えた否定のリテラルがどれくらい計算量を減らすかっていう事も説明するかもしれません。さて、どうなるんでしょうか。私自身も少々不安ですが、これからまた、がんばっていきますので宜しくお願いいたします。
