目次のようなもの

情けないことに、私のブログにおいては、諸般の事情（というより、立派な方々から、いろいろといじめられて、都合よく使われたりすること）により、進捗は遅々という表現すらかわいく見えまして、更新の間隔が数年の間を挟むということも稀ではありません

せっかく続けて読んでいただいていた読者の方々もまた、どういう内容だったかをきっと忘れてしまわれていることでしょうし、初めて読むという方におかれては、なおさらわかりにくいものでしょう

そこで、ブログトップに、このブログ「P=NP?の覚え書き」の目次に相当するような各記事のまとめのページを作成しようと考えた次第です
　
　
１．P=NP?問題についての簡単な説明
　

・「はじめに」では、われわれが言葉を理解するという例を挙げています。ラジオのニュースのように、初めから言葉と分かっているものを聞いているときをクラスＰという分類にし、寝ているときに、たとえば「火事だ」という言葉を、様々な雑音の中から拾い出すということをクラスNPとして分類し、このクラスＰに属する問題とクラスNPは同程度の計算量で解ける問題かどうか、ということを明らかにするという学問だと言うことです

　
・「改めてP=NP？って」では、P=NP？問題において専門的に知っておくべきごく簡単な事項の説明・解説をした後に、クラスPとクラスNPという問題において、クラスＰの問題がクラスNPの問題に包含されるのは自明ですが、クラスNPがクラスＰと等しいかどうかということを考えるときに、クラスNPの問題は、結局「NP完全」という定義をされている問題に置き換えられるということ、そして、この「NP完全」の問題が、クラスPの問題と同等であるかということが、問題の核心であるということを説明しています
　

　さて、専門書では、良くクラスNPの問題について、素数を例にして説明されています。5や13のような小さな数であれば、素数であるということを判別することは比較的時間もかからず証明できます。ところが、基本的に、わり算というのは、とんでもなく手間がかかるものです（私のブログ「ホンダエツロウの悪戦苦闘」の「かけ算とわり算について（２）」をご参照いただくとすこし参考になるかもしれません）から、桁数の大きな数が素数であるかどうかということを判定するのは、答えを知らなければ、大変手間暇のかかる問題となります。例を挙げれば、3桁の数377（=13×29）が素数であるかどうかという問題でも、13もしくは29で割れるということを知ってさえいれば簡単ですが、そうでなければ、何度もわり算を繰り返して、証明する必要があります
　
　
２．参考文献
　

・「参考文献」は、参考文献を挙げているページです。このブログでは主に、テキストとして掲げている竹内外史先生の「PとNP―計算量の根本問題」（日本評論社（絶版））を引用することが多いです
　
　
３．集合論的整数について簡単に
　P=NP?問題を考えるにはあまり関係はないのですが、個人的に、どうしても、カントールの集合論を用いた整数についての考え方について触れておきたい、という個人的な考え方から書いた記事となります。ご参考までに
　

・「集合論における整数」 カントールの集合論的整数の考え方や、集合の濃度という概念について触れています
　
　
４．クラスという概念について

・「クラスについて」では、数学におけるクラスという概念が、「集合の集合」である、ということについて説明しているのですが、部分集合について上記３．における、集合論的整数論を用いて説明しているために、やや難解となっています。とりあえず、ここでは、集合の集合がクラスである、ということだけを覚えていただければよいかと思います
　
　
５．決定問題、チューリングマシン、クラスＰについて　
　ここからは、いよいよP=NP?問題について、もう少し詳しく見ていくことになります。そこで、まず、クラスＰに属する問題がどのような問題か、ということを説明するために、決定問題とチューリングマシンについて説明し、そのあとクラスＰの定義を述べています。
　

・「クラスPとチューリングマシン　その１」では、チューリングマシンが決定問題を扱うモデルと簡単に説明したあと、決定問題について主に触れています。決定問題をここではごく簡単に説明すると、計算機が文字列を受け取ったときに、ある処理をして受理をするか拒否をするかを決定するような問題ということです
　

・「クラスPとチューリングマシン　その２」では、まず、チューリングマシンが具体的にどのような処理をするものなのか、ということを具体的に説明しています。簡単にいうと、一本の無限に長いテープ上に記録されているデータを手続きに従って順番に処理することによって、受理か不受理（拒否）を最終的に決定する機械がチューリングマシン（これからは、頭文字をとってＴＭと略します）です。
　
　そのあと、クラスＰを定義して、ＴＭが多項式時間つまりデータの長さｎに対して、ｎの多項式で表せる式に比例した時間で処理できるような問題である、ということを説明しています

このあと、
　

・「チューリングマシンの数理モデル」では、 数学的にＴＭを説明するために数理モデルというものの定義を示しています
　
　
６．クラスNPと非決定性チューリングマシン

・「クラスNPと非決定性チューリングマシン」では、非決定性チューリングマシン（以下、と略します）を説明した後、クラスNPに属する問題について説明しています。ＴＭとクラスＰの関係は、ＴＭでは、無限に長いテープにはあらかじめ問題が書き込まれていて、それを手続きに従って順番に処理するときにデータの長さの多項式に比例する時間内に処理できる問題がクラスＰということでした。ＮＴＭとは、まず、試行という段階がまずあって、そこで、無限に長いテープに適当な手順やデータが書き込まれます。その適当に書き込まれたデータを手順通り行って、多項式時間（テープに書き込まれた手順とデータの長さの和ｎの多項式に比例した時間）内に受理か不受理（拒否）かを決定できる問題が、クラスNPと定義できるということを説明しています
　

・「NTMの数理モデルとクラスPとNPの違い」では、ＮＴＭの数理モデルをＴＭの数理モデルと比較しながら記述、説明しています
　
　
７．オラクルチューリングマシン（ＯＴＭ）とＯＴＭプログラム
　

・「オラクルチューリングマシンとOTMプログラム」では、オラクルチューリングマシン（以下、ＯＴＭと略す）を説明して、そのＯＴＭで多項式時間以内で解ける問題のことを多項式ＯＴＭプログラムと呼ぶということを説明しています。ＯＴＭは直接P=NP?に関わるものではないといえ、密接な関係があるため、記事を起こしています。ＯＴＭについての説明は、短い記事ですので、リンク先を読んでいただければ幸いです
　

・「OTMの数理モデルと計算量およびそのクラス」では、ＯＴＭの数理モデルをＴＭと比較しながら説明しています。
　

ここで、１．で説明した、「改めてP=NP？って」という記事を挟み、次からは、クラスNPの問題において中核となる概念NP完全について説明していく流れになっています
　
　
８．NP完全
　NP完全について数学的に説明しています
　

・「NP完全とその数学的定義　その１」では、NP完全を数学的に定義するために必要な準備をしています。まず「∝」を定義して、L1∝L2を、言語L1を多項式時間内で言語L2に変換できるということを表す記号であるということについて説明しています。そのあと、NP完全を定義するための第一の補題「L1∝L2で、L2∈PならばL1∈Pである。従ってL1∝L2でL1∉PならばL2∉P」が成立するということを説明しています
　

・「NP完全とその数学的定義　その２」では、この第二の補題「L1∝L2，　L2∝L3，　ならば　L1∝L3」について触れた後、NP完全の定義にはいります。ここでは、簡単に「NP完全とは、クラスNPに属するすべての言語L’が多項式時間でクラスNPに属するある言語Lに変換できる場合、その言語LのことをNP完全な言語という」という部分を引用しておきましょう
　最後に、「クラスNPに属するすべての言語L’が多項式時間でクラスNPに属するある言語Lに変換できる」ということを、第二の補題を使って証明した第三の補題を説明してこの記事は終わります
　
　
９．ＮＰ完全である「充足問題（SAT）」について
　８．では、NP完全を定義し、Ｐ=NP?問題を考察するとき、クラスNPに属する問題についてはNP完全な問題だけを考察すれば良いということを説明しました
　これからしばらくは、充足問題（以下SATと略す）というクラスNPに属する問題が、NP完全であるということを証明していきます。
　まず、ここでは、充足問題（SAT）がどのような問題であるか、ということを説明します。次の１０．におおいて、このSATがNP完全であるということを証明したCookの定理を解説していく、という手順になっています
　

・「充足問題について　その前に」では、SATを理解する上でどうしても必要なブール代数の基本知識について説明しています

　
・「充足問題　その１」では、ブール変数やリテラル、SATにおける節とはなにか、など、SATを扱う上で必要な知識の説明です

　
・「充足問題　その２」では、さらにSATを理解するために必要な「真理関数」と「充足」という概念を数学的に定義しています

　
・「充足問題　その３」では、いよいよSATについて定義しています。簡単にいえば、あるブール関数の有限集合が論理和（以下OR）と論理積（以下AND）で結合されている（これをSATでは節という）とき、この式を真（Ｔ）とするようなブール変数の値の組があるかどうかを求める問題、ということになるでしょう
　
　
１０．Cookの定理ーSATがNP完全であることを証明する定理
　上の９．で記述したSATがNP完全であることを証明したのがCookの定理です

　
・「Cookの定理　その1」では、まず、ピタゴラスの定理（三平方の定理）を例に挙げて、定理に名前が付くことが、どれくらい重要かということを説明したあと、これから証明する、SATがNP完全であることの証明のあらすじを、以下のように述べています
　
　　手順１．　SATがクラスNPであると言うことを証明し、
　　手順２．　NTMで完全にランダムな入力をTMで処理するという部分が
　　　　　　　多項式時間内でSATに変換できることを証明する

　
このあと、「手順１．」について説明して、ここまでを終えています

　
・「Cookの定理　その2」以下その8まで、上記「手順２．」についてを説明しています。その2では、まず、大まかな証明の考え方と、処理回数、処理時間についての説明をしています
　　
・「Cookの定理　その3」では、まず、TM（ここでは特にNTM）において、書き込まれたデータが処理時間と同等であるということを簡単に説明します。このような準備が終わったあと、以下、その8まで「手順２．」の実際にTMとしての処理が多項式時間内にSATに変換できることを説明していくことになります。その3では、まず、使用するブール変数についての定義を行っています。特にデータに関しては「すべてのデータに対して１対１で対応するブール変数があり、添え字がそのデータを示す」ということを引用して強調しておきたいと思います

　
・「Cookの定理　その4」では、まずNTMの状態を表すブール変数の定義を行っています。この他、このような定義下では、NTMが処理を行っている場合、状態を表すブール変数は、すべて真（これを真理値が与えられている、あるいは真理値をとる、という表現をします）となるということなどを説明しています。ここまでで、ようやく使用するブール関数についての定義が終り、実際にNTMをSATへ変換する為の手順について少し触れる、ということをしています

　
・「Cookの定理　その5」では、NTMの実際の処理における内部状態の遷移を例にとって、SATとして表現すること（以下SATへの変換と述べます）について説明しています。また、変換はG1～G6の6つで表せるということに少しだけ触れています

　
・「Cookの定理　その6」では、その5でも少し触れたNTMのSATへの変換G1～G6のうち、G1～G5について説明しています

　
・「Cookの定理　その7」と
・「Cookの定理　その8」では、
　

　　G6　：i番目の段階(ただし、0≦i＜p(n))において、
　　　　　マシンMLのi+1番目の状態は、
　　　　　i番目の状態からチューリングマシンの状態遷移関数δ
　　　　　によって決定される　

　
について、SATへの変換を説明しています。これがかなりややこしいので、二回に分けています。その7では、NTMのヘッドにかかっていないテープのi+1番目の状態はi番目の状態と同じ、ということを説明し、その8では、ヘッドのある部分のテープのi+1番目の状態についてのSATへの変換ということについて説明しています。最後に、「最終的には節C＝G1∪G2∪G3∪G4∪G5∪G6というSATがプログラムMLが入力xを受容する計算になっている」ということを述べ、これらが明らかに多項式時間で処理できるということについて触れて、以上のCookの定理についての説明を終わっています
　
　
１１．ここからの進め方
　ここまで、P=NP？問題を扱う上で、まず、この問題の概要を理解していただいた上で、クラスPとTM（チューリングマシン）が密接な関係にあること、同様にクラスNPがNTM（非決定チューリングマシン）と密接な関係にあるということを説明しました。その上で、クラスNPの問題を詳しく扱おうとするときに、NP完全な問題を扱えばよいということを述べ、Cookの定理によってSAT（充足問題）がNP完全であるというところまで説明しました

　
・「このブログを再開するに当たってのこれからの進め方」では、論理式が、サーキットと呼ばれるグラフ（節点・頂点と呼ばれるものを枝・辺などで結んだもの）として表現できることを述べ、このあと、グラフ理論を用いて解析していく過程を次のように端的に説明しています

「
　１．一般的なサーキットがNP完全である事を証明する
　　１－１.　サーキットがNP完全である事を証明するためにSATを変形した３SATがNP完全である事を証明する
　　１－２.　一般的なサーキットの問題のうちVC（頂点カバー）問題、独立セット問題、
　　　　　　クリーク(clique)の問題が本質的に同じ問題である事を示す
　　１－３.　上記の三つの問題のうちVC問題がNP完全ということ３SATを使って示す
　２．一般的なサーキットの計算量を求める
　　２－１.　論理式がサーキットで表せる事を示す
　　２－２．サーキットの計算量の様々なクラスを考察する
　　２－３．ユニフォームという概念
　３．モノトーン（否定のリテラルがない論理式）のサーキットが多項式時間以内で解けない問題である事を証明する
」
　
　
１２．3SAT
　上の１１．でも説明したように、論理式からグラフ理論への展開のステップとして、まず、3SAT、すなわち、SATのうちすべての節が三つのブール変数で構成されているものについて

　
　　SAT∝3SAT　
　　（NP完全であるSATが多項式時間以内に3SATに変換できるということ）

　
を示すことによって、3SATがNP完全であることを示していきます

　
・「３SAT　その１」では、まず、3SATがNP完全であることの証明の方針として、上記のように　SAT∝3SAT（NP完全であるSATが多項式時間以内に3SATに変換可能）であることを証明していくということに触れたあと、各節の要素（ブール変数）の数が3のときと1のときのSATが3SATに多項式時間以内で変換できるということを示しています

　
・「３SAT　その２」では、SATから3SATへの変換を、変換元SATの節の数kによって分けて示しています。ただし、k＞3のときに関しては、別途、次の「３SAT　その３」で詳しく説明することにしています

　
・「３SAT　その３」では、上記「３SAT　その２」でも触れているように、SATの節の数が3より大きい場合の　SAT∝3SAT　について詳しく説明しています

　

　

１３．簡単なグラフ理論及びサーキットというグラフについて

・「サーキットというグラフ　その１」では、グラフ理論についてごく簡単に説明し、一般的な論理式をグラフとして表現するサーキットというグラフについて定義しています

　
・「グラフ理論についての簡単なお話」では、グラフ理論の成り立ちや基本的な概念について簡単に説明しています
　

・「サーキットというグラフ　その２」では、上の「サーキットというグラフ　その1」で触れた一般的な論理式をグラフとして表現するサーキットというグラフについて関連するさまざなことがらについて定義、説明しています
　
　

１４．頂点カバー・独立セット・クリーク
　
　・「頂点カバー、独立セット、クリーク　その１」では、グラフ理論におけるNP困難とされる頂点カバー、独立セット、クリークについての必要な知識やその定義、そのほか、これらがサーキットというグラフとの関連について簡単な説明をしています

　

　・「頂点カバー、独立セット、クリーク　その２」では、頂点カバー、独立セット、クリークについて、本質的に同じ問題であるということを説明しています

　頂点カバー、独立セット、クリークという問題が本質的に同じ問題であるということが示された後、頂点カバー問題をnp完全であるということを示すことで、これらすべての問題がNP完全であるということを示すことにします

　・「頂点カバー問題がNP完全であるということ　その１」では、頂点カバー問題がNP完全であるということをすでに証明された３SATに置き換えられる事でNP完全であるということを証明するという大まかな概要を述べています
　
　・「頂点カバー問題がNP完全であるということ　その２」では、３SATの問題を頂点カバー問題に翻訳するための方法をしてしています（注；2014/01/26　これについての証明はその３以降の予定です）
　
　・「頂点カバー問題がNP完全であるということ　その３」と
　・「頂点カバー問題がNP完全であるということ　その４」では
では、上記その２で、３SATの問題を頂点カバー問題に翻訳したものが、互いに同じ事であるかと言うことを証明することによって頂点カバー問題がNP完全であることを証明しています。
　

１５．論理式をグラフにした場合の計算量
　ここまで論理式をグラフに置き換えてP=NP？問題を扱う方法を考えてきました。ここからは、モノトーンと呼ばれる論理式についてグラフ理論を用いて計算する方法を説明していきます

　・「サーキットというグラフの計算量　その１」では、ここまでの流れをまとめ、パリティとモノトーンという概念について定義を行っています

　・「サーキットというグラフの計算量　その２」では、モノトーンのブール関数においてのmintermとmaxtermという言葉を定義したあと、min(f),Max(f)という集合の表記について説明します。また、モノトーンな論理式という事についても説明しています

　・「サーキットというグラフの計算量　その３」では、これまで説明してきたパリティ関数の計算量について、リーフの数と深さを計算する方法を説明しています。その３はまず、その準備になります

　・「サーキットというグラフの計算量　その４」では、その３につづき、証明の手続きに入ります。ここでは、まずKhrapchenkoの定理を証明しています

　・「サーキットというグラフの計算量　その５」では、その４で証明したKhrapchenkoの定理を利用し、L(Parity(x1,x2,…,x2n))≧(nの2乗)　という事を証明しています

　・「サーキットというグラフの計算量　その６」では、パリティ関数の計算量について、リーフの数がL(Parity(x1,x2,…,x2n))=(nの2乗)　という事を証明しています。ここでいったんサーキットの計算量についての説明は終わりになります。このあと、サーキットの計算量の様々なクラスを考察するんなどをし、その後、一般的なモノトーンサーキットの計算量について考察します。

　・「サーキットの計算量の様々なクラス　その1」では、ここから、ノードの入力の数（インデグリー）による計算量のクラスについて説明してきますが、その準備としていくつかの定義などを行っています。

　・「サーキットの計算量の様々なクラス　その２」では、NC^i、AC^iといった計算量のクラスの定義をしています。

　・「サーキットの計算量の様々なクラス　その３」では、その2で定義したユニフォームなクラスNC^i、AC^iといったクラスの計算量がクラスPであるということを述べています

「サーキットの計算量の様々なクラス　補足1」では、NC^i、AC^iといった計算量のクラスの定義を説明しましたが、数学基礎論的な補足説明を少し加えています。

　・「サーキットの計算量の様々なクラス　その4」　では、ノンユニフォームの場合を含めたNC^iやAC^iをここからしばらく検討していきます。今回は準備とこれまで説明してこなかった空間を計算量として見なす考え方についてもここではお話ししています。

　・「サーキットの計算量の様々なクラス　その5」では、ユニフォームの場合を含めたNC^iやAC^i、L、Pの包含関係や、NC^1の内容の検討が主な内容となります。

　・「サーキットの計算量の様々なクラス　その6」では、クラスPが多項式サイズのサーキットで表わされること、とれに伴う考察についてテキストの内容を紹介しています<

　・「サーキットの計算量の様々なクラス　その7」では、ここからノンユニフォームな多項式サイズのサーキットについて考察を始めるのですが、まずはいろいろな定義をしています。

　・「サーキットの計算量の様々なクラス　その8」では、P/Polyについての性質を定理として説明したものを取り上げています

　・「サーキットの計算量の様々なクラス　その9」では、最後に細く説明的な内容となりこの計算量のクラスの節を締めくくっています

１６．モノトーンとmP≠mNP
モノトーンという条件の下にクラスPとクラスNPの派生クラスであるmPとmNPにおいてmP≠mNPという事に関してじっくりと検討していきます

　・「 モノトーンそしてmP≠mNP その1」と
　・「 モノトーンそしてmP≠mNP その2」では、まず検討に必要な定義をしています

　・「 モノトーンそしてmP≠mNP その3」では、求める定理のを示し、その証明に関して必要な肯定的テストグラフ・否定的テストグラフや近似サーキットなど必要な事柄に関しての定義などを説明しています

　・「 モノトーンそしてmP≠mNP その4」では、サーキットをリーフから部分サーキットに分けて近似サーキットに置き換えるやり方の節をしています。まずひまわりと花摘みについて説明しています

　・「 モノトーンそしてmP≠mNP その5」では、サーキットを近似サーキットに置き換える際に行うひまわりの花つみについて、ひまわりが存在するかどうかの定理について説明をしています

　・「 モノトーンそしてmP≠mNP その6」では、上「その5」で証明した定理を用い近似サーキットの定義を完成させ、また、置換の際の方法なども説明しています

　・「 モノトーンそしてmP≠mNP その7」と、
　・「 モノトーンそしてmP≠mNP その8」と、
　・「 モノトーンそしてmP≠mNP その9」では、ここまでで説明した定義を使い、定理を証明するのに必要な三つの補題を説明しています。

　・「 モノトーンそしてmP≠mNP その10」と、
　・「 モノトーンそしてmP≠mNP その11」では、ここまで説明した三つの補題を用いて、二回に分けて定理の証明を行っています

　・「 モノトーンそしてmP≠mNP その12」では、補足説明に加え、ノンモノトーンな命題において計算量が減る場合の竹内先生のアイディアを紹介させていただいています。

１７．ノンモノトーン・否定のリラテルがあると計算量が減る場合について
ノンモノトーンの場合否定のリラテル（リーフ）がありますが、これがあった場合に計算量が減るということに着目した議論をしています。

　・「ノンモノトーンで計算が減る場合　その1」では、ノンモノトーンな命題において計算量が減る場合の竹内先生のアイディアと定理およびその証明を説明させていただいています。

　・「ノンモノトーンで計算が減る場合　その2」と
　・「ノンモノトーンで計算が減る場合　その3」では、ノンモノトーンな命題において計算量を減らすアイディアとそのシミュレーション結果、およびシミュレーションプログラムの公開アドレスなどを示しています

※2014年11月30日
長い時間掛かりましたが、なんとか完結することができました。これも温かく見守って頂いた皆様のおかげと思います。感謝に堪えません。本当にありがとうございました。