Editing Communication complexity (section)

=== Example: ''EQ'' ===

We consider the case where Alice and Bob try to determine whether or not their input strings are equal.  Formally, define the ''Equality'' function, denoted <math>EQ : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}</math>, by <math>EQ(x, y) = 1</math> if <math>x = y</math>.  As we demonstrate below, any deterministic communication protocol solving <math>EQ</math> requires <math>n</math> bits of communication in the worst case.  As a warm-up example, consider the simple case of <math>x, y \in \{0, 1\}^3</math>.  The equality function in this case can be represented by the matrix below.  The rows represent all the possibilities of <math>x</math>, the columns those of <math>y</math>.

{| class="wikitable" style="font-family: monospace; text-align: right; margin-left: auto; margin-right: auto; border: none;"
! 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
|-
|}

In this table, the function only evaluates to 1 when <math>x</math> equals <math>y</math> (i.e., on the diagonal).  It is also fairly easy to see how communicating a single bit divides someone's possibilities in half.  When the first bit of <math>y</math> is 1, consider only half of the columns (where <math>y</math> can equal 100, 101, 110, or 111).