He aquí un argumento que creo que muestra que $\log n - \omega(1)$ es imposible. (Este argumento surgió de una conversación que tuvo con Steve Fenner.)
Vamos a Alice de entrada del ser $x\in\{0,1\}^n$ y vamos a Bob entrada del ser $y\in\{0,1\}^n$. Asumir la memoria compartida las tiendas de los estados en $\{0,1\}^m$, y su estado inicial es $0^m$. Estamos interesados en el bajo-delimitación $m$ para cualquier protocolo que calcula EQ$(x,y)$.
Un protocolo dado se define por dos colecciones de funciones de $\{f_x\}$$\{g_y\}$, representando las funciones aplicadas a la memoria compartida por Alice en cada entrada $x$ y Bob en cada entrada $y$, respectivamente, junto con algunos de contestar criterio. Para ser más específicos, supongamos que si la memoria compartida siempre contiene la cadena " $1^{m-1}b$ luego de la salida del protocolo es $b$ (para cada una de las $b\in\{0,1\}$). Para su comodidad, también vamos a suponer que $f_x(1^{m-1}b) = 1^{m-1}b\:$ $g_y(1^{m-1}b) = 1^{m-1}b\:$ por cada $x,y\in\{0,1\}^n$$b\in\{0,1\}$. En otras palabras, Alice y Bob no cambiar la memoria compartida una vez que se sabe la respuesta.
Ahora, para cada una de las $x,y\in\{0,1\}^n$, considere lo que sucede cuando Alice y Bob ejecutar el protocolo sobre la entrada de $(x,y)$. Definir $A_{x,y}\subseteq\{0,1\}^m$ a ser el conjunto de todos los estados de la memoria compartida que Alice recibe en cualquier punto en el protocolo, y, asimismo, definir $B_{x,y}\subseteq\{0,1\}^m$ a los estados de la memoria compartida que Bob recibe. También definir
\[
S_{x,y} = \{0w\,:\,w\in A_{x,y}\} \cup \{1w\,:\,w\in B_{x,y}\}.
\]
Vamos a suponer que Alice va primero, por lo $0^m \in A_{x,y}$ todos los $x,y$. También vamos a hacer las siguientes observaciones:
Por la definición de $A_{x,y}$$B_{x,y}$, sostiene que $f_x(A_{x,y}) \subseteq B_{x,y}$ $g_y(B_{x,y}) \subseteq A_{x,y}$ todos los $x,y$.
Para cada $x,y$ $x\not=y$ sostiene que $1^{m-1}0\in A_{x,y} \cup B_{x,y}$, debido a que Alice y Bob salida es 0 cuando sus cadenas no están de acuerdo.
Para cada $x$ sostiene que $1^{m-1}0\not\in A_{x,x} \cup B_{x,x}$, debido a que Alice y Bob no la salida es 0 cuando sus cadenas de acuerdo.
Ahora vamos a demostrar que $S_{x,x}\not=S_{y,y}$ siempre $x\not=y$. Para ello, supongamos hacia la contradicción que $x\not=y$ pero $S_{x,x} = S_{y,y}$ (es decir, $A_{x,x} = A_{y,y}$$B_{x,x} = B_{y,y}$), y tener en cuenta el comportamiento del protocolo en la entrada de $(x,y)$.
Deje $w_t$ ser el contenido de la memoria compartida después de $t$ convierte han pasado en el protocolo, por lo que tenemos $w_0 = 0^m$, $w_1 = f_x(w_0)$, $w_2 = g_y(w_1)$, y así sucesivamente. Se sostiene que
\[
\begin{array}{c}
w_0 = 0^m \in A_{x,x}\\
w_1 = f_x(w_0) \in f_x(A_{x,x}) \subseteq B_{x,x} = B_{y,y},\\
w_2 = g_y(w_1) \in g_y(B_{y,y}) \subseteq A_{y,y} = A_{x,x},
\end{array}
\]
y, en general,
\[
\begin{array}{c}
w_{2t + 1} = f_x(w_{2t}) \in f_x(A_{x,x}) \subseteq B_{x,x} = B_{y,y}\\
w_{2t+2} = g_y(w_{2t+1}) \in g_y(B_{y,y}) \subseteq A_{y,y} = A_{x,x}
\end{array}
\]
para cada una de las $t\in\mathbb{N}$. De ello se desprende que $A_{x,y} \subseteq A_{x,x}$$B_{x,y} \subseteq B_{y,y}$.
Pero ahora tenemos nuestra contradicción, suponiendo que el protocolo es correcta: dado que el$A_{x,y}\subseteq A_{x,x}$$B_{x,y} \subseteq B_{y,y}$, se deduce que el $1^{m-1}0 \in A_{x,x}\cup B_{y,y}$, así que Alice y Bob salida de la respuesta incorrecta 0 en $(x,x)$ o $(y,y)$.
Cada una de las $S_{x,x}$ es un subconjunto de a $\{0,1\}^{m+1}$, por lo que hay en la mayoría de las $2^{2^{m+1}}$ opciones para $S_{x,x}$. Dado que los conjuntos de $S_{x,x}$ deben ser distintos para distintas opciones de $x$, se deduce que el $2^{2^{m+1}} \geq 2^n$, lo $m \geq \log n - 1$.
