目次のようなもの

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

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

そこで、ブログトップに、このブログ「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をアウトプットして計算する

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

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

おはようございます。といいながら時は流れてもうこんばんは、あるいはお休みなさいの方がいい方もいらっしゃるかもしれません。では、おやすみ……トドのように、と言いたいところですが、もうちょっとがんばらないとですね。「秋の田の」といえば「我が衣手は露に濡れつつ」と来るのが百人一首。なんでも、上の句を分類して「あ」の音で始まる詩はいくつあり、と言うようにいろいろなテクニックがあるようですが、坊主めくりで良いと言えばそれでも良いですよね。人類の発展のためにはちょっとそれでは寂しいのかもしれませんが。


今回は補題cを説明していきます。苫を粗まないようにしないとですね。

【補題c】Cはモノトーンサーキットとします。このとき、C≧C'が成立しないような否定的テストグラフの

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

　　　　　※ただし、kはクリークとなるノードの数（「その3」参照）、lは濃度、m=(p-1)l(「その5」）参照)、nはノードの数
　　
を満たす

【証明】
補題bと同様にいま、

　　A=┌X1┐∨┌X2┐∨…∨┌Xr┐,　B=┌Y1┐∨┌Y2┐∨…∨┌Ys┐

として、

　　AЦB≦A∨B　　または　　AПB≦A∧B

が成立しないような否定的テストグラフの数が、高々

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

であるということを言えば良いということになります。（このような近似サーキットへの変換にかかる計算量はsize(C)で押さえられる、つまりたかだかクリーク表示の数であることは明らか）

(1)　AЦB≦A∨B　が成立しない場合
AЦBはA∨Bから高々2m回の花摘みで得られることから、1回の花つみで新たに受容される否定的テストグラフの数を考察することにすると、まず否定的テストグラフで与える1～k-1の番号の与え方は(k-1)^n通り。その中の一つから定義される否定的テストグラフをGとします。

集合の集合の元Z1,Z2,…Zpがあってひまわりを作っており、その中心をZとします。このとき

　”┌Z┐がGを受容する（命題Aとおく）か、または、どの┌Z1┐,┌Z2┐,…,┌Zp┐もGを受容しない(命題Bとおく)”

は次のことと同等です。（A∪B=￢(￢A∩￢B)の形式になっています）

”Zの二つの頂点に負荷された値は相異なる（命題Aの否定）が、同時にどのZiをとっても、その中に二つの頂点で負荷された値が同じものが存在する（命題Bの否定と共に上の命題全体の否定にもなっている）”

これらから次の確立についての不等式が出てきます。以下のZが正付加とは、Zの相異なる二つの頂点に付加されたの値が異なることと定義しています。（Pr[x]は事象xに関する確率）

　　Pr[Zは正付加であるが、Z1,Z2,…,Zpは正付加でない]

　　≦　Pr[Z1,Z2,…,Zpは正付加でない|Zは正付加である]

　　　　※Pr[A|B]はB上のAの相対確率（Pr[A∩B]/Pr[B]）を表わしている
　　　　
　　=　Pr[Z1は正付加でない|Zは正付加である]×Pr[Z2は正付加でない|Zは正付加である]×…
　　　　×Pr[Zpは正付加でない|Zは正付加である]

　　≦　Pr[Z1は正付加でない]×Pr[Z2は正付加でない]×…Pr[Zpは正付加でない]

上の式の二番目から三番目の等号で結ばれた式の関係は”Ziが正付加でない”という確率変数が”Zは正付加である”上の相対確率として独立であることを用いています。

同じ式の三番目から四番目ですが、以下の図を用いて説明すると、

三番目の式はB/(B+C)で表わされ、四番目の式は（A+B)/(A+B+C)と表わされます。証明したいことは、

　　B/(B+C)≦(A+B)/(A+B+C)

ですが、分母を払うと

AB+B^2+BC≦AB+AC+B^2+BC
　　　　0≦AC

と変形され確かに成立します。

ところで、補題a（「その7」参照）で見てきたように、


　　　Pr[Ziは正付加でない（ノード集合Ziの二つのノードが同じ番号を取る）]≦lC2/(k-1)　

ですから、

　　　Pr[Zは正付加であるが、Z1,Z2,…,Zpは正付加でない]≦（lC2/(k-1)）^p

となり、花つみ一回ごとに、高々（lC2/(k-1)）^p・(k-1)^nの新しい否定テストグラフがAЦB≦A∨Bを満たさないことが分ります。

したがって、全体では高々2m回の花つみがありますから、次の数で抑えられます

　　　2m・（lC2/(k-1)）^p・(k-1)^n

(2)　AПB≦A∧B　が成立しない場合
　補題b（「その8」参照）の時と同様に、A∧BからAПBを作る過程に従って考える

(a)┌Xi┐∧┌Yj┐を┌Xi∪Yｊ┐書き換えるとき

　┌Xi∪Yｊ┐≦┌Xi┐∧┌Yj┐

がどんな否定グラフでも成立するので問題がないことになります


(b)|Xi∪Yｊ|>l+1のとき┌Xi∪Yｊ┐を消すこと

これはサーキットのサイズが小さくなることなので問題ないということになります


(c)花摘みの場合

　これは(1)と同様に考えます。

したがって、全体として

　4m・（lC2/(k-1)）^p・(k-1)^n

となり、mが十分に大きければ

　4m・（lC2/(k-1)）^p・(k-1)^n≦　m^2・（lC2/(k-1)）^p・(k-1)^n

が成り立ちますから証明は終わりました

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

おはようございます。日本語には同音異義語が多く、これがいろはうたや駄洒落などの多く言葉遊びを生む要因にもなっています。でも、ここ最近随分寒くなってきてるので、そんなことをすると滑ってさらに寒くなるといけませんから、近似られたサーキットの方をを以下説明しましょうね。うう寒い。


今回は補題bを説明していきます。

【補題b】Cはモノトーンサーキットとする。このとき、肯定的テストグラフでそのグラフではC≦C'が成立（「その3」を参照）しないようなグラフの数は

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

　　　　　※ただし、kはクリークとなるノードの数（「その3」参照）、
　　　　　　　　　　　lは濃度、m=(p-1)l(「その5」参照)、nはノードの数
　　
を満たす

【証明】
いま、

　　A=┌X1┐∨┌X2┐∨…∨┌Xr┐,　B=┌Y1┐∨┌Y2┐∨…∨┌Ys┐

として、

　　A∨B≦AЦB　　または　　A∧B≦AПB

が成立（「その6」参照）しないような肯定的テストグラフの数が、高々

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

であるということを言えば、このような近似サーキットへの変換にかかる計算量はsize(C)で押さえられる、つまりたかだかクリーク表示の数であることは明らかですから、補題は証明されるということになります。

まず、AЦBの方ですが、花つみの結果においても近似サーキットは元のサーキットに比べ重複がある可能性がありますので、常に、A∨B≦AЦBとなり、問題ありません。

つぎに、AПBの方を考えるます。「その6」で行った作る過程を検討してみると、

(1)┌Xi┐∧┌Yj┐を┌Xi∪Yｊ┐に書き換るのは、どんな肯定的テストグラフにおいても同値であるので問題ありません。

(2)もし|Xi∪Yｊ|>lならば┌Xi∪Yｊ┐を消す場合。この場合はXi∪Yｊ|を含むような肯定的テストグラフがどれだけあるかを考えます。いま|Xi∪Yｊ|>lすなわち、|Xi∪Yｊ|≧l+1ですのでXi∪Yｊを固定すれば、肯定的テストグラフのk個のクリークをなしているノードの中にすくなくてもl-1個のノードを持つXi∪Yｊは存在し、それ以外の同じ数の消す訳ですから、組み合わせは多くても、

　　(n-l-1)C(k-l-1)

であることが分ります。ところでこの消すノードの数は高々m^2ですから全体としては

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

となります。

（3）花つみでは、AЦBの場合と同様につねに、A∧B≦AПBとなりますので問題ありません。

以上のことより、全体としての数は

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

であることが証明されました

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

おはようございます。収穫の秋、食欲の秋でおなかがすいて困りますね。もっともおなかがすかないのも困りますが。小さい秋はここにもあります、とだけ今日は自己主張しましょうか。もっとも、ありがた迷惑でもう飽き飽きだ、というご意見の方がマスメディアでも述べられるかのように大多数かもしれませんが


さて、今回から三つ補題を紹介することにします。どういう名付けにするかに少し困りましたが、とりあえず補題a,b,cとすることにします。まず補題aから。


まず、補題aから

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

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

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


【証明】いま近似サーキットを
　

　　　　　


とする。A≠0ならばA≧┌X1┐は明らか。

また、否定的テストグラフ（「その2」参照）においてクリーク表示┌X1┐が0となるのはテストグラフに付加された1,2,…,k-1で、X1の二つの頂点が同じ値を取る場合。一方、1,2,…,k-1の番号をn個のノードに付加する仕方は(k-1)^n通りで、どの付加の仕方も同じ確率で生じます。ノード集合X1の二つのノードが同じ番号を取る確率がをPx1とすると


　　　Px1≦|x1|C2/(k-1)≦lC2/(k-1)　　（1）

したがって、否定テストグラフにおいて┌X1┐が0を取る確率も（1）式で表わされるため、逆に否定テストグラフがあるクリーク表示┌X1┐で１を取る確率は

　　1-Px1≧1-lC2/(k-1)　　　　　　　　　　（2）

として表わされる。これが(k-1)^n個ある否定テストグラフの組み合わせそれぞれに言えるということから、補題は証明された、

ということになります。

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

おはようございます。昨日は疲れから少々早めに寝てしまい、その分少し早めに目が覚めてこの記事を書いているのですが、やっぱり夜遅くやるよりは少し寝てからの方が良いですね。でも目をつむっているだけでも十分であるとかないとか。何となくが何となく良い感じであるのはなんとなくですが良い感じですね。それにしても、テキストにはいろんな文字が使われていまして、似ている文字を選んできて使用するというのも一苦労なんですよ。今回近似サーキットを扱っていますが、近似サーキットの記号を近似させるのにも一苦労ってどういうことなんでしょうかねえ、ふう。


さて、今日は前回の定理を用いて近似サーキットの定義をしていきます。

まず、

　　m=(p-1)^l・l!

とおきます。ここでlは濃度ですがpはよりも大きい整数です。こうしておくと、花つみが終了すればクリーク表示の数は<2m(「モノトーンそしてmP≠mNP その4」参照）から≦mとなるのが分ると思います。

【論理和型近似サーキットの定義】
つまり、「モノトーンそしてmP≠mNP その4」で考えていた、C=C1∨C2の近似サーキットC'1＝A,C'2＝Bとして表わし、それぞれの花つみが終わっってクリーク表示の数が≦mなったものを∨で結んだものを

　　AЦB

と表わすことにし求める近似サーキットであると定義します。


次に論理積型の近似サーキットを考えていきます。

論理和型と同様にC=C1∧C2において、近似サーキットC'1＝A,C'2＝Bとして表わし、論理和型と同様に
　
　　C'1＝A=┌X1┐∨┌X2┐∨…∨┌Xr┐,　C'2＝B=┌Y1┐∨┌Y2┐∨…∨┌Ys┐

となっているとします。このとき、C=C1∧C2は、
　　　　　　　　　

となり、ここで┌Xi┐∧┌Yj┐はクリーク表示ではなく、また個数も≦m^2であるのは明らかで、これは花つみをしてもmより大きいかもしれないという可能性があります。

【論理積型近似サーキットの表記と求め方】

まず、求める論理積型の近似サーキットを
　
　AПB

と表記することにします

その求め方として以下の手順を採用します

(1)┌Xi┐∧┌Yj┐を┌Xi∪Yｊ┐に書き換えます。

　※テキストには説明ありませんが、┌Xi┐∧┌Yj┐が真ならば┌Xi∪Yｊ┐は必ずしも真ではありませんが、┌Xi∪Yｊ┐が真ならば┌Xi┐∧┌Yj┐は必ず真であるため置き換えることが可能だということだと思われます。


(2)もし|Xi∪Yｊ|>lならばXi∪Yｊは真となりますので、┌Xi∪Yｊ┐を消します

(3)そのようにした上で花つみを行いAПBを得る

という事になります。



次回からは、以上で完成した近似サーキットについての三つの補題を順に説明していくことになります。

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

おはようございます。昨日神社にお参りしたら、七五三さんのかわいらしいお嬢ちゃんがいたりと華やかでした。男の子は五歳の時一度、女の子とは三歳と七歳の二度、参拝するわけですが、幼い頃は理由が分らず、だだをこねた記憶があるような。もっとも、千歳飴がうらやましかったんですけどね。


さて、今日は、近似サーキットに関する補題を一つ説明します。テキストによると、エルデス(Erdös)とラドー(Rado)によるものだそうです。

【ErdösとRadoによる補題】
　いまŹを集合の集合で、Źの元となる集合の濃度(単位集合あたりの元の数)は高々lとします。

　　|Ź|>(p-1)^l・l!   　　　　　　　　　 (1)

ならば、その中にはp個の花びらによるヒマワリが存在する

【証明】
　数学的帰納法によって証明します

(i)l=1の場合
　Źの元になる集合の濃度が1という意味ですので明らかにどんなｐ個の元集合を持ってきてもヒマワリになります。
　例えば　

(ii)l≧2の場合
　ḾをŹのなかの互いに素な集合の集合の中で極大なものとします。そのうえでS=∪Ḿと定義します

　
　　（例）l=8 とし、元である集合の元を10進整数で示すことにすると
　　　 Ź1={{1},{1,2},{2,3},{4,5,6},{7,8}}

　　　　の場合　その互いに素な元の集合は

　　　　{{1}},　{{1,2}},　{{2,3}},　{{4,5,6}},　{{7,8}},
　　　　{{1}},　{{2,3}},　{{1},{4,5,6}},　{{1},{7,8}},
　　　　{{1,2},{4,5,6}},　{{1,2},{7,8}}
　　　　{{2,3},{4,5,6}},　{{{2,3},{7,8}},　
　　　　{{4,5,6},{7,8}}
　　　　{{1},{2,3},{4,5,6}},
　　　　{{1},{2,3},{7,8}},
　　　　{{1},{4,5,6},{7,8}},
　　　　{{1,2},{4,5,6},{7,8}},
　　　　{{2,3},{4,5,6},{7,8}},
　　　　{{1},{2,3},{4,5,6},{7,8}}

     　の19通り

　　　　大きい方から3つ選びこれをSとすると
　　　　　S1={{{1},{2,3},{4,5,6},{7,8}},　{{1},{4,5,6},{7,8}},
         　　{{1,2},{4,5,6},{7,8}}}



　さて、いま|S|≧pならば、Ḿ同士がひまわりでそこで花つみをすれば良いということになります。


　　（例）上の例でp=2 とする　|S1|=3 だから、

　　　　　S1={{{1},{2,3},{4,5,6},{7,8}},　{{1},{4,5,6},{7,8}},
         　　{{1,2},{4,5,6},{7,8}},{{2,3},{4,5,6},{7,8}}}

  　　　の、どの元を二つとっても元同士がひまわりになり、
　　　　そこで花つみをすればŹ1の花つみにもなっている


次に　|S|<pの時を考えます。このとき次のことが成立します

　　|S|≦(p-1)l　　　　　　　　　(2)

上の式はとりあえずはいまは意味がないのですが、lは正の整数ですので|S|<pから導き出せる当然の式です。

また、Ḿに属する集合が互いに素である事と、Mが極大であることから、次のことが言えます

　　Z∈Ź　→　S∩Z≠φ

いまi∈Sなるiについて、iがどれだけのŹの元（げん）Zの元（げん）になっているかを考えると、(2)式よりあるi∈Sで少なくどもŹの1/{(p-1)l}部分のZの元になっていますので、この元iを固定して、Ź'を

　　Ź'={Z-{i}|i∈ZでZ∈Ź}

と定義すれば、仮定(1)式を用いて次の式が出てきます。

　　|Ź'|=|Z|/{(p-1)l}＞(p-1)^(l-1)・(l-1)!

lについての数学的帰納法の仮定よりŹ濃度l-1においてp個のひまわりを持っています。

以上(i)と(ii）によって数学的帰納法によりŹはp個のひまわりを持っていることが証明されました。


この補題の証明はは数学的帰納法を用いるということと(i)がポイントとなっていますね。


さて、次回は、近似サーキットの定義を完成させます。少々難しいですがどうかついてきて下さるとうれしく存じます。
　

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

おはようございます。おめでとうございます。土曜も日曜もなくくるくると回っております～。私の頭の中以外、何がおめでたいのか分りませんが。とりあえず、今日から十一月ですので、元気よくやってみました。


さて、今回から数度に分けて、サーキットに近似サーキットを適用していくやり方を説明していきます。考え方としてはサーキットをリーフから部分、部分に分けて近似サーキットに置き換えていくという考え方です。

そういうわけで、まずリーフから。

 (i) 枝{i,j}を持つリーフをのインプットのブール変数をxijと表記するとした場合、i≠j)┌{i,j}┐を近似サーキットと定義する

次に、C=C1∨C2の時を考えます

 (ii)C=C1∨C2で近似サーキットC'1,C'2が以下のように近似サーキットの論理和ですでに結ばれているとき
　　　
　　　C'1=A=┌X1┐∨┌X2┐∨…∨┌Xr┐,　C'2=B=┌Y1┐∨┌Y2┐∨…∨┌Ys┐

これを論理和で結ぶと　　　

┌X1┐∨┌X2┐∨…∨┌Xr┐∨┌Y1┐∨┌Y1┐∨┌Y2┐∨…∨┌Ys┐

となり、r+s個のクリーク表示を論理和∨で結んだものになるためr+s≦2mである事は言えるが、r+s≦mは満たさないかもしれず、すなわち、リーフをはじめノードのサイズが元と同じにならないかもしれません。そのために次のようなことを考えます。


【ヒマワリと花つみ】
　いま相異なる集合Z1,Z2,…,Zpで、Zi∩Zjがすべてのi≠jについて等しいとき、Z1,Z2,…,Zpを中心Zi∩Zjをもつヒマワリと呼びます

また、ある数p≧2を定めて、現在問題になっているノード集合の集合{X1,X2,…,Xr,Y1,Y2,…,Ys}を見ます。そのとき、もし、X1,X2,…,Xr,Y1,Y2,…,Ysの中でp個の集合がヒマワリを作っているとすれば、そのp個のノード集合をそのヒマワリの中心で置き換える、という事にします。この操作を花つみと呼ぶことにします。花つみは常にこれ以上できなくなるまですることにします。頂点の数は花つみをするたびに減りますので、高々2m回の花摘みしかできない、という事になります。

これに関する補題（ある定理の中のサブ定理のことを補題と言います）がありますが、少し難しいのでそれはまた次回説明することにしましょう。

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

おはようございます。大学は宮崎の大学に通ったのですが、日本も南の方に行けば行くほど時間にはだいたいでして、あちらには日向時間というものが存在しました。だからいつだってじれったかったりするのですが、慣れればそれが良かったりすると言う恐るべきもの。ちゃわちゃわっていう女の子の方言もかわいかったですね。もちろん熊本弁もかわいいですが。何処に行ってもその地方の女の子の方言の語尾ってかわいくて味がありますよね。


さて、今回から少しずつmP≠mNPを説明していくことになります。この結果はテキストによるとA.RazborovとA.E. Andreevがほとんど同時に独立に証明したものである、とあります。

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

　　　　

  ※註　当然のことながら、ここでf(n)=Ω(g(n))は、c>0なる実数が存在していればf(n)≧c・g(n)となるような関数


【証明の方針】
もしサーキットサイズが小さければ、そのサーキットはだいたいの肯定テストグラフに0の値を与えたいていの否定テストグラフには1値を与えることをいう


以上のようなやり方でやっていくのですが、詳細は追々説明するにしても、これがいくつもの補題があるのでややこしいです。

さて、だいたいの、ということがありましたが、考え方としてまず肯定的テストグラフであるか否定テストグラフであるかどうかの判断はn個のノードがある場合k個のノードかk-1個のノードのクリークがあるかどうかを判定してから詳細に判断すればいいわけで、そういう考え方の元、以下にクリーク表示というものを定義します。

【クリーク表示の定義】
　グラフGのノード集合Xがあったときに、これがクリークになっているときに、
　
　 ┌X┐(G)=1

そうでないときには

　 ┌X┐(G)=0

と┌X┐を定義してクリーク表示と言うことにします


また、クリーク表示を用いて近似サーキットというものを考えます。まず定義の方針としては、高々m個のクリーク表示を∨で結んだもの、すなわち┌X1┐∨┌X2┐∨…∨┌Xr┐でr≦m、またさらに|Xi|≦lがすべてのi=1,…,rに対して成立しているものとします。ただしm≧2かつl≧２です。さて元のサーキットのノード数nやいくつのノードのクリークであるかを示すkにk関する制限は後ほど述べていくことにして、モノトーン・サーキットCを近似サーキットC'にする場合の定義の条件というものを記しておきましょう。

【近似サーキットを定義する際の条件】
　1．Cが小さいモノトーン・サーキットならば、たいていの肯定的テストグラフGについて
　　
　　　　C(G)≦C'(G)

　　が成立している。

　　さらに、たいていの否定テストグラフGでは

　　　　C(G)≧C'(G)

　　が成立している。

すなわち、近似サーキットの方が肯定テストグラフにおいては成立するものが多く、否定的テストグラフの方では元のサーキットの方が成立するものが多いという事ですが、証明の方針に従って

　2．すべての近似サーキットは、たいていの肯定的テストグラフに0の値を与えるか、またはたいていの否定的テストグラフに1を与えるかのどちらかである

という条件も加えます

次回は、この近似テストグラフをリーフから順に定義していきます。

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

おはようございます。何故か休みの日の朝が一番しんどいという気がするのですが何故でしょうか。そうです、それはこのブログの記事をを書かないといけないから……。え、あ、なぜか、またしーんとしちゃって……。え、あの、もとい、その前の日にしっかりと仕事をがんばってきているからです。ええ、多分、そうです。いや、多分、そうに違いありません。


さて、今回は引き続き定義となります。

前回は言語Lやpredicate Pがモノトーンであるとはどういうことかと言うことを定義しました。今回はそれらがクラスmNPやクラスmPに属することがどういうことかということについて定義していきます。

【クラスmNPに属するという事の定義】

• 言語LがmNPに属することをLがモノトーンであってさらにNPに属することとする
• predicate PがmNPに属することも同様にpredicate PがモノトーンであってさらにNPに属することとする

【クラスmPに属するという事の定義】

• 言語LがmPに属することをLが多項式サイズのユニフォームなモノトーン・サーキットで表わされることとする
• predicate PがmNPに属することも同様にpredicate Pが多項式サイズのユニフォームなモノトーン・サーキットで表わされることとする
  ※ここでモノトーン・サーキットとはリーフのブール変数がx1,x2,…,xnで表わされ、￢x1,￢x2,…,￢xnではないということ

さてこのほかに問題を扱う上で重要となるのが、predicate Pの扱いですが、すべての言語は自然数にコーディングできます。このコーディングした自然数を二進法で{0,1}*に変換した上で、その二進法での{0,1}*のpredicateがmPかmNPかであるかという判断をすると定義しておきます。ここはちょっと難しいですが、前回と合わせてよく考えてみて下さいね。


さて、ここまでが前提としての定義ですが、もう少し、今回の証明に必要な定義を予めやっておこうと思います。

「頂点カバー、独立セット、クリーク　その１」で頂点カバーやクリークというサーキットの問題を説明し、以下、これら三つが同等でNP完全（「頂点カバー問題がNP完全であるということ　その１」～「その４」）であるという話をさせて頂いていますが、今回このうちクリーク問題を使って考えます。


【Clique k,n(G)、肯定的テストグラフ・否定的テストグラフの定義】

そこで、Clique k,n(G)を、Gはn個のノードをもつグラフで、そこにk個のノードによるクリークが存在するかを決定する問題とします。存在すればClique k,n(G)=1、しなければClique k,n(G)=0となります

また、このときn個のノードを持つグラフが肯定的テストグラフであるということを、k個のノードのクリークを持っていて、それ以外の枝を一つも持っていないとします。肯定的テストグラフであれば、すなわちClique k,n(G)=1であることは自明です。またn個のノードからk個のノードを取ってくる組み合わせですので、nCm個の肯定的テストグラフが存在します。

同様に、n個のノードを持つグラフが否定的テストグラフであるということを、n個すべてのノードに1～k-1の値のうちどれか一つを振り当て、異なった値を持つ二つの頂点だけが辺で結ばれているグラフと定義します。否定的テストグラフであれば、すなわちClique k,n(G)=0です。またn個のノードに1～k-1の値を振り当てる組み合わせは(k-1)^n通りあります。否定的テストグラフのノードに与える値の組み合わせが違ってもグラフの形が同じだという場合もありますが、これはすべて違うグラフと見なすということにします。



以上を予備的な定義としまして、他にもう少し近似サーキットの定義などもありますが、これは、次回以降、mP≠mNPを示す定理とその証明の説明の中でしていくことにします。

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

おはようございます。今日から新章に入ります。そう言えば新米の季節ですね。おいしい新米。うれしい新米。楽しい新米。まだまだ新米（？）の私ですが宜しくお願いいたします。ちょっと嘘が入ってますかね。ええ、分っています。新米ってほどでもないって事ですよね。


さて、この章ではモノトーンのサーキットを検討していきます。思い出して頂きたいのですがこの章で言うモノトーンは「サーキットというグラフの計算量　その１」などで出てきていて、

　　　x≦y　　ならば　f(x)≦f(y)
　　　
　　ただし、x=(x1,x2,…,xn),y=(y1,y2,…,yn)で、
　　　　　　x≦yはx1≦y1∧x2≦y2∧…∧xn≦yn
　　　　　　を意味します
　
となっています。

では、本題に入り、まず今回と次回は定義をいくつか述べます。今回はモントーンな関数fや言語L、そしてクラスPの表記の一種predicate Pのモノトーンについて定義します。ただし、この章でも特に断らない限り^はべき乗を表わす二項演算子であるとします。

【モノトーンな関数ｆや言語Ｌやpredicate Pの表記によるモノトーンなクラスPの定義】

　ブール関数fがf:{0,1}^n→{0,1}、即ちこれをn個の二進数の元を持つ集合から0か1かへの2値への写像であるとする場合、fを言語

　　L={x|x∈{0,1}^nでf(x)=1}

で表わすこととします。また同時にfをクラスPのブール変数x1,x2,…,xnのpredicate P（predicateは日本語で述語の意味）とい表記の仕方で表わすときは

　P(x1,x2,…,xn)　iff　f(x1,x2,…,xn)=1

という定義になります。

さて、fがモノトーンであるとします。このとき、Ｌやpredicate Pもモノトーンとなります。

すなわち、Lのモノトーンとは

　(x1,x2,…,xn)∈L,(x1,x2,…,xn)≦(y1,y2,…,yn)→ (y1,y2,…,yn)∈L

となります。同様にpredicate Pがモノトーンであるということは

 P(x1,x2,…,xn),(x1,x2,…,xn)≦(y1,y2,…,yn)→ P(y1,y2,…,yn)
　
が成立するということです。ちょっとややこしいので今回はとりあえずここまでにしましょう。

サーキットの計算量の様々なクラス その9

おはようございます。10月ももうすぐ終わり。そうしている間にあっという間に一年も終わりそうですね。落ち葉の季節も近づきましたが、こちらも大詰め。しかしもう少しでゴールが見えてきそうで見えてこない。ちょうど十月終わりといった状況であります。


今回、「サーキットの計算量の様々なクラス」と題して代表的なクラスの計算量の考え方についてその概要を説明してきました。これがどれほどの意味を持つのか難しく、クラスAとBにおいてのクラスの分類A≠Bという、あまり関係しないのではというのが竹内外史先生のご意見のようです。そういうこともあって、ここまである程度駆け足で見てきました。

これからの進め方ですが、計算量のクラスのお話しは今回でいったん終わり、次回からはモノトーンサーキットでの問題について説明したいと思います。こちらは、分っていることが多く、また、実際の電子回路などの設計にも応用できそうな手法が多く見受けられると言うこと、などがその理由です。

では本題に入ります。

前回クラスγ/Fを

　　　γ/F={L⊆{0,1}*|∃B∈γ,h∈F,L={x｜<x,h(|x|)>∈B}　　　　　

と定義するとき、γ=P、F=Polyの場合すなわちP/Polyが重要であり、定理としてP/Polyがノンユニフォーム多項式サイズのサーキットの表わすクラスであること、などをお話をしました。今回、サーキットの計算量の様々なクラスのお話しの最後として、補足説明的なお話しをいくつかさせて頂こうと思います。

やはり前回の最後に、

「単にPをユニフォームな多項式サイズのサーキットであると見なせる観点から、P/PolyをノンユニフォームPと呼ばれるとテキストにはあります。」

と述べましたが、これに関連して、P=NP問題を解く際、NP⊆Pを解くという方法の他に、

　　　NP⊆P/Poly　

という事の検討興味ある問題だとあります。ここで、P/PolyにはクラスPに入らないものはいくらでもあるためP/PolyがクラスNPに含まれないということは明らかであるために、NP=P/Polyと言わないともあります。たとえば、P/Polyのサーキットのサイズが多項式サイズであっても、結果を自己言及できないために真偽の判断をクラスNPでは判断できない、場合があると考えれば良いのではないでしょうか。

このことに関して、テキストもあまり詳しく触れておらず、ここまで説明を省略してきたTMを拡張したOTMやNOTMを含んだ階層構造、これをポリミナル・ハイアラーキー（PH）と呼びますがこれにも関係してくるという事などが簡単に触れられています。

このあたりの議論に関しては以下の論文などを参照すると良いようです。

「R.M.Karp and R.Lipton, Turing machines that take advice, Enseign.Math,28(1982),191-209.」

これに関連していくつかの数学基礎論的・計算機理論的「言語」も紹介されていますが、今回は省略します。最後にテキストのp.55からのこの節に関する最後の部分を引用して終わりたいと思います。

「　不思議なことに、以下の重大問題、いろいろなクラスA,BについてA≠Bを証明したいという議論の中で、このユニフォームの概念が用いられることはほとんどない。
　まだ学問が未発達で、それが関係する段階に到っていないのか、それとも本質的にクラスの分類A≠Bという問題には、ユニフォームという概念が関係しないのか？すなわち今まで考えられているクラスには、その分離の問題はユニフォームという性質とは独立の問題なのかは分らない。
　しかし著者は後者の方の意見に傾いている。」

サーキットの計算量の様々なクラス その8

おはようございます。いかに失うものもないタコのようなふにゃふにゃのしている私でも、いろいろ悲しいことはあります。しかし、生きているだけで必要にして十分であるはず。ええ、すでに何を言っているか自分でも分りませんが、さて、今回のことをきちんと説明できるのでしょうか。


前回クラスγ/Fを

　　　γ/F={L⊆{0,1}*|∃B∈γ,h∈F,L={x｜<x,h(|x|)>∈B}　　　　　①

と定義するとき、γ=P、F=Polyの場合すなわちP/Polyが重要であるというお話をしました。今回は、以下の定理を説明します。

【定理】　L∈P/Polyの必要十分条件は
　　

で定義されるブール関数の列fnが多項式サイズのサーキットで計算されることである。

すなわち、P/Polyがノンユニフォーム多項式サイズのサーキットの表わすクラスである

【証明】
(i)L∈P/Polyを仮定する

このときPに属するB（①式での∃B∈γの部分）とPolyに属するh（①式でのh∈Fの部分）で

　　　　L={x｜<x,h(|x|)>∈B}　

を満たすものがあるという事になります。以下n=|x|と表わすこととし、

　　　　m=|<x,h(n)>|

と定義すれば、多項式サイズのサーキットCmで


　　　　<x,h(|x|)>∈B　iff Cmは<x,h(|x|)>に対して1を計算する
　
　　　　　※iffは同値関係をあらわす


を満たすものが存在するという事になります。なぜなら、定義から「<x,y>はO(|x|+|y|)の時間でx,yが計算される」からです。(前回の記事を参照して下さい）

また、Cm以外のリーフがm個のサーキット全体C'nを考えても、mはnで押さえられており、かつ仮定からLはクラスPであり、Pであれば、前々回説明したように　多項式サイズのサーキットによって計算可能となるからです。従って、まず必要条件の証明が終わりました。


(ii)Lが多項式サイズのサーキットCnで決定されると仮定する

このCnをコーティングするようなh(n)があり、|h(n)|はnの多項式p(n)によって押さえられる、すなわち

　　　|h(n)|≦p(n)

であるとします。このことは、すなわち、h∈Polyである事を意味しますね。（前回のPolyの定義を参照して下さい）

一方仮定より、入力xと与えられたCnから出力が1か0かというのは多項式時間により決定できますから、クラスPであることは明らかです。このことをBとすると、

　　 x∈L　iff <x,|h(x)|>∈B

となりますので、L∈P/Polyが導かれ、十分条件が証明されました


単にPをユニフォームな多項式サイズのサーキットであると見なせる観点から、P/PolyをノンユニフォームPと呼ばれるとテキストにはあります。

次回はもう少し補足説明をして、今回のクラスの話を終えたいと思っています。しかし、もう少し説明することもあるかなとも考えていますので、現在少し悩んでいるところです。

サーキットの計算量の様々なクラス その7

おはようございます、ではなくすでに、こんにちはですね。いや、がんばっている分、眠くなる今回の記事。報われない思いがするのは私だけでしょうか。などと言いつつ、途中疲れて寝てしまったのも私。まったく反省しきりでございます。


さて今回から、ノンユニフォームの多項式サイズのサーキットを表わすクラスについて、以下数回にわたって考えていくことになります。

前回同様、注意点としてx^iという式の^はべき乗を表わす二項演算子とします。

今回は必要な定義についてです。いろいろ記号が出てきます。できるだけ解説を入れて説明したいと思いますが、「チューリングマシンの数理モデル」や「クラスPとチューリングマシンその１」などの記事もご参考頂ければ幸いです。


【関数集合Fの定義】
まず、Fをh:N→Σ*なる関数hの集合とします。ここで、Nは自然数全体の集合、Σ*は入力記号の全体の集合。従ってここではすべて自然数があればそれを入力全体の集合にするようなそのような関数をh、その集合をFとすると言い換えることができます。


【関数集合Polyの定義】
次に、Polyを定義して、|h(n)|がn（入力xとしたときの|x|）の多項式で押さえられているすべてのh:N→Σ*の関数の集合とします。


【関数集合γおよびγ/Fの定義】
γをL⊆{0,1}*なる言語Lのクラス、即ち、言語Lはすべての2進数全体の部分集合で、Lの中の集合（クラス）をγとしたときに

　　　　< , >:({0,1}*)^2→{0,1}*

が1対１の写像を表わす関数、言い換えれば、({0,1}*)^2を{0,1}*にへのコーディングであり

　　　　|<x,y>|=O(|x|+|y|)

を満たすものであるとする。ただし<x,y>はO(|x|+|y|)の時間でx,yが計算されるものとする。このような<,>の例はいくらでもありますね。

このとき、Fの助けを借りて、γから計算できるクラスγ/Fを次の式で定義するものとします。

　　　γ/F={L⊆{0,1}*|∃B∈γ,h∈F,L=｛x｜<x,h(|x|)>∈B}

これは、非常にややこしいのですが慣れて頂くほかなく、まず、L=｛x｜<x,h(|x|)>∈B}によってBが規定され、そのうちの∃Bを元とするという事で
が規定されています。なんだこりゃですね。

こうしてみると、<x,h(|x|)>が与えられればxは簡単に計算できます。すなわち、この場合h(|x|)が助けを与えているわけですが、そういう余分な情報を<x,h(|x|)>は持っていると見なせるということになります。

さて、このような場合

　γ＝P, F=Poly

のP/Polyが重要になってくるということで、次回からはこの解説になります。

サーキットの計算量の様々なクラス その6

おはようございます。「一粒で何度もおいしいこの冒頭の云々」と前回書いたところ非常に微妙な反応がありましたので、一粒で何度も微妙な味わいのあるこの冒頭のつかみの部分とお詫びして訂正させて頂きたいと思います。


さて、今回まではユニフォームのクラスについてもう少しお話しすることになります。

ここまで、論理式やサーキットの計算量のクラスがなんであるかと言うことを考えていましたが、今度は逆にクラスPをサーキットで表わすということについて考察していきます。

再びTM（チューリングマシンの略、以下同じ）のインプットがx、n=|x|として処理時間がt(n)、空間量がs(n)であるようなプログラムMの場合を考えます。

前にも言いましたが、プログラムはすべてコーディングして自然数に表せますし、ご存じの通りコンピュータの中ではすべてが二進数で表わされていますので、結局|x|=nなるxは、nビットの0と1で表わされる二進数の元を持つ集合{0,1}^n(※)の元ということにもなります。

※注：{0,1}^nの　^nの部分はべき乗を表わす数字のように右肩に乗るようなものですが、便宜上、以下このように表わしていきます)

このような場合、言語LがTMのプログラムMで決定されるとすると以下のような定理がなり立つという事になります。

「プログラムMで決定される言語LはサイズがO(t(n)log s(n))のサーキットで表わされる」
（※註：テキストでも証明は省略されており、参考文献があります。「I.Wegener, The complexity of Boolean Functions, John Wiley and Teubner,1987 pp.271-277」）

この定理は要するに、クラスP は多項式サイズのサーキットによって計算可能ということになります。当然と言えば当然ですけど、結構これも難しい証明があるようですね。

もう少し考察を進めると、ここまで、多項式サイズのサーキットであっても計算量がクラスPであるためにはユニフォームという条件が必要だということでお話をしていました。言い換えれば、クラスPはユニフォームな多項式サイズのサーキットで表わされる言語全体と言うこともつまりそう定義することも可能ということになります。

さて、ここからはテキストを引用して終わりましょう。一部前回引用した部分も含みます。

「（上のようにクラスPがユニフォームな多項式サイズのサーキットで表わされる言語全体と定義できると言うことは）NC^1とPとの関係において重要である。すなわちNC^1は多項式サイズの論理式、Pは多項式サイズのサーキットということになる。この意味ではNC^1はPの純粋な部分という気分がする。したがってPについての問題はNC^1にあてはめてまず考えるのが良いと思う。特にP=NPの問題のためには、まず

　NC^1≠AC^1

をかんがえ、解決するのが本質に迫る方法の一つだと思う」

サーキットの計算量の様々なクラス その5

おはようございます。一粒で何度でもおいしいこの冒頭のつかみの部分。実はこの部分が一番時間と労力を使っているのでは無いかと思われるというのは内緒です。いや、しかし、よく考えればそれこそP=NP問題。テキストに書かれている部分は分っている事実ですので計算量はクラスP ですからね。だから難しくないか、といえばそうでもないところが、この世の深淵に触れる一事実というべきなのでしょうか。


さて、前回は、ノンユニフォームを考える場合の制限とPSPACE、LSPACE（この記事ではLとも表記される）について少し触れました。空間についての計算量の考察は、

　L⊆P

　L≠PSPACE

　NC^1⊆LSPACE⊆AC^1

が前回挙げられた証明済みの関係ですが、ユニフォームの制限がある場合、一般に、

　NC^0⊆AC^0⊆NC^1⊆AC^1⊆NC^2⊆AC^2⊆………⊆NC=AC⊆P

という事が成り立ちますから、LSPACEをLと表わすと

　　NC^0⊆AC^0⊆NC^1⊆L⊆AC^1⊆NC^2⊆AC^2⊆………⊆NC=AC⊆P

という事は容易に分かると思います。しかし、この包含関係のイコールの部分が成立するかどうかについては、一般には成立しないと思われているようですが、この予想で証明があるのは、

　AC^0≠NC^1

だけという大変難しい問題のようです。

竹内先生におかれましては、このあと、P=NP問題については、


「
　NC^1≠AC^1

を考え解決するのが本質に迫る方法の一つと思う」(テキストp.47)


と書かれています。これについては追々説明していくということで、まず、ノンユニフォームでの場合のNC^1についてもう少し分っている事実などを述べていきたいと思います。

NC^1について、多項式このインデグリーを2に直すのに必要な計算量はO(log n)になることは自明だと思います。次に多項式個のアウトデグリーを1個のアウトデグリーに変換するには多項式時間で済むという事になります。言い換えると、NC^1は多項式サイズの論理式に変換することができるでしょう。

ところで、証明は省略しますが、Spiaの定理というものがスレッシュホールド関数を扱う場合分っている事実として証明されていますので、これを使うと、NC^1は多項式サイズで深さがO(log n)の論理式で表わされるという事が分かるということになるようです。

「このようなNC^1の定式化はNC^1の内容を良く表わす上で重要である」(テキスト p46)

と竹内先生は書かれていますので、ご紹介しておきます。

サーキットの計算量の様々なクラス その4

おはようございます。ではなく、今日はになってしまいました。団体競技だとユニフォームがありますよね。無いと何となく締まらない感じがするのは私だけでしょうか。しかし、学校の制服となるとどうなんでしょうね。そういうふうに、いろいろ悩ましいユニフォームですが、サーキットのクラスにおいてもなかなか悩ましく、いやいや、だからって何もない方が良いって事じゃ無いんですけどね。

今回はノンユニフォームの場合を考えると言うことでした。

まず、現在考えている族{C1,C2,…}で表わされたサーキットや論理式がサイズにおいてが多項式サイズであるという制限を外すとどうなるかというと、インデグリー1であってもチューリングマシンでの計算自体は多項式時間で終わらない可能性のあるものはいくらでも考えられますので、そういうものは計算不可能すなわちクラスPには入らないということになります。

そこで、NC^iやAC^iについて考えるときユニフォーム即ち以下の定義を「サーキットの計算量の様々なクラス　その2」示していますが


【ユニフォームの定義】
ある種の族{C1,C2,…}で表わされたサーキットや論理式などを自然数に置換し、置換した自然数を再び同じ族で表わすことができるとする。このとき

　f(i)=Ci　

という関数があって、それをクラスAC^0で表わすことができるもの



この制限を廃したNC^iやAC^iについて考える、という事になります。

これがこれからの流れにおいて考慮に入れておく点ですが、その他いくつかこれまで省略しておいたPSPACEというものを補足したいと思います。

まず、現在TM（以下チューリングマシンをこう表記する）で多項式時間で解けるかどうかがクラスPに入る問題かどうかと言うことでインプットxに対しn=|x|としたときの時間t(n)をもっぱら扱ってきましたが、一方でTMのヘッドの動く距離（あるいはテープの動く距離）が有限であるかどうか問うことも問題となるということを「クラスPとチューリングマシンその2」）においても簡単に触れていました。ここでは、その空間的な量をs(n)と表わすことにし、その量が多項式で表せるものを多項式空間PSPACEとします。

ところで、ヘッドはテープの同じ場所を何度も訪れることができるために、一般に

　P⊆PSPACE

であることは容易に分ります。

ところで、多項式空間では無く、TMのプログラムがO(log n)で必ず停止し受容されると言うようなプログラムのクラスもあります。これはLOGSPACEもしくはLSPACEで表わされ、時には単にLと書かれる場合もあります。

LとPの関係は

　L⊆P

となっているようですが、はっきり証明があって分っているのは

　L≠PSPACE

そして、

　NC^1⊆LSPACE⊆AC^1

などで、分っていないことがかなり多いとテキストには書かれています。

サーキットの計算量の様々なクラス その3

およげたいやきくんではありませんが、まいにちまいにち、鉄板の穴の中でくるくると回されながら焼かれている気がしている今日この頃。今朝もくるくると早朝から働かせていただいております。

さて、今回はNC^iとAC^iの包含関係などを検討していくことになります。

テキストによると、このような議論をするときユニフォームとは限らないサーキットの族Cnが、多項式のサイズで深さが

であると考えます。

ところで、NC^iのインデグリーが定数で抑えられているのに対してAC^iはなんの制限もありませんので一般的に、

　NC^i⊆AC^i

であることは明らかです。

次に、NC^iのインデグリーを抑えている定数をcとするときインデグリーcのサーキットをインデグリーが0か2のバイナリーサーキットに置き換える事を考えると、このことは可能であることもサーキットのサイズsはlogc倍増えるであろう事は簡単に分ります。

ところで、

　AC^i⊆NC^i+1

を検討してみると、これは定義からして深さはO(log n)倍、サイズもこの記事の最初に定義したように多項式倍に増える、という事になるだけと言えます。

ここで、

　NC=∪NC^i,　AC=∪AC^i

とすると、以上より

　NC=AC

ということが言え、NCやACにはユニフォームという制限、即ち、自己言及可能であるという制限がついていますので

　NC=AC⊆P

が言えるということになります。すなわち、たいていのサーキットはチューリングマシンで計算可能であると言える、という事になります。

今回はここまでです。次回からはNCとACのユニフォームという制限を外した場合、即ちノンユニフォームなサーキットでの場合をしばらく考えるということになります。

サーキットの計算量の様々なクラス 補足1

前回の補足を少しさせて頂きたいと思います。

NC^i,AC^iの定義で、

ユニフォームなサーキットの族{Cn1,Cn2,…}で、多項式のサイズや深さが




という事をお話ししましたが、まず、どうしてこのようなことをやるのかということについて、テキストには書いてありませんが、私の思うところを少しお話ししたいと思いいます。

まず、このブログの3回目に「集合論における整数」という記事で簡単に整数や実数の無限に触れ、濃度という考え方を説明しています。今回はそれにも関係することです。

少し視野を広げてみると現在やっていることは数学基礎論（Wikipedia：http://ja.wikipedia.org/wiki/数学基礎論　を参照のこと）という分野でやっていることにあたります。数学基礎論とは数学の分野ではありますが、比較的新しい分野で、数学自体の基礎を数学によって表現できるか、その限界や方法論を扱っている分野でもあります。

どうでも良いですが、高校三年生の数Ⅲで習う微分方程式などは、フーリエ変換=>ラプラス変換という具合にして代数的に求める方法というのが確立されています。量子力学でももっぱらこういうものを使って軌道の非連続性の説明していたと記憶していますが、どうにも自分が知らないことはどうでも良い事だというように仰る方もいらっしゃるようですので、少し書いてみました。

さて、話を

について戻すと、実数の無限大をωとして扱うと、このωを一つの数として考えて、

　ω，2ω，…

となどどんどん数を増やしていき、ωのω個というのを




　

というように表記します。

サーキットは論理式で表わされ、考えられる論理式を整数に一対一で対応させるようなことを考えると、




というのが、じつは






に対応しているのではないかということは誰の目にも明らかでしょう。


さらに、このように論理式を一対一に対応する整数で表わす（以下これを整数でコーディングすると呼びます）が、この考え方は、ゲーデルが不完全性定理を証明するときに用いた考え方であり、自分自身が正しいかどうかを証明するのには自分自身で証明することはできないという考え方に用います。そういうことから、数学の特に整数を扱う部分への公理系への洞察がなされるという事になります。今回の節の最後に、言語について少し触れるかもしれませんが、ここでいいう言語というのは公理系の別名とも言えます。(どういう表記をするかということにも少し特徴がありますが）

サーキットの計算量の様々なクラス その2

しかし、どうしていじめというのは無くならないんですかね。私もんＨＫのいまはあれであれをああし続けてどうしているのか不明の方にタコだとか何とか言い続けられましたが、別にくねくねしたくてしているわけでも無し、なんでそういうことを言うかな、と思うわけですよ。要するに、気に入らないからといって何をしても良いと思っている人もたくさんいらっしゃって、こちらに原因がないとは言いきれないとは思いますがねえ。


　さて、計算量のクラスとしてNC^i、AC^iの説明に入りたいと思います。実は、

　NC^i


は


　


と

　AC^iは


　


と表記するのですが、これからたびたび説明で使う関係上、その度に図で表記するのも煩雑なのでNC^i、AC^iという表記を使わせて頂きたいと思います。多少見にくいですがどうぞご了承下さい。


まずは定義から

【NC^i,AC^iの定義】

ユニフォームなサーキットの族{C1,C2,…}で、多項式のサイズや深さが




で、NC^iはインデグリーが定数で抑えられているもの。AC^iは、インデグリーに制限のないもので計算されるブールの族。

［用語の解説］
※族：数学における族（ぞく、family）は、添字付けされた元（要素）の（一般には非可算無限個の）集まりで、対、n-組、列などの概念の一般化である。系（けい、collection）と呼ぶこともある。元がどのような対象であるかによって、点族、集合族（集合系）、関数族（関数系）などと呼ばれる。
　　（Wikipedia（http://ja.wikipedia.org/wiki/族_(数学)より引用））

※ユニフォーム：定義としては、ある種の族{C1,C2,…}で表わされたサーキットや論理式などを自然数に置換し、置換した自然数を再び同じ族で表わすことができるとする。このとき

　f(i)=Ci　

という関数があって、それをクラスAC^0で表わすことができるもの



今回はもう少しこの定義について解説したあと、次回以降、それぞれのクラスの包含関係などの考察に入ります。

今まで考察してきたもののサイズや深さはO(log n)でした。即ちこれが現時点ではもっとも一般的に有用なグラフといえるかもしれません。ところが、これはいま平面上にサーキットがあったから、そうだとも言えます。これが立体面であれば、オーダーはこの自乗になるのは自明です。そのように次元を上げていった場合などを一般化して扱うのが数学とも言えます。そういうわけで今回は、



の場合、すなわちNC^i,AC^iの場合も考察してみようということになるわけです。