例: EQ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/08 03:46 UTC 版)
ここでは、アリスとボブが同じ文字列を持っているかどうかを決定する問題を例として示す。つまり、 x {\displaystyle x} と y {\displaystyle y} が等しいかどうかを判定しようということである。 x {\displaystyle x} と y {\displaystyle y} が完全に等しいことを確認するには最悪ケースで n {\displaystyle n} ビットの通信が常に必要になることは証明するのも簡単である。 x {\displaystyle x} と y {\displaystyle y} がそれぞれ 3ビットという簡単な場合を考えて見よう。この場合の等価関数は下記のような行列で表される。行はありうべき x {\displaystyle x} の値が並び、列には同様に y {\displaystyle y} が並ぶ。 EQ 000 001 010 011 100 101 110 111 000 1 0 0 0 0 0 0 0 001 0 1 0 0 0 0 0 0 010 0 0 1 0 0 0 0 0 011 0 0 0 1 0 0 0 0 100 0 0 0 0 1 0 0 0 101 0 0 0 0 0 1 0 0 110 0 0 0 0 0 0 1 0 111 0 0 0 0 0 0 0 1 見ての通り、この関数は x {\displaystyle x} と y {\displaystyle y} が等しい場所（対角線上）だけで 1 となる。1 ビット通信する毎に可能性が半分に分割されていく。 y {\displaystyle y} の最初のビットが 1 であると知っている場合、列の半分だけを考慮すればよい（ y {\displaystyle y} は 100, 101, 110, 111 のいずれかになる）。 定理: D ( E Q ) = n {\displaystyle D(EQ)=n} . 証明。 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 であると言うことができる。しかし、そのような等価行列の長方形は存在しえない。
※この「例: EQ」の解説は、「通信複雑性」の解説の一部です。
「例: EQ」を含む「通信複雑性」の記事については、「通信複雑性」の概要を参照ください。
例: EQ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/08 03:46 UTC 版)
再び、EQ の例である。確実性が求められないなら、アリスとボブは等しいかどうかの判定を O(log n) 個のメッセージで行うことができる。次のようなプロトコルを考える。アリスとボブは同じランダム列 z ∈ { 0 , 1 } n {\displaystyle z\in \{0,1\}^{n}} にアクセスできるものとする。アリスは z ⋅ x {\displaystyle z\cdot x} を計算し、そのビット（b と呼ぶ）をボブに送信する。なお、 ( ⋅ ) {\displaystyle (\cdot )} はGF(2)のドット積である。ボブは b と z ⋅ y {\displaystyle z\cdot y} を比較する。もし等しいならボブは x と y が等しいと言う事ができる。 明らかに x = y {\displaystyle x=y} なら z ⋅ x = z ⋅ y {\displaystyle z\cdot x=z\cdot y} であり、従って P r o b z [ A c c e p t ] = 1 {\displaystyle Prob_{z}[Accept]=1} である。x と y が等しくない場合でも z ⋅ x = z ⋅ y {\displaystyle z\cdot x=z\cdot y} である可能性はあり、その場合ボブは答えを間違う。これはどんなとき発生するだろうか？ x と y が等しくない場合、それらの一部の位置で以下のように値が異なっているはずである: x = c 1 c 2 … p … p ′ … x n {\displaystyle x=c_{1}c_{2}\ldots p\ldots p'\ldots x_{n}} y = c 1 c 2 … q … q ′ … y n {\displaystyle y=c_{1}c_{2}\ldots q\ldots q'\ldots y_{n}} z = z 1 z 2 … z i … z j … z n {\displaystyle z=z_{1}z_{2}\ldots z_{i}\ldots z_{j}\ldots z_{n}} x {\displaystyle x} と y {\displaystyle y} が等しいなら、 z i ∗ x i = z i ∗ c i = z i ∗ y i {\displaystyle z_{i}*x_{i}=z_{i}*c_{i}=z_{i}*y_{i}} であり、これによりドット積も等しくなる。従って、等しい項は無視して x {\displaystyle x} と y {\displaystyle y} が異なる部分だけを注目すればよい。さらに、ドット積が等しいかどうかに関わらず、ビット x i {\displaystyle x_{i}} とビット y i {\displaystyle y_{i}} を入れ替えることができる。つまり、 x {\displaystyle x} に 0 であるビットを集め、 y {\displaystyle y} に 1 であるビットを集めるよう入れ替えを行うこともできる。 x ′ = 00 … 0 {\displaystyle x'=00\ldots 0} y ′ = 11 … 1 {\displaystyle y'=11\ldots 1} z ′ = z 1 z 2 … z n ′ {\displaystyle z'=z_{1}z_{2}\ldots z_{n'}} この場合、 z ′ ⋅ x ′ = 0 {\displaystyle z'\cdot x'=0} および z ′ ⋅ y ′ = Σ i z i ′ {\displaystyle z'\cdot y'=\Sigma _{i}z'_{i}} となる。問題は、 Σ i z i ′ = 0 {\displaystyle \Sigma _{i}z'_{i}=0} であるようなランダム列 z ′ {\displaystyle z'} が存在する可能性である。各 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) 個のメッセージで計算できることを示す。
※この「例: EQ」の解説は、「通信複雑性」の解説の一部です。
「例: EQ」を含む「通信複雑性」の記事については、「通信複雑性」の概要を参照ください。
- 例: EQのページへのリンク
