通信複雑性
さらに、ドット積が等しいかどうかに関わらず、ビット 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'} が存在する可能性である。