サーキットというグラフの計算量 その4

秋になって、どういうわけかやる気が起こってきたのか、何となくがんばっている私。この時期になっても台風がいくつも来るわけだ、と個人的には納得してはいけないことも納得してしまいそうな今日この頃。皆様はなんの秋でいらっしゃいますでしょうか。

そういうわけで、ってどういうわけか知りませんが、最近早朝からがんばっている私。しかし、このブログ誰が読んでいるんでしょうねって自分でいったらいけないか。

今回はKhrapchenkoの定理の証明ですね。注意しておきますと、これは、パリティのリーフの数を計算すつと言うよりもう少し一般的な定理になり、この定理からパリティのリーフが求まるという順序になります。

再掲すると、

AとBとが集合{0，1}^n（0と1の元をn個持つ集合）の互いに素な部分集合だとするとき論理関数FがAとBとを分離することを、Aに対してはFが0、Bに対してはFが1となることと定義する。また、このようなとき、以下のことを定義していると、


つぎの式が成り立つ、

　　

という事でした。


以下証明です。

【Khrapchenkoの定理の証明】

数学的帰納法により次のように証明していきます。

上の式が成り立つと仮定します。


(i)　L(F)（リーフ）が1のとき
　まずL(F)=1のときの例としてF(x1,x2,…,xn)=x1となるような式を考えます。このときa～bという式は、仮にa=(0,a2,…,an)であるならばb=(1,a2,…,an)であるという事と同等になります。したがって以下のことが言えることとなり、

が成立。少し変形し、二つの式をお互いに掛け合わせれば容易に、

が導けます。


(ii)L(F)>1のとき
　F=F1∧F2とします。このときA1とA2とを次の式で定義することにします。
　
   　A1={a∈A|F1(a)=0},　　　A2=A-A1

すなわち、A1を論理関数F1でBから分離できるものだけにする、ということです。これをi回繰り返してみるとFiによってAiはBから分離できるということになり、帰納法の仮定より

という式が導き出せます。さらに、F=F1∧F2でしたからL(F)=L(F1)+L(F2)が成り立ちますから、

となります。ところで、

であることから

という式が成立することに。これは右辺が定理の右辺に相当しますから（左辺は定理の左辺より当然小さい）、従って数学的帰納法により、Khrapchenkoの定理が証明されました。上の式を変形するとこの式が成り立つことが分ります。つまり、上の式をひらめいたことがこの定理のキモということになるわけですよね。


というわけで次回は、Khrapchenkoの定理から

　　L(Parity(x1,…,xn))≧(nの2乗）

という式を証明します。上の式で(nの2乗）としてきちんと式を図にして表示していないのは、今回関係ないところだったからで、次はきちんとします。単に面倒だったから、とかそう言うわけではありません。多分………。