通信複雑性
これはどんなとき発生するだろうか?
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} が異なる部分だけを注目すればよい。