通信複雑性
ここでは、アリスとボブが同じ文字列を持っているかどうかを決定する問題を例として示す。つまり、 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} が並ぶ。
見ての通り、この関数は x {\displaystyle x} と y {\displaystyle y} が等しい場所(対角線上)だけで 1 となる。1 ビット通信する毎に可能性が半分に分割されていく。 y {\displaystyle y} の最初のビットが 1 であると知っている場合、列の半分だけを考慮すればよい( y {\displaystyle y} は 100, 101, 110, 111 のいずれかになる)。
また、R を R = M × {\displaystyle \times } N (ただし、M ⊆ {\displaystyle \subseteq } X かつ N ⊆ {\displaystyle \subseteq } Y)であるような A の部分行列と見ることもできる。既に k {\displaystyle k} ビットの情報をやり取りした状態を考えて見よう。ある h {\displaystyle h} ∈ {\displaystyle \in } { 0 , 1 } k {\displaystyle \{0,1\}^{k}} について、次のように行列が定義される。
T h = { ( x , y ) : {\displaystyle T_{\mathrm {h} }=\{(x,y):} 入力 ( x , y ) {\displaystyle (x,y)} でやり取りされた k ビットが h {\displaystyle h} である } {\displaystyle \}}
ここで、 T h {\displaystyle T_{\mathrm {h} }} ⊆ {\displaystyle \subseteq } X × {\displaystyle \times } Y であり、 T h {\displaystyle T_{\mathrm {h} }} は長方形であると同時に A の部分行列である。