通信複雑性
証明。 D ( E Q ) ≤ n − 1 {\displaystyle D(EQ)\leq n-1} と仮定する。その場合、同じ履歴 h {\displaystyle h} を共有する ( x , x ) {\displaystyle (x,x)} と ( x ′ , x ′ ) {\displaystyle (x',x')} が存在する。この履歴は長方形を定義するので、 f ( x , x ′ ) {\displaystyle f(x,x')} も 1 でなければならない。定義から x ≠ x ′ {\displaystyle x\neq x'} であるが、等しいということは a = b {\displaystyle a=b} であるような ( a , b ) {\displaystyle (a,b)} を意味する。従って矛盾する。直感的に n {\displaystyle n} より小さい D ( E Q ) {\displaystyle D(EQ)} があるなら、1つより多い要素を持つ EQ 行列の長方形が定義できるはずである。その長方形の全要素は 1 でなければならず、それによって ractangle が 1 であると言うことができる。しかし、そのような等価行列の長方形は存在しえない。
各 z i ′ {\displaystyle z'_{i}} は 0 {\displaystyle 0} である可能性と 1 {\displaystyle 1} である可能性が同じであるため、これを満足する文字列である可能性は単に 1 / 2 {\displaystyle 1/2} となる。以上より、 x {\displaystyle x} と y {\displaystyle y} が等しくない場合、 P r o b z [ A c c e p t ] = 1 / 2 {\displaystyle Prob_{z}[Accept]=1/2} となる。アルゴリズムを繰り返すことによって、その正確性を上げていくことが可能である。これは、乱択通信アルゴリズムの要求にも合っている。
以上により、「アリスとボブが n ビットのランダム列を共有した場合」に互いに 1 ビットを送ることで E Q ( x , y ) {\displaystyle EQ(x,y)} を計算できることを示した。次節では、n ビットのランダム列を共有するのと同程度に O(log n) ビットのやり取りで目的を達成する方法を示す。それにより、EQ が O(log n) 個のメッセージで計算できることを示す。
0/1 入力行列 M f = [ f ( x , y ) ] x , y ∈ { 0 , 1 } n {\displaystyle M_{f}=[f(x,y)]_{x,y\in \{0,1\}^{n}}} について、 f {\displaystyle f} を決定するのにやり取りが必要な最小ビット数の最悪ケース D ( f ) {\displaystyle D(f)} は、行列 M f {\displaystyle M_{f}} の階数の対数が下限となっている。対数階数予想(log rank conjecture)によれば、 M f {\displaystyle M_{f}} の通信複雑性 D ( f ) {\displaystyle D(f)} の上限は、 M f {\displaystyle M_{f}} の階数の対数のべき乗である。D(f) の上限と下限が ( M f ) {\displaystyle (M_{f})} の階数の対数の多項式であることから、D(f) は ( M f ) {\displaystyle (M_{f})} の階数の対数に多項式的に関連していると考えられる。
r i {\displaystyle r_{i}} を選択するのに必要な通信ビット数は O(log 100n) = O(log n) である。
入力 ( x , y ) {\displaystyle (x,y)} について、 P {\displaystyle P} と P R ′ {\displaystyle P'_{R}} が正しい値を得る確率をそれぞれ p ( x , y ) {\displaystyle p(x,y)} と p R ′ ( x , y ) {\displaystyle p'_{R}(x,y)} と定義する。
ある固定の ( x , y ) {\displaystyle (x,y)} について、Hoeffdingの不等式を使うと、次のような式が得られる:
Pr R [ | p R ′ ( x , y ) − p ( x , y ) | ≥ 0.1 ] ≤ 2 exp  ( − 2 ( 0.1 ) 2 ⋅ 100 n ) < 2 − 2 n {\displaystyle \Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq 2\exp(-2(0.1)^{2}\cdot 100n)<2^{-2n}}
従って、 ( x , y ) {\displaystyle (x,y)} を任意とした場合、次のようになる: