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

今日も今日とて早朝からがんばっていますが、何となく台風上陸との報に罪悪感を感じてしまう私。関係ないのは分っているのですが。と、とにかく、被害の無いことをお祈りするのみです。


前回はKhrapchenkoの定理の証明を証明しました。今回はこれを用いて、以下の命題を証明するということの説明を行います。






まず、AとBとが２値0か1を元とし、n個の元を持つ集合{0,1}^nの互いに素な部分集合だったという事を思い出して下さい。さらに、今回は以下のようにその互いに素な集合を定義すると

　A={(x1,x2,…,xn)|Parity(x1,x2,…,xn)|=0}
　B={(x1,x2,…,xn)|Parity(x1,x2,…,xn)|=1}

論理式parity(x1,x2,…,xn)が集合Aと集合Bを分離しているのは明らかです。また、

　

　　　 　　　　　　　　※AとBの元はそれぞれのnビット。
　　　　　　　　　　　　　ゆえににAとBの1ビットの差異は
　　　　　　　　　　　　　
　　　　　　　　　　　　　n個×（集合A(もしくはB)の元の個数）


なので、これをKhrapchenkoの定理

に代入してやると求める命題

が出てくるということになります。


意外と簡単に出てくるものですね。頭のいい人の考えることは本当に違いますねえ。

さて、次は

　　　L(Parity(x1,x2,…,x2n)|)≦4・L(Parityx1,x2,…,xn))

という事から

　　　L(Parityx1,x2,…,xn))≦(nの2乗)

という事を求め、今回求めた

　　　L(Parityx1,x2,…,xn))≧(nの2乗)

と合わせ技で

　　　L(Parityx1,x2,…,xn))＝(nの2乗)

ということを説明します。(nの2乗)を




としなかったのは単に説明上の都合です。面倒だからじゃ無いですってば。