En la informática teórica , la complejidad de la comunicación estudia la cantidad de comunicación necesaria para resolver un problema cuando la entrada al problema se distribuye entre dos o más partes. El estudio de la complejidad de la comunicación fue introducido por primera vez por Andrew Yao en 1979, mientras estudiaba el problema de la computación distribuida entre varias máquinas. [1] El problema generalmente se expresa de la siguiente manera: dos partes (tradicionalmente llamadas Alice y Bob ) reciben cada una una (potencialmente diferente)- cadena de bits y . El objetivo es que Alice calcule el valor de una determinada función,, eso depende de ambos y , con la menor cantidad de comunicación entre ellos.
Mientras que Alice y Bob siempre pueden tener éxito si Bob envía todo su -bit cadena a Alice (quien luego calcula la función ), la idea aquí es encontrar formas inteligentes de calcular con menos de bits de comunicación. Tenga en cuenta que, a diferencia de la teoría de la complejidad computacional , la complejidad de la comunicación no se preocupa por la cantidad de cálculo realizado por Alice o Bob, o el tamaño de la memoria utilizada, ya que generalmente no asumimos nada sobre el poder computacional de Alice o Bob.
Este problema abstracto con dos partes (llamado complejidad de comunicación entre dos partes), y su forma general con más de dos partes , es relevante en muchos contextos. En el diseño de circuitos VLSI , por ejemplo, se busca minimizar la energía utilizada al disminuir la cantidad de señales eléctricas que pasan entre los diferentes componentes durante un cálculo distribuido. El problema también es relevante en el estudio de estructuras de datos y en la optimización de redes informáticas. Para un estudio del campo, consulte el libro de texto de Kushilevitz & Nisan (2006) .
Definicion formal
Dejar donde asumimos en el caso típico que y . Alice sostiene uncadena de bits mientras Bob sostiene un cadena de bits . Al comunicarse entre sí un bit a la vez (adoptando algún protocolo de comunicación que se acuerde de antemano), Alice y Bob desean calcular el valor dede modo que al menos una de las partes conozca el valor al final de la comunicación. En este punto, la respuesta se puede comunicar de nuevo para que, al costo de un bit extra, ambas partes conozcan la respuesta. La complejidad de la comunicación en el peor de los casos de este problema de comunicación de la informática, denotado como , se define entonces como
- número mínimo de bits intercambiados entre Alice y Bob en el peor de los casos.
Como se observó anteriormente, para cualquier función , tenemos . Usando la definición anterior, es útil pensar en la funcióncomo una matriz (llamada matriz de entrada o matriz de comunicación ) donde las filas están indexadas por y columnas por . Las entradas de la matriz son. Inicialmente, tanto Alice como Bob tienen una copia de la matriz completa. (asumiendo la función es conocido por ambas partes). Entonces, el problema de calcular el valor de la función puede reformularse como "poner a cero" en la entrada de la matriz correspondiente. Este problema se puede resolver si Alice o Bob conocen ambos y . Al inicio de la comunicación, el número de opciones para el valor de la función en las entradas es el tamaño de la matriz, es decir. Luego, a medida que cada parte se comunica un poco con la otra, el número de opciones para la respuesta se reduce, ya que esto elimina un conjunto de filas / columnas que da como resultado una submatriz de.
Más formalmente, un conjunto se llama un rectángulo (combinatorio) si siempre y luego . Equivalentemente, es un rectángulo combinatorio si se puede expresar como para algunos y . Considere el caso cuandolos bits ya se intercambian entre las partes. Ahora, para un, definamos una matriz
Luego, , y no es difícil demostrar que es un rectángulo combinatorio en .
Ejemplo:
Consideramos el caso en el que Alice y Bob intentan determinar si sus cadenas de entrada son iguales o no. Formalmente, defina la función de Igualdad , denotada, por si . Como demostramos a continuación, cualquier protocolo de comunicación determinista que resuelva requiere bits de comunicación en el peor de los casos. Como ejemplo de calentamiento, considere el caso simple de. La función de igualdad en este caso se puede representar mediante la matriz a continuación. Las filas representan todas las posibilidades de, las columnas las de .
Ecualizador | 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 |
Como puede ver, la función solo se evalúa como 1 cuando es igual a (es decir, en diagonal). También es bastante fácil ver cómo la comunicación de un solo bit divide sus posibilidades a la mitad. Si sabes que la primera parte de es 1, solo necesita considerar la mitad de las columnas (donde puede ser igual a 100, 101, 110 o 111).
Teorema:
Prueba. Asumir que. Esto significa que existe tal que y que tienen la misma transcripción de la comunicación . Dado que esta transcripción define un rectángulo, también debe ser 1. Por definición y sabemos que la igualdad solo es cierta para Cuándo . Esto produce una contradicción.
Esta técnica de probar los límites inferiores de la comunicación determinista se denomina técnica del juego del engaño . [2]
Complejidad de la comunicación aleatoria
En la definición anterior, nos preocupa la cantidad de bits que deben transmitirse de manera determinista entre dos partes. Si ambas partes tienen acceso a un generador de números aleatorios, ¿pueden determinar el valor decon mucha menos información intercambiada? Yao, en su artículo seminal [1] responde a esta pregunta definiendo la complejidad de la comunicación aleatoria.
Un protocolo aleatorio para una función tiene un error de dos caras.
Un protocolo aleatorio es un protocolo determinista que utiliza una cadena aleatoria adicional además de su entrada normal. Hay dos modelos para esto: una cadena pública es una cadena aleatoria que ambas partes conocen de antemano, mientras que una cadena privada es generada por una parte y debe comunicarse a la otra parte. Un teorema que se presenta a continuación muestra que cualquier protocolo de cadena público puede ser simulado por un protocolo de cadena privado que usa O (log n) bits adicionales en comparación con el original.
Tenga en cuenta que en las desigualdades de probabilidad anteriores, se entiende que el resultado del protocolo depende solo de la cadena aleatoria; tanto las cadenas x y y permanecen fijos. En otras palabras, si R (x, y) produce g (x, y, r) cuando se usa una cadena aleatoria r , entonces g (x, y, r) = f (x, y) para al menos 2/3 de todos opciones para la cadena r .
La complejidad aleatoria se define simplemente como el número de bits intercambiados en dicho protocolo.
Tenga en cuenta que también es posible definir un protocolo aleatorio con error unilateral y la complejidad se define de manera similar.
Ejemplo: EQ
Volviendo al ejemplo anterior de EQ , si no se requiere certeza, Alice y Bob pueden verificar la igualdad usando solomensajes. Considere el siguiente protocolo: suponga que Alice y Bob tienen acceso a la misma cadena aleatoria. Alice calculay envía este bit (llámelo b ) a Bob. (Laes el producto escalar en GF (2)) . Luego, Bob compara b con. Si son iguales, entonces Bob acepta, diciendo que x es igual a y . De lo contrario, lo rechaza.
Claramente, si , luego , entonces . Si x no es igual a y , es posible que, lo que le daría a Bob una respuesta incorrecta. ¿Como sucedió esto?
Si X y Y no son iguales, tienen que difieren en algunos lugares:
Donde x e y están de acuerdo,por lo que esos términos afectan a los productos punto por igual. Podemos ignorar esos términos y fijarse sólo en donde X y Y son distintos. Además, podemos intercambiar los bits y sin cambiar si los productos punto son iguales o no. Esto significa que podemos intercambiar bits para que x contenga solo ceros e y contenga solo unos:
Tenga en cuenta que y . Ahora, la pregunta es: para alguna cadena aleatoria, ¿cuál es la probabilidad de que ? Desde cada uno es igualmente probable que sea 0 o1 , esta probabilidad es solo. Por tanto, cuando x no es igual a y ,. El algoritmo se puede repetir muchas veces para aumentar su precisión. Esto se ajusta a los requisitos de un algoritmo de comunicación aleatorio.
Esto muestra que si Alice y Bob comparten una cadena aleatoria de longitud n , pueden enviarse un bit entre sí para calcular. En la siguiente sección, se muestra que Alice y Bob solo pueden intercambiarbits que son tan buenos como compartir una cadena aleatoria de longitud n . Una vez que se muestra, se deduce que EQ se puede calcular en mensajes.
Ejemplo: GH
Para otro ejemplo más de complejidad de comunicación aleatoria, recurrimos a un ejemplo conocido como el problema gap-Hamming (abreviado GH ). Formalmente, Alice y Bob mantienen mensajes binarios,y quisiera determinar si las cadenas son muy similares o si no son muy similares. En particular, les gustaría encontrar un protocolo de comunicación que requiera la transmisión de la menor cantidad de bits posible para calcular la siguiente función booleana parcial,
Claramente, deben comunicar todos sus bits si el protocolo va a ser determinista (esto se debe a que, si hay un subconjunto determinista y estricto de índices que Alice y Bob se transmiten entre sí, imagínese tener un par de cadenas en ese conjunto no estar de acuerdo en posiciones. Si se produce otro desacuerdo en cualquier posición que no se transmita, esto afectará el resultado de, y por lo tanto daría lugar a un procedimiento incorrecto.
Una pregunta natural que uno se hace entonces es, si se nos permite errar del tiempo (en instancias aleatorias extraído uniformemente al azar de ), entonces ¿podemos salirse con la nuestra con un protocolo con menos bits? Resulta que, sorprendentemente, la respuesta es no, debido a un resultado de Chakrabarti y Regev en 2012: muestran que para instancias aleatorias, cualquier procedimiento que sea correcto al menos del tiempo debe enviar bits de comunicación, es decir, esencialmente todos.
Monedas públicas versus monedas privadas
Es más fácil crear protocolos aleatorios cuando ambas partes tienen acceso a la misma cadena aleatoria (protocolo de cadena compartida). Todavía es posible utilizar estos protocolos incluso cuando las dos partes no comparten una cadena aleatoria (protocolo de cadena privada) con un pequeño costo de comunicación. Cualquier protocolo aleatorio de cadena compartida que utilice cualquier número de cadena aleatoria puede simularse mediante un protocolo de cadena privada que utilice bits O (log n) adicionales .
Intuitivamente, podemos encontrar algún conjunto de cadenas que tenga suficiente aleatoriedad para ejecutar el protocolo aleatorio con solo un pequeño aumento en el error. Este conjunto se puede compartir de antemano y, en lugar de dibujar una cadena aleatoria, Alice y Bob solo necesitan acordar qué cadena elegir del conjunto compartido. Este conjunto es lo suficientemente pequeño como para que la elección se pueda comunicar de manera eficiente. Sigue una prueba formal.
Considere algún protocolo aleatorio P con una tasa de error máxima de 0,1. Dejar ser cadenas de longitud n , numeradas. Dado tal, definir un nuevo protocolo que elige al azar algunos y luego ejecuta P usandocomo la cadena aleatoria compartida. Se necesitan O (log 100 n ) = O (log n ) bits para comunicar la elección de.
Definamos y ser las probabilidades de que y calcular el valor correcto para la entrada .
Por un fijo , podemos usar la desigualdad de Hoeffding para obtener la siguiente ecuación:
Por lo tanto, cuando no tenemos reparado:
La última igualdad anterior se cumple porque hay diferentes pares . Dado que la probabilidad no es igual a 1, hay algunos para que para todos :
Desde tiene como máximo 0.1 probabilidad de error, puede tener una probabilidad de error de 0,2 como máximo.
Complejidad de la comunicación cuántica
La complejidad de la comunicación cuántica intenta cuantificar la posible reducción de la comunicación mediante el uso de efectos cuánticos durante un cálculo distribuido.
Se han propuesto al menos tres generalizaciones cuánticas de la complejidad de la comunicación; para una encuesta, consulte el texto sugerido por G. Brassard.
El primero es el modelo de comunicación qubit , donde las partes pueden utilizar la comunicación cuántica en lugar de la comunicación clásica, por ejemplo, intercambiando fotones a través de una fibra óptica .
En un segundo modelo, la comunicación todavía se realiza con bits clásicos, pero las partes pueden manipular un suministro ilimitado de estados entrelazados cuánticos como parte de sus protocolos. Al realizar mediciones en sus estados entrelazados, las partes pueden ahorrar en la comunicación clásica durante un cálculo distribuido.
El tercer modelo implica el acceso a entrelazamientos previamente compartidos además de la comunicación qubit , y es el menos explorado de los tres modelos cuánticos.
Complejidad de la comunicación no determinista
En la complejidad de la comunicación no determinista, Alice y Bob tienen acceso a un oráculo. Después de recibir la palabra del oráculo, las partes se comunican para deducir. La complejidad de la comunicación no determinista es entonces la máxima de todos los pares sobre la suma del número de bits intercambiados y la longitud de codificación de la palabra de Oracle.
Visto de manera diferente, esto equivale a cubrir todas las entradas 1 de la matriz 0/1 mediante rectángulos combinatorios 1 (es decir, submatrices no contiguas, no convexas, cuyas entradas son todas una (ver Kushilevitz y Nisan o Dietzfelbinger et al. )). La complejidad de la comunicación no determinista es el logaritmo binario del rectángulo que cubre el número de la matriz: el número mínimo de 1-rectángulos combinatorios necesarios para cubrir todas las entradas 1 de la matriz, sin cubrir ninguna entrada 0.
La complejidad de la comunicación no determinista ocurre como un medio para obtener límites inferiores para la complejidad de la comunicación determinista (ver Dietzfelbinger et al.), Pero también en la teoría de matrices no negativas, donde da un límite inferior en el rango no negativo de una matriz no negativa. [3]
Complejidad de comunicación de errores ilimitados
En la configuración de error ilimitado, Alice y Bob tienen acceso a una moneda privada y sus propias entradas . En este escenario, Alice tiene éxito si responde con el valor correcto decon probabilidad estrictamente mayor que 1/2. En otras palabras, si las respuestas de Alice tienen alguna correlación distinta de cero con el valor verdadero de, entonces el protocolo se considera válido.
Tenga en cuenta que el requisito de que la moneda sea privada es esencial. En particular, si el número de bits públicos compartidos entre Alice y Bob no se contabilizan en contra de la complejidad de la comunicación, es fácil argumentar que calcular cualquier función tienecomplejidad de la comunicación. [4] Por otro lado, ambos modelos son equivalentes si el número de bits públicos utilizados por Alice y Bob se cuenta contra la comunicación total del protocolo. [5]
Aunque los límites inferiores de este modelo son sutiles, son extremadamente fuertes. Más específicamente, está claro que cualquier límite en los problemas de esta clase implica inmediatamente límites equivalentes en los problemas en el modelo determinista y los modelos de monedas público y privado, pero tales límites también son válidos inmediatamente para los modelos de comunicación no determinista y los modelos de comunicación cuántica. [6]
Forster [7] fue el primero en probar límites inferiores explícitos para esta clase, mostrando que calcular el producto interno Requiere al menos bits de comunicación, aunque un resultado anterior de Alon, Frankl y Rödl demostró que la complejidad de la comunicación para casi todas las funciones booleanas es . [8]
Problemas abiertos
Considerando una matriz de entrada de 0 o 1 , el número mínimo de bits intercambiados para calcular determinísticamente en el peor de los casos, , se sabe que está acotado desde abajo por el logaritmo del rango de la matriz. La conjetura del rango logarítmico propone que la complejidad de la comunicación,, está acotado desde arriba por una potencia constante del logaritmo del rango de . Dado que D (f) está acotado desde arriba y desde abajo por polinomios de rango logarítmico, podemos decir que D (f) está polinomialmente relacionado con el rango logarítmico. Dado que el rango de una matriz es un tiempo polinomial calculable en el tamaño de la matriz, tal límite superior permitiría aproximar la complejidad de comunicación de la matriz en tiempo polinomial. Sin embargo, tenga en cuenta que el tamaño de la matriz en sí es exponencial en el tamaño de la entrada.
Para un protocolo aleatorizado, se conjetura que el número de bits intercambiados en el peor de los casos, R (f), está relacionado polinomialmente con la siguiente fórmula:
Tales conjeturas de rangos logarítmicos son valiosas porque reducen la cuestión de la complejidad de la comunicación de una matriz a una cuestión de filas (columnas) linealmente independientes de la matriz. Esto revela que la esencia del problema de la complejidad de la comunicación, por ejemplo, en el caso de EQ anterior, es averiguar en qué parte de la matriz están las entradas, para saber si son equivalentes.
Aplicaciones
Los límites inferiores en la complejidad de la comunicación se pueden utilizar para probar los límites inferiores en la complejidad del árbol de decisión , circuitos VLSI , estructuras de datos, algoritmos de transmisión , compensaciones de espacio-tiempo para máquinas de Turing y más. [2]
Ver también
Notas
- ^ a b Yao, AC (1979), "Algunas preguntas de complejidad relacionadas con la informática distribuida", Proc. Del 11º STOC , 14 : 209–213
- ^ a b Kushilevitz, Eyal; Nisan, Noam (1997). Complejidad de la comunicación . Prensa de la Universidad de Cambridge. ISBN 978-0-521-56067-2.
- ^ Yannakakis, M. (1991). "Expresando problemas de optimización combinatoria mediante programas lineales" . J. Comput. Syst. Sci . 43 (3): 441–466. doi : 10.1016 / 0022-0000 (91) 90024-y .
- ^ Lovett, Shachar, CSE 291: Communication Complexity, Winter 2019 Unbounded-error Protocols (PDF) , consultado el 9 de junio de 2019
- ^ Göös, Mika; Pitassi, Toniann; Watson, Thomas (1 de junio de 2018). "El panorama de las clases de complejidad de la comunicación" . Complejidad computacional . 27 (2): 245-304. doi : 10.1007 / s00037-018-0166-6 . ISSN 1420-8954 . S2CID 4333231 .
- ^ Sherstov, Alexander A. (octubre de 2008). "La complejidad de comunicación de errores ilimitados de funciones simétricas". 2008 49º Simposio anual del IEEE sobre fundamentos de la informática : 384–393. doi : 10.1109 / focs.2008.20 . ISBN 978-0-7695-3436-7. S2CID 9072527 .
- ^ Forster, Jürgen (2002). "Un límite inferior lineal en la complejidad de la comunicación probabilística de error ilimitado" . Revista de Ciencias de la Computación y Sistemas . 65 (4): 612–625. doi : 10.1016 / S0022-0000 (02) 00019-3 .
- ^ Alon, N .; Frankl, P .; Rodl, V. (octubre de 1985). "Realización geométrica de sistemas de conjuntos y complejidad comunicativa probabilística". 26º Simposio Anual sobre Fundamentos de las Ciencias de la Computación (SFCS 1985) . Portland, Oregón, EE. UU .: IEEE: 277–280. CiteSeerX 10.1.1.300.9711 . doi : 10.1109 / SFCS.1985.30 . ISBN 9780818606441. S2CID 8416636 .
Referencias
- Kushilevitz, Eyal; Nisan, Noam (2006). Complejidad de la comunicación . Cambridge: Cambridge University Press. ISBN 978-0-521-02983-4. OCLC 70764786 .
- Brassard, G. Complejidad de la comunicación cuántica: una encuesta. https://arxiv.org/abs/quant-ph/0101005
- Dietzfelbinger, M., J. Hromkovic, J. y G. Schnitger, " Una comparación de dos métodos de límite inferior para la complejidad de la comunicación ", Theoret. Computación. Sci. 168, 1996. 39-51.
- Raz, Ran . "Complejidad de circuitos y comunicaciones". En teoría de la complejidad computacional. Steven Rudich y Avi Wigderson, eds. Instituto de Estudios Avanzados de la Sociedad Americana de Matemáticas, 2004. 129-137.
- AC Yao, "Algunas cuestiones de complejidad relacionadas con la informática distribuida", Proc. of 11th STOC, págs. 209–213, 1979. 14
- I. Newman, Bits aleatorios privados versus comunes en la complejidad de la comunicación , Information Processing Letters 39, 1991, págs. 67-71.