Complejidad de la comunicación

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 30 de diciembre de 2019; la verificación requiere 1 edición .

En informática teórica , la complejidad de la comunicación estudia la cantidad de comunicación requerida para resolver un problema cuyos parámetros son compartidos entre dos o más partes. Esta noción fue introducida por Andrew Yao en 1979 [1] , quien estaba investigando el siguiente problema para dos participantes, tradicionalmente llamados Alice y Bob . Alice recibe una cadena x de n bits y Bob una cadena y de n bits , y su objetivo es que uno de ellos (por ejemplo, Bob) calcule una función definida y conocida por ambas partes , con la menor cantidad de comunicación entre ellos. . Por supuesto, siempre pueden calcular así: Alice envía su cadena completa de n bits a Bob, quien luego evalúa la función . Por lo tanto, en esta formulación del problema, es interesante para qué funciones f hay una forma de calcular transmitiendo menos de n bits. Es importante notar que en este problema no estamos interesados en la complejidad de los cálculos realizados por Alice o Bob, o el tamaño de la memoria utilizada para estos cálculos. $f(x,y)$ $f(x,y)$ $f(x,y)$ $f(x,y)$

Este problema abstracto de dos participantes (llamado complejidad de la comunicación de dos participantes) y su forma general con muchos participantes surge en varias áreas de la informática: por ejemplo, en el diseño de grandes circuitos integrados , la necesidad de minimizar la energía utilizada reduciendo la número de señales eléctricas entre diferentes componentes durante la computación distribuida. La complejidad de la comunicación también se utiliza en el estudio de estructuras de datos y algoritmos, en la optimización de redes informáticas, en la teoría de la complejidad computacional y la complejidad de la prueba, y en otras áreas.

Formal definición

Deje que se dé inicialmente alguna función , donde en la declaración más típica . Alice recibe , Bob recibe . Intercambiando mensajes entre ellos bit por bit (usando algún protocolo de comunicación predeterminado ), Alice y Bob quieren calcular el valor para que al final de la comunicación al menos uno de ellos sepa el valor . $f:X\times Y\to Z$ $X=Y=\{0,1\}^{n},Z=\{0,1\}$ $x\en X$ $y\en y$ $z=f(x,y)$ $z$

La complejidad de comunicación para calcular la función $F$ , denotada por , se define como el número mínimo de bits de comunicación que es suficiente para resolver el problema en el peor de los casos (es decir, este número de bits debería ser suficiente para cualquier par de ). $D(f)$ $x,y$

Con base en esta definición, es conveniente pensar en la función f como una función dada por la matriz A , en la que las filas están indexadas por elementos , y las columnas, respectivamente, por elementos . En cada celda de esta matriz, indexada por los elementos x e y , se escribe el valor correspondiente de f , es decir, . Alice y Bob conocen la función f y, por lo tanto , conocen la matriz A. A continuación, a Alice se le da el número de fila x y a Bob el número de columna y , y su tarea es determinar el valor escrito en la celda correspondiente. Por lo tanto, si en algún momento uno de los jugadores conoce el número de columna y el número de línea al mismo tiempo, también sabrá el valor en la celda correspondiente. Al comienzo de la comunicación, cada jugador no sabe nada sobre el número del otro jugador, por lo que, desde el punto de vista de Alice, la respuesta puede ser cualquier valor en la fila x , y desde el punto de vista de Bob, cualquier valor en la columna y . . En el proceso de comunicación con cada bit transmitido, aparece nueva información que permite a los jugadores cortar algunas de las posibles celdas. Por ejemplo, si en algún momento Alice transmite el bit b , desde el punto de vista de Bob, todas las entradas posibles de Alice en ese momento se dividen en dos conjuntos: aquellas para las que Alice enviaría y aquellas para las que Alice enviaría . Conociendo el valor del bit b , Bob corta algunas de las posibles entradas de Alice y, por lo tanto, reduce el conjunto de celdas posibles desde su punto de vista. En este caso, desde el punto de vista de un observador externo, después de cada mensaje, el conjunto de filas posibles o el conjunto de columnas posibles se reduce y, por lo tanto, el conjunto de celdas posibles se reduce por alguna submatriz de la matriz A. $x\en X$ $y\en y$ $A_{\mathrm {x,y} }=f(x,y)$ $b=0$ $b=1$

Más formalmente, llamaremos a un conjunto rectángulo (combinatorio) si se sigue del hecho de que y . Entonces cada submatriz de la matriz A está asociada con un rectángulo combinatorio R tal que , donde y . Ahora considere la situación cuando ya se han transferido k bits entre los participantes. Deje que estos primeros k bits sean dados por la cadena . Entonces es posible definir un conjunto de pares de entradas en las que las primeras k son iguales $R\subseteq X\times Y$ ${\ estilo de visualización (x_ {1}, y_ {1}) \ en R}$ ${\ estilo de visualización (x_ {2}, y_ {2}) \ en R}$ ${\ estilo de visualización (x_ {1}, y_ {2}) \ en R}$ ${\ estilo de visualización (x_ {2}, y_ {1}) \ en R}$ $R=M\veces N$ $M\subconjunto X$ $N\subseteq Y$ ${\displaystyle h\en \{0,1\}^{k))$ $T_{\mathrm {h} }\subseteq X\times Y$ $h$

T_{\mathrm {h} }=\{(x,y):k

- el bit de comunicación en las entradas es igual a

{\ estilo de visualización (x, y)}

{\ estilo de visualización h \}}

Entonces es un rectángulo combinatorio, es decir, define una submatriz de la matriz A. ${\displaystyle T_{\mathrm {h} ))$

Ejemplo: función EQ

deja _ Considere un problema en el que Alice y Bob quieren determinar si se les dan las mismas cadenas, es decir, quieren verificar eso . Es fácil mostrar que para resolver este problema de prueba de igualdad (EQ) , necesitamos transmitir n bits en el peor de los casos, si queremos poder responder esta pregunta exactamente para todos los pares posibles de x e y . $X=Y=\{0,1\}^{n},Z=\{0,1\}$ $x=y$

Para el caso, las cadenas x e y constan de tres bits. La función de igualdad en este caso está definida por la siguiente matriz, donde las filas están indexadas por las entradas de Alice y las filas están indexadas por las entradas de Bob. $n=3$

ecualizador	000	001	010	011	100	101	110	111
000	una	0	0	0	0	0	0	0
001	0	una	0	0	0	0	0	0
010	0	0	una	0	0	0	0	0
011	0	0	0	una	0	0	0	0
100	0	0	0	0	una	0	0	0
101	0	0	0	0	0	una	0	0
110	0	0	0	0	0	0	una	0
111	0	0	0	0	0	0	0	una

Como podemos ver, la función es igual a 1 solo en las celdas donde x es igual a y (es decir, en la diagonal). ${\ ecualizador de estilo de pantalla}$

Teorema: ${\ Displaystyle D (EQ) = n}$

Prueba. Supongamos que , es decir, existe un protocolo que resuelve el problema de verificar la igualdad para todos los pares de cadenas de bits de longitud n , mientras transmite no más de un bit. Escribamos en una línea todos los bits que se enviaron en el protocolo para cada posible par de cadenas idénticas (para ellos ). Hay exactamente tales pares distintos , y hay a lo sumo cadenas de bits distintas de longitud . Según el principio de Dirichlet , existen dos pares y , para los cuales se obtienen las mismas cadenas, es decir, se enviaron los mismos bits en el protocolo. Dado que el conjunto de pares de cadenas para las que se enviaron los mismos bits define un rectángulo, entonces y también debe ser igual a 1, lo que contradice el hecho de que . Por lo tanto, nuestra suposición es incorrecta, lo que significa que ${\ estilo de visualización D (EQ) \ leq n-1}$ $n-1$ ${\ estilo de visualización (x, x)}$ $EQ(x,x)=1$ ${\ estilo de visualización (x, x)}$ $2^{n}$ $n-1$ ${\displaystyle 2+4+\dotsb +2^{n-1}=2^{n}-2<2^{n))$ ${\ estilo de visualización (x, x)}$ ${\ estilo de visualización (x', x')}$ $EQ(x,x')$ $EQ(x',x)$ $x\neq x'$ ${\ estilo de visualización D (EQ)> n-1}$

En otras palabras, si es menor que n , entonces deberíamos poder cubrir todos los de la matriz EQ con menos rectángulos de un color (todas las celdas están marcadas con unos). Sin embargo, hay exactamente unos en la matriz EQ , y dos no pueden estar en el mismo rectángulo de un solo color, ya que las celdas marcadas con ceros inevitablemente caerán en este rectángulo. Por lo tanto, dicha cobertura no existe y, por lo tanto, al menos n . ${\ estilo de visualización D (EQ)}$ $2^{n}$ $2^{n}$ ${\ estilo de visualización D (EQ)}$

Notas

↑ Yao, AC (1979), Algunas preguntas complejas relacionadas con la computación distribuida, Proc. del 11.° STOC vol.14 : 209–213

Literatura

Kushilevitz, Eyal; Nissan, NoamComplejidad de la comunicación (indefinida) . -Cambridge: Cambridge University Press , 2006. -ISBN 978-0-521-02983-4 .
Razborov A.A. Complejidad de la comunicación . - MTSNMO, 2012. - 24 págs. — ISBN 978-5-4439-0202-9 .
Vereshchagin N.K., Shchepin E.V. Información, codificación y predicción. - M. : FMOP, MTsNMO, 2012. - 238 p. - ISBN 978-5-94057-920-5 .

ecualizador	000	001	010	011	100	101	110	111
000	una	0	0	0	0	0	0	0
001	0	una	0	0	0	0	0	0
010	0	0	una	0	0	0	0	0
011	0	0	0	una	0	0	0	0
100	0	0	0	0	una	0	0	0
101	0	0	0	0	0	una	0	0
110	0	0	0	0	0	0	una	0
111	0	0	0	0	0	0	0	una

ecualizador	000	001	010	011	100	101	110	111
000	una	0	0	0	0	0	0	0
001	0	una	0	0	0	0	0	0
010	0	0	una	0	0	0	0	0
011	0	0	0	una	0	0	0	0
100	0	0	0	0	una	0	0	0
101	0	0	0	0	0	una	0	0
110	0	0	0	0	0	0	una	0
111	0	0	0	0	0	0	0	una

ecualizador	000	001	010	011	100	101	110	111
000	una	0	0	0	0	0	0	0
001	0	una	0	0	0	0	0	0
010	0	0	una	0	0	0	0	0
011	0	0	0	una	0	0	0	0
100	0	0	0	0	una	0	0	0
101	0	0	0	0	0	una	0	0
110	0	0	0	0	0	0	una	0
111	0	0	0	0	0	0	0	una