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

いろいろあって、半年に一本というペースに落ちてきていますが、誰かのせいです。どいつだー。いえ、すべて私のせいなんですが。人間誰しも自分が悪すぎて恥ずかしいときには他人のせいにしたくなりますよね。特に怖い人の前では。幸い私には奥さんがいませんけれども、私の怖い人にはいらっしゃるだろうということで、やはり奥さんは大切にしないといけません。

えっと、なんだか訳が分らなくなってきましたが、話しを続けさせて頂こうと思います。

今回からしばらくは、パリティを計算するようなグラフが持つリーフの数L(Parity)についてお話しします。パリティの基本的な性質をグラフの計算量の例としてて説明するということが主な目的です。これが分ると自然と深さd(Parity)も分ります。

まず、パリティを計算する場合の論理式Fをグラフにしたものの例を下に示します。ブール変数はx1,x2,x3,x4の4ビットですが、リーフL(F)=16,深さd(F)=4となっています。ここからしばらくは、このようなグラフのリーフの数L(parity)の求め方を説明します。

図　 parity関数の例

ちなみにこういうグラフの形を二分木と呼んだりもします。そして一番上のノードを根（root）と呼びます。根からリーフまですべてのノードは下のノードからインプットとして二つの枝を持ちます。そのため二分木と呼ばれるわけです。このようなグラフの深さは必ずd=logL(F)（ただし対数の底は2）となることは自明ですね。ちなみに計算機科学などの計算機を扱う分野では対数の底は特に断らない限り2です。これは計算機の世界が基本的に2進数で物事を表現することが基本だからです。ここでも特に断らない限り以下、対数の底は2ですのでご注意下さい。

今回はまず、準備として以下のことを定義しておきます。

元が0と1からなり、n個の元を持つ集合を{0,1}^nと表記することにします。この集合｛0,1}^nの部分集合で互いに素である二つの集合ＡとＢを論理式Ｆが分離するという事を定義して、FがＡの元に対しては0、Ｂの元に対しては1を取るという事にします。

また、部分集合ＡとＢに対して以下のことを定義します。

このあとはKhrapchenkoの定理と呼ばれる次の不等式を帰納法で証明します。それは次回に。できる方は自分で証明を考えてみると面白いかもしれません。