目次のようなもの

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

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

そこで、ブログトップに、このブログ「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日
長い時間掛かりましたが、なんとか完結することができました。これも温かく見守って頂いた皆様のおかげと思います。感謝に堪えません。本当にありがとうございました。

ノンモノトーンで計算が減る場合 その3

おはようございます。

今回は、前回に引き続き、

(a∨b∨c）∧(￢b∨￢c∨d)=T

という事を利用して、SAT表現で部分的に{{a,b,c},{notb,notc,d}}のような節がある場合、探すためのコストは81/4の定数倍となりますが、節二つ分を計算する必要が無くなる場合をもう少し詳しく考察します。

　　例）{{{a,b,c},{not b,not c,d},{e}}=｛{a,c,not c,d},{e}}={{T},{e}}={{e}}


まず、モノトーンの場合普通のサーキットであれば、前回の節までで考察したように、オーダーは

size(C)=2^(p-1)/m^2≧n^(8・k^(1/2))

より決まります（参照：モノトーンそしてmP≠mNP その11（http://peunp.blogspot.jp/2014/11/blog-post.html））

ところが、乱数を発生させずに、

(a∨b∨c）∧(￢b∨￢c∨d)=T

となるものを探すということを考えますと、節集合Cの元の数|C|をn、節の中のブール変数の平均の数をmとおいて、総当たりで探すことになりますから、オーダーは単純に考えるとO(m^2*n^2)となり、オーダーは多項式で表わすことができるようになります。発生確率も4/81と比較的高いことから、乱数で元を発生させたようなホワイトノイズがSATの節にある場合は著しく計算量を減らすことができるということになります。つまりNTMで適当にデータを作成して処理するというような場合ほとんどの場合ホワイトノイズであると考えられますので、多項式時間で解を求められるのではないのかと考えます

さらに、乱数を発生させて探す場合にはオーダーは確率4/81の逆数の84/4に乱数発生のコストを加えたものを定数Aとすると、コストは最悪でもA（m^2）より大きくならず、即ちオーダーは（m^2）まで押さえられると思われます。

プログラムを用いた乱数を場合どれくらいの試行を行えば良いかを確認したのですが、例えば、n=1000,r=100の場合、81×100の試行で約56％、81×500で約98％まで節の数は減少し、81×800で99.7％、81×100で残りの節はほぼ0か1にまで減少しました。

検証用のプログラムはGitHubにアップロードしています。（実際はいくつかのバージョンがあるのですが、今回の検証用のプログラムだけアップロードします）。プログラムの解説は、今回のブログの目的から外れますので行いませんが、よろしければ、どうぞご確認下さい。

アドレスはこちら

https://github.com/Futarisizuka/SAT_term_compress_simulation

ノンモノトーンで計算が減る場合 その2

おはようございます。今回からは少しまじめにお話しします。自分の考えをお話しするので緊張するのです。


今回ここで発表することは、すでに、「http://etsurohonda-blog.blogspot.jp/2011/11/pnp.html」やhttp://etsurohonda-blog.blogspot.jp/2011/11/pnp.html」などで発表しているのですが、改めてきちんと考察をしてまとめておこうということもありまして、身の程知らずにもここに書かせて頂きます。

基本的なアイディアをまず述べます。

(a∨b)∧(￢b∨c)

の括弧を外すことを考えると普通ならば

(a∨b)∧(￢b∨c)=a∧￢b∨a∧c∨b∧￢b∨b∧c

となり、計算量は増大するように思われますが、一般に公式を用いると

(a∨b)∧(￢b∨c)=a∨c　　　　　　　　　　（１）

となり計算量は減ります。

さらに

(a∨b∨c)∧(￢b∨￢c∨d)

のような論理式は（１）を応用すると

(a∨b∨c）∧(￢b∨￢c∨d)=(b∨(a∨c))∧(￢b∨(￢c∨d))
　　　　　　　　　　　　=(a∨c)∨(￢c∨d)
                        =a∨c∨￢c∨d
=a∨T∨d
                        =T
となります。


これをSATの節に応用して考察していきます。そのとき、以下の二つの考え方を用います

一つ目は、SAT表現における節において、各変数はブール変数であるため取りうる値は二値ですが、実際には項があるかないか、あれば真か偽かという事で、場合としては三通りの場合分けで考察します

二つ目は、たくさんの節集合がある場合に、適当な二つの節を持ってきる場合を考えます。はじめに論理式で説明したように、その節に同じ項があり、逆の値を持つときには計算せずその値を消去できます。例えば{{a,b},{not(b),c}}という節は,{{a,c}}と同値になります。そのため節が一つとなる、あるいはあとで説明しますが、節自身が消滅する場合もあり、著しく計算量が減るという考え方です。以下はもう少し詳しく場合分けして考察していきます。

※以下はSAT表現で、節集合Ｃの元の数はr、節の各リテラルは元々はm個のブール変数であるとして以下考えていきます

（a）適当に取った二つの節に同じ項があり逆の値を持つ場合
上でも説明していますが、部分的に{{a,b},{not(b),c}}=｛{a,c}｝とできる場合のことです。この場合、ある節にbが含まれ別の節にnot(b)が含まれる確率を考えます。そうすると、確率は1/9となる事が分かります。また、その逆もあり得ますので、確率は二倍となり、その場合に減る計算量は上の式の左辺の計算量は単純に3これが右辺では１ですのでとなります。
（注：以前のブログでは逆もありうるということを考慮に入れていませんでしたので修正しています）

ここからが以前と違う結論になるのですが、探すコストが9/2であるのに対し減らせるコストが2、前後に他の項があれば4の場合もあります。すなわち減らせる計算量は最大でも4。場合減らすコストより一致する項を探すコストの方が大きくなるため、この場合はやるだけ無駄ということになります。

（a'）適当に取った二つの節に二つ同じ項があり一つは同じ値、もう一つは逆の値を持つ場合

この場合の例としては{{a,b},{a,not(b)}}=｛{a}｝となり、かなり小さくなっていますが、変数が増えると{a}にあたる部分が複数の変数からなりすべて一致するとのは比較的まれな場合と考えられます。また、見かけ上は小さくなっていますが、{a}に相当する部分が複数の変数よりなる場合の計算のコストは(a)の場合とほぼ同様と考えられますので考察から除外しても問題ないと考えます。

（b）適当に取った二つの節に同じ項二つありそれぞれがあり逆の値を持つ場合
部分的に{{a,b,c},{notb,notc,d}}のような節がある場合です。この場合、探すためのコストは81/4の定数倍となりますがこの場合二つの節が一つになったときに真となります

　　例）{{{a,b,c},{not b,not c,d},{e}}=｛{a,c,not c,d},{e}}={{T},{e}}={{e}}

そのため、この場合、節二つ分を計算する必要が無くなり、減らす事のできるコストは論理和と論理積の個数即ち、（(節Aの長さ-1)+（節Bの長さ-1)+1）となります。従って、節の長さ（節の中の変数の個数）が11に等数発生などのコストを上乗せし、上回る場合はこの手法は有効となります。


今回は以上ですが、次回、この方法であるならば、乱数を発生させて適当な節と変数に注目すれば確率4/81ではありますが、大きく計算量を減らすことができる、と言う点に着目してもう少し考察を深めてみたいと思います。

ノンモノトーンで計算が減る場合 その1

おはようございます。日本料理がユネスコの無形文化遺産に晴れて登録され認定書が渡されたというニュースがありましたが、日本食の素材の良さを生かすも殺すも包丁さばき。元々、良く切れる刃物があったことも日本食には重要だったのかもしれないなともおもいます。立派な料理人さんや包丁とは違いなかなか切れない頭とほどほどとも言いがたい腕の私ですが、この大変といえば大変で私には立派すぎる素材をなんとか綺麗に切り分けてみたいものです。

さて今回は、ノンモノトーン・サーキットの計算量が減る場合に関してブール代数的な表現とその定理の証明をします。

まず、前回(「モノトーンそしてmP≠mNP その12」）、テキストから引用した竹内先生のアイディアを再掲したいと思います。

「まずアイディアを説明する。a1,…,anを相異なった元とする。このとき集合Aが{a1,…,an-1}であるか{a1,…,an-2,an}であるか,……または{a2,…,an}であるかであるか?という命題を考える。いま{a1,…,ǎi,…,an}をa1,…,anからaiを抜いた元の集合を表わすものとすれば、上のAは{a1,…,ǎi,…,an}のi=1,…,nのどれかということになる。ここで表わされるaの数はn(n-1)である(注：n個の元をとり、それをチェックするのにはn(n-1))。これをAは{a1,a2,…,an}からa1を取ったものかa2を取ったものか、……またはanをとったものかといえば、aの表わされる数は2n（注：取り出す組み合わせがnチェックにn）とすくなくなる」

では、ブール代数的に表現した式(formula)ではどうなるのかというと

(※注：フォントセットの都合上テキストでxとあるものをzを用いています。以下同様)

　　※ここでyiは任意のチェックのために必要なブール代数


とする。ここでi,jは1,2,…,nを走るとテキストにはあります。この場合、式のサイズ(以下formula size)という概念で考えると、

　(1)はn(n-1)/2+n^2

　(2)はn(n-1)/2+3n

という形になりオーダーこそ同じものの確かにサイズが減っています。

このことを即ち

【定理】(1)と(2)は同等である

として証明していきます

【証明】

上式（１）、（２）の

　　

の部分とは独立に

　　




　すなわち

　　


を仮定し、この仮定のもとで、次の二式が同等であるということを言えば良いわけです

　
　　　

まず、(＊)より(z1∨…∨ži∨…∨zn)から(z1∨…∨zn)∧￢ziが出ることをいいます。

(＊)からまず、　

　　　z1∨…∨ži∨…∨zn→￢zi

　を出すことができます。これから　
　　
　　　z1∨…∨ži∨…∨zn→(z1∨…∨zn)∧￢zi

　を出すことができます。

また、

　(z1∨…∨zn)∧￢zi→z1∨…∨ži∨…∨zn)∧￢zi

　　　　　　　　　　　　　　→　z1∨…∨ži∨…∨zn

というのは自明です。

これから、つぎの3つの式が同等であると言うことが分かります


　

　

以上で証明が終わりました。

次回は、この定理から、私が考えたことを説明したいと思います。

モノトーンそしてmP≠mNP その12

おはようございます。クールジャパンと言いながらもいろんな問題を抱えている日本。その一つが飽食の問題でしょうか。世界中でヒットしている進撃の巨人というマンガも実は飽食の日本に対する子ども達の不安やいらだちを顕したものではないかとも思います。その一方でポケモンなどかわいらしいものもたくさんありますよね。最近妖怪ウオッチが爆発的なヒットだそうです。たまごっちみたいに世界中で社会問題になったものもありますから、これからどうなりますやら。しかし、どうして私の書いたものはどれもこれもヒットしないんでしょうかねえ。

やれやれと。では、前回で予定していた定理の証明まで終えたのですが、もう少しの間、補足説明などをさせて下さい。

まず、テキストから見た今回説明した定理までの位置づけですが、漸く本格的にこのテキストに書いてある内容について、基本的な部分の説明が終わったといったところでしょうか。ここまでご理解頂ければ、あとは、応用して詳しい議論がなされていくことになりますので、入門のブログとしては一通りの役目を終えたかと思います。

さて、mP≠mNPを証明した定理ですが、基本的にモノトーンであるという前提でした。ところが、すべてのモノトーンな命題を表わすサーキットが多項式倍のモノトーン・サーキットで表せるならばP≠NPの証明にもなるわけですが、そうとは限らないという証明が以下の論文でRazborovによってなされているとテキストにはあります。

「A lower bound on the monotone network complexity of the logical permanet, Math Zametyki, 37(6), 1985, 887-900(ロシア語）,英訳 Math. Notes, 37(6), 1985,485-493」

これは、今回説明した定理の証明と似た方法によって, mPに属する二部グラフの問題はモノトーン・サーキットでは多項式サイズで表せないことを証明した、とあります。また、E.Tardosは

「The gap between monotone and  non-montone circuit complexity is exponential, Combinatorica, 8(1),1988,141-142」

でモノトーンとノンモノトーンとの差がべき乗であることを証明しているとあります。要するにクリークのようなNPｰ完全な問題がモノトーンな命題であれば、多項式サイズに収まらないことはここまで見たように分っていることだとして、どうして、ノンモノトーンとの差が出るかということが問題となるわけです。

ノンモノトーンな命題においてサイズが減る様子に関して竹内先生がテキストに述べられているアイディアを説明して今回は終わります。実際の証明は次回以降になりますのでご了承下さい。

「まずアイディアを説明する。a1,…,anを相異なった元とする。このとき集合Aが{a1,…,an-1}であるか{a1,…,an-2,an}であるか,……または{a2,…,an}であるかであるか?という命題を考える。いま{a1,…,ǎi,…,an}をa1,…,anからaiを抜いた元の集合を表わすものとすれば、上のAは{a1,…,ǎi,…,an}のi=1,…,nのどれかということになる。ここで表わされるaの数はn(n-1)である(注：n個の元をとり、それをチェックするのにはn(n-1))。これをAは{a1,a2,…,an}からa1を取ったものかa2を取ったものか、……またはanをとったものかといえば、aの表わされる数は2n（注：取り出す組み合わせがnチェックにn）とすくなくなる」

とあります。先にも少し書きましたが、次回以降はこのことについて、ブール代数の場合に翻訳し、同等であるという定理の証明をします。

モノトーンそしてmP≠mNP その11

おはようございます。と言ってもまたお昼を廻ってしまいました。申し訳ありません。昨日は冬至だったようです。最近道理でミカンがおいしい。ええ、冬に到っても食欲は落ちていません。それにしても、昨日の十五夜お月様も綺麗でしたね。十三夜のお月様はミラクルムーンと言ったらしいですが、十五夜お月様も丸々としていて実においしそう、いや美しかったです。

今回は定理の証明の続きですね。難しい言葉を使えば承前。

(b)近似サーキットC'が少なくても(1/2)(k-1)^nの否定的テストグラフの値に1を与えるとき

このときは補題c(「その9」()参照 )より

　　　　　size(C)・m^2・((n-l-1)C(k-l-1)/(k-1))^p・(k-1)^n≧(1/2)(k-1)^n

が成立。このとき、l≦(1/2)(k-1)から次の不等式が得られます。

　　　　　((n-l-1)C(k-l-1)//(k-1)=l(l-1)/(2(k-1))≦(K^(1/2)(K^(1/2)-1))/(2(k-1))<1/2

したがって、このほか1<k≦n^(1/4)、m=(p-1)^l・l!などを用いて次の不等式がすべて成立します。

　　　　　size(C)・m^2・2^(-p)≧1/2
          size(C)=2^(p-1)/m^2

　　　　　2^(p-1)≧2^(9・k^(1/2)・logn)=n^(9・k^(1/2))

　　　　　(p-1)^(2l)≦(11・k^1/2・logn)^(2・k^(1/2))≦(n^(5/32))^(2・k^(1/2))=n^(5/16・k^(1/2))

　　　　　(l!)^2≦(└k^(1/2)┘)^(2・k^(1/2))=n^((1/4)・k^(1/2))
　　　　

以上より

          size(C)=2^(p-1)/m^2≧n^(8・k^(1/2))

が求められ、定理は証明されました。

次回は補足説明などを予定しています

モノトーンそしてmP≠mNP その10

おはようございます。ではなく、こんにちはになってしまいましたか。何でも、日本の若い方の70％は生まれ変わっても日本に生まれたいとか。最近これが一番日本らしいなと思いました。窮屈な日本ですが、それなりになれると住みやすく離れづらい、そういうことなのでしょうか。それとも、いったん外国に出たら最後、なかなか就職なども難しくなるらしいというのが影響しているのか。まさか、生まれ変わってまで、ずっと日本人じゃ無きゃいじめられる世界というのも怖いですね。いろんな意味で開かれた日本というのも大事だと思います。


いよいよ今回は、問題となっているA.RazborovとA.E. Andreevが証明した定理（「その3」参照）の証明に入りたいと思います。

【定理】（再掲）

1<k≦n^(1/4)とするときClique k,nを表わすモノトーンサーキットのサイズは少なくても

　n^Ω(k^(1/2))

【証明】

ここでは、まず、lとpを以下のように定めておくことにします。

　　l=└k^(1/2)┘,　　p=┌10k^(1/2)logn┐

　　※ここで└a┘は≦aを満たす最大の整数、また┌a┐は≧aを満たす最少の整数

またlogの底は断らない限り2で、mはいままで通りm=(p-1)^l・l!(「その６」参照)です。


さて、つぎに、補題a(「その7」参照)を再掲すると

【補題a】
すべての近似サーキットは0だけからなるサーキットであるか、または否定的テストグラフの少なくとも

　　(1-lC2/(k-1))・(k-1)^n

の部分に対して1をアウトプットして計算する


とありましたが、いまこの　(1-lC2/(k-1))の部分を考えますと、k<1でl=└k^(1/2)┘より、2lC2<k-1が求められ（例：k-1=1が最少。このときl=1で1C2=0。lはごくゆっくりとしか増加しない事が分れば帰納法的にすぐ分ります）、サーキットCの近似サーキットC'は0であるか、少なくても1/2・(k-1)^n個の否定テストグラフに1を与えることが分ります。

この場合を二つに分けて考えていきます。

(a)近似サーキットC'=0を取るとき

　このとき肯定テストグラフが誤って0を出力する即ち、C'＜Cとなるようなグラフの数は補題b（「その8」参照）より求まっていますので

　　　size(C)・m^2・(n-l-1)C(k-l-1)≧nCk

これより、

　　　size(C)≧(n!(k-l-1)!)/(k!(n-l-1)!m^2)

が、求まります。

いま1<k≦n^(1/4)としていますから、上の式の(k-l-1)!/k!の部分を考えると、

　　　　(k-l-1)!)/k!≧k^(-(l+1))≧n^(-(1/4)k^(1/2))

同様にn!/(n-l-1)!の部分を考えると

　　　　n!/(n-l-1)!≧(n-l)^(l+1)≧(n-n^(1/8))^(k^(1/2))≧n^((15/16)k^(1/2))

また、
　　　　m=(p-1)^l・l!と　l=└k^(1/2)┘より

　　　　m^2＜p^(2l)・(k^(1/2))^(2l)=(p(k^(1/2)))^(2l)＜n^((9/16)k^(1/2))

　　　　1/m＞n^(-(9/16)k^(1/2))

ですから

　　　size(C)≧(n!(k-l-1)!)/(k!(n-l-1)!m^2)≧n^((1/8)k^(1/2))

となり、定理を満たしています。

次回、(b)否定的テストグラフの少なくとも

　　(1-lC2/(k-1))・(k-1)^n

の部分に対して1をアウトプットして計算する

を説明します。もちろん頭の良い方でしたら、もう自分で導き出せますよね。