モノトーンそして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を与えるかのどちらかである

という条件も加えます

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