Complejidad de la comunicación

Complejidad del envío de información en un algoritmo distribuido.

En informática teórica , la complejidad de la comunicación estudia la cantidad de comunicación requerida 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 plantea de la siguiente manera: dos partes (tradicionalmente llamadas Alice y Bob ) reciben cada una una cadena de bits ( potencialmente diferente) y . El objetivo es que Alice calcule el valor de una determinada función, que depende de ambos y , con la menor cantidad de comunicación entre ellos. ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle f(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$

Si bien Alice y Bob siempre pueden tener éxito haciendo que Bob envíe su cadena de bits completa 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 tiene que ver con 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. ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle n}$

Este problema abstracto con dos partes (llamado complejidad de la comunicación bipartita), 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 disminuyendo 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 estudios de campo, consulte los libros de texto de Rao y Yehudayoff (2020) y Kushilevitz y Nisan (2006).

Definicion formal

Sea donde asumimos en el caso típico que y . Alice tiene una cadena de bits mientras que Bob tiene una cadena de bits . Al comunicarse entre sí bit a bit (adoptando algún protocolo de comunicación acordado de antemano), Alice y Bob desean calcular el valor de tal 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, a costa de un bit adicional, ambas partes sepan la respuesta. El peor caso de complejidad de comunicación de este problema de comunicación de la informática , denotado como , se define entonces como ${\displaystyle f:X\times Y\rightarrow Z}$ ${\displaystyle X=Y=\{0,1\}^{n}}$ ${\displaystyle Z=\{0,1\}}$ ${\displaystyle n}$ ${\displaystyle x\in X}$ ${\displaystyle n}$ ${\displaystyle y\in Y}$ ${\displaystyle f(x,y)}$ ${\displaystyle f}$ ${\displaystyle D(f)}$

${\displaystyle D(f)=}$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ón como una matriz (llamada matriz de entrada o matriz de comunicación ) donde las filas están indexadas por y las columnas por . Las entradas de la matriz son . Inicialmente, tanto Alice como Bob tienen una copia de la matriz completa (suponiendo que ambas partes conocen la función). Entonces, el problema de calcular el valor de la función se puede reformular 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 dan como resultado una submatriz de . ${\displaystyle f:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}}$ ${\displaystyle D(f)\leq n}$ ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle x\in X}$ ${\displaystyle y\in Y}$ ${\displaystyle A_{x,y}=f(x,y)}$ ${\displaystyle A}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle 2^{2n}}$ ${\displaystyle A}$

Más formalmente, un conjunto se llama rectángulo (combinatorio) si siempre y entonces . De manera equivalente, es un rectángulo combinatorio si se puede expresar como para algunos y . Consideremos el caso en el que las partes ya han intercambiado bits. Ahora, para un particular , definamos una matriz. ${\displaystyle R\subseteq X\times Y}$ ${\displaystyle (x_{1},y_{1})\in R}$ ${\displaystyle (x_{2},y_{2})\in R}$ ${\displaystyle (x_{1},y_{2})\in R}$ ${\displaystyle R}$ ${\displaystyle R=M\times N}$ ${\displaystyle M\subseteq X}$ ${\displaystyle N\subseteq Y}$ ${\displaystyle k}$ ${\displaystyle h\in \{0,1\}^{k}}$

${\displaystyle T_{h}=\{(x,y):{\text{ the }}k{\text{-bits exchanged on input }}(x,y){\text{ is }}h\}}$

Entonces, , y no es difícil demostrar que es un rectángulo combinatorio en . ${\displaystyle T_{h}\subseteq X\times Y}$ ${\displaystyle T_{h}}$ ${\displaystyle A}$

Ejemplo: ecualizador

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 Igualdad , denotada por if . Como demostramos a continuación, cualquier resolución determinista de un protocolo de comunicación 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 siguiente matriz. Las filas representan todas las posibilidades de , las columnas las de . ${\displaystyle EQ:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}}$ ${\displaystyle EQ(x,y)=1}$ ${\displaystyle x=y}$ ${\displaystyle EQ}$ ${\displaystyle n}$ ${\displaystyle x,y\in \{0,1\}^{3}}$ ${\displaystyle x}$ ${\displaystyle y}$

En esta tabla, la función sólo se evalúa como 1 cuando es igual (es decir, en la diagonal). También es bastante fácil ver cómo comunicar un solo bit divide las posibilidades de alguien a la mitad. Cuando el primer bit es 1, considere solo la mitad de las columnas (donde puede ser igual a 100, 101, 110 o 111). ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle y}$

Teorema: D(EQ) = n

Prueba. Asumir que . Esto significa que existe tal que y tienen la misma transcripción de comunicación . Dado que esta transcripción define un rectángulo, también debe ser 1. Por definición , sabemos que la igualdad solo es verdadera cuando . Esto produce una contradicción. ${\displaystyle D(EQ)\leq n-1}$ ${\displaystyle x\neq x'}$ ${\displaystyle (x,x)}$ ${\displaystyle (x',x')}$ ${\displaystyle h}$ ${\displaystyle f(x,x')}$ ${\displaystyle x\neq x'}$ ${\displaystyle (a,b)}$ ${\displaystyle a=b}$

Esta técnica de demostrar los límites inferiores de la comunicación determinista se denomina técnica del conjunto de 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 de con mucha menos información intercambiada? Yao, en su artículo fundamental ^[1] responde a esta pregunta definiendo la complejidad de la comunicación aleatoria. ${\displaystyle f}$

Un protocolo aleatorio para una función tiene un error bilateral. ${\displaystyle R}$ ${\displaystyle f}$

${\displaystyle \Pr[R(x,y)=0]>{\frac {2}{3}},{\textrm {if}}\,f(x,y)=0}$

${\displaystyle \Pr[R(x,y)=1]>{\frac {2}{3}},{\textrm {if}}\,f(x,y)=1}$

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 de las partes y debe comunicarse a la otra parte. Un teorema que se presenta a continuación muestra que cualquier protocolo de cadena pública puede simularse mediante un protocolo de cadena privada que utiliza 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 únicamente de la cadena aleatoria; ambas cadenas xey permanecen fijas . 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: ecualizador

Volviendo al ejemplo anterior de EQ , si no se requiere certeza, Alice y Bob pueden verificar la igualdad usando solo mensajes. Considere el siguiente protocolo: suponga que Alice y Bob tienen acceso a la misma cadena aleatoria . Alice calcula y envía este bit (llámelo b ) a Bob. (El es el producto escalar en GF(2) .) Luego Bob compara b con . Si son iguales, entonces Bob acepta y dice que x es igual a y . En caso contrario, lo rechaza. ${\displaystyle O(\log n)}$ ${\displaystyle z\in \{0,1\}^{n}}$ ${\displaystyle z\cdot x}$ ${\displaystyle (\cdot )}$ ${\displaystyle z\cdot y}$

Claramente, si , entonces , entonces . Si x no es igual a y , aún es posible que , lo que le daría a Bob la respuesta incorrecta. ¿Como sucedió esto? ${\displaystyle x=y}$ ${\displaystyle z\cdot x=z\cdot y}$ ${\displaystyle Prob_{z}[Accept]=1}$ ${\displaystyle z\cdot x=z\cdot y}$

Si x e y no son iguales, deben diferir en algunas ubicaciones:

${\displaystyle {\begin{cases}x=c_{1}c_{2}\ldots p\ldots p'\ldots x_{n}\\y=c_{1}c_{2}\ldots q\ldots q'\ldots y_{n}\\z=z_{1}z_{2}\ldots z_{i}\ldots z_{j}\ldots z_{n}\end{cases}}}$

Cuando x e y concuerdan, esos términos afectan por igual a los productos escalares. Podemos ignorar con seguridad esos términos y observar sólo dónde difieren x e y . Además, podemos intercambiar los bits y sin cambiar si los productos escalares son iguales o no. Esto significa que podemos intercambiar bits para que x contenga solo ceros y y contenga solo unos: ${\displaystyle z_{i}*x_{i}=z_{i}*c_{i}=z_{i}*y_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle y_{i}}$

${\displaystyle {\begin{cases}x'=00\ldots 0\\y'=11\ldots 1\\z'=z_{1}z_{2}\ldots z_{n'}\end{cases}}}$

Tenga en cuenta que y . Ahora, la pregunta es: para alguna cadena aleatoria , ¿cuál es la probabilidad de que ? Dado que cada uno tiene la misma probabilidad de ser ${\displaystyle z'\cdot x'=0}$ ${\displaystyle z'\cdot y'=\Sigma _{i}z'_{i}}$ ${\displaystyle z'}$ ${\displaystyle \Sigma _{i}z'_{i}=0}$ ${\displaystyle z'_{i}}$0 o1 , esta probabilidad es justa . Por lo 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. ${\displaystyle 1/2}$ ${\displaystyle Prob_{z}[Accept]=1/2}$

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 sólo pueden intercambiar bits que sean tan buenos como compartir una cadena aleatoria de longitud n . Una vez que se muestra esto, se deduce que el EQ se puede calcular en mensajes. ${\displaystyle EQ(x,y)}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$

Ejemplo: GH

Para ver otro ejemplo más de complejidad de la comunicación aleatoria, recurrimos a un ejemplo conocido como problema de brecha-Hamming (abreviado GH ). Formalmente, Alice y Bob mantienen mensajes binarios y les gustaría determinar si las cadenas son muy similares o no. 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, ${\displaystyle x,y\in \{-1,+1\}^{n}}$

${\displaystyle {\text{GH}}_{n}(x,y):={\begin{cases}-1&\langle x,y\rangle \leq {\sqrt {n}}\\+1&\langle x,y\rangle \geq {\sqrt {n}}.\end{cases}}}$

Claramente, deben comunicar todos sus bits para que el protocolo sea determinista (esto se debe a que, si hay un subconjunto estricto y determinista de índices que Alice y Bob se transmiten entre sí, entonces imagina tener un par de cadenas que en ese conjunto desacuerdo en las posiciones. Si ocurre otro desacuerdo en cualquier posición que no se transmita, esto afectará el resultado de y, por lo tanto, resultaría en un procedimiento incorrecto. ${\displaystyle {\sqrt {n}}-1}$ ${\displaystyle {\text{GH}}_{n}(x,y)}$

Una pregunta natural que uno se hace entonces es: si se nos permite equivocarnos en el tiempo (en instancias aleatorias extraídas uniformemente al azar de ), ¿podemos salirnos con la nuestra con un protocolo con menos bits? Resulta que la respuesta, sorprendentemente, es no, debido a un resultado de Chakrabarti y Regev en 2012: muestran que, para casos aleatorios, cualquier procedimiento que sea correcto al menos la mayor parte del tiempo debe enviar bits de comunicación, es decir esencialmente todos ellos. ${\displaystyle 1/3}$ ${\displaystyle x,y}$ ${\displaystyle \{-1,+1\}^{n}}$ ${\displaystyle 2/3}$ ${\displaystyle \Omega (n)}$

Monedas públicas versus monedas privadas

La creación de protocolos aleatorios se vuelve más fácil cuando ambas partes tienen acceso a la misma cadena aleatoria, lo que se conoce como protocolo de cadena compartida. Sin embargo, incluso en los casos en los que las dos partes no comparten una cadena aleatoria, aún es posible utilizar protocolos de cadena privados con sólo un pequeño costo de comunicación. Cualquier protocolo aleatorio de cadena compartida que utilice cualquier número de cadenas aleatorias puede simularse mediante un protocolo de cadena privado que utilice O (log n) bits adicionales.

Intuitivamente, podemos encontrar algún conjunto de cadenas que tengan 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 ponerse de acuerdo sobre qué cadena elegir del conjunto compartido. Este conjunto es lo suficientemente pequeño como para que la elección pueda comunicarse de manera eficiente. Sigue una prueba formal.

Considere algún protocolo aleatorio P con una tasa de error máxima de 0,1. Sean cadenas de longitud n , numeradas . Dado tal , defina un nuevo protocolo que seleccione algunos aleatoriamente y luego ejecute P usando como cadena aleatoria compartida. Se necesitan O (log 100 n ) = O (log  n ) bits para comunicar la elección de . ${\displaystyle R}$ ${\displaystyle 100n}$ ${\displaystyle r_{1},r_{2},\dots ,r_{100n}}$ ${\displaystyle R}$ ${\displaystyle P'_{R}}$ ${\displaystyle r_{i}}$ ${\displaystyle r_{i}}$ ${\displaystyle r_{i}}$

Definamos y como las probabilidades de que y calculemos el valor correcto para la entrada . ${\displaystyle p(x,y)}$ ${\displaystyle p'_{R}(x,y)}$ ${\displaystyle P}$ ${\displaystyle P'_{R}}$ ${\displaystyle (x,y)}$

Para una fija , podemos usar la desigualdad de Hoeffding para obtener la siguiente ecuación: ${\displaystyle (x,y)}$

${\displaystyle \Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq 2\exp(-2(0.1)^{2}\cdot 100n)<2^{-2n}}$

Así cuando no tenemos arreglado: ${\displaystyle (x,y)}$

${\displaystyle \Pr _{R}[\exists (x,y):\ |p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq \sum _{(x,y)}\Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]<\sum _{(x,y)}2^{-2n}=1}$

La última igualdad anterior se cumple porque hay pares diferentes . Como la probabilidad no es igual a 1, hay alguna de modo que para todos : ${\displaystyle 2^{2n}}$ ${\displaystyle (x,y)}$ ${\displaystyle R_{0}}$ ${\displaystyle (x,y)}$

${\displaystyle |p'_{R_{0}}(x,y)-p(x,y)|<0.1}$

Dado que tiene como máximo una probabilidad de error de 0,1, puede tener como máximo una probabilidad de error de 0,2. ${\displaystyle P}$ ${\displaystyle P'_{R_{0}}}$

Colapso de la complejidad de la comunicación aleatoria

Digamos que además permitimos que Alice y Bob compartan algún recurso, por ejemplo un par de partículas entrelazadas. Utilizando ese recurso, Alice y Bob pueden correlacionar su información y así intentar "colapsar" (o "trivializar") la complejidad de la comunicación en el siguiente sentido.

Definición. Se dice que un recurso está ${\displaystyle R}$ "colapsando" si, al utilizar ese recurso , sólo un bit de comunicación clásica es suficiente para que Alice conozca la evaluación en el peor de los casos para cualquier función booleana . ${\displaystyle R}$ ${\displaystyle f(x,y)}$ ${\displaystyle f}$

El hecho sorprendente de un colapso de la complejidad de la comunicación es que la función puede tener un tamaño de entrada arbitrariamente grande, pero aún así el número de bits de comunicación es constante a uno solo. ${\displaystyle f}$

Se ha demostrado que algunos recursos no colapsan, como las correlaciones cuánticas ^[3] o, más generalmente, las correlaciones casi cuánticas, ^[4] mientras que, por el contrario, se muestra que otros recursos colapsan la complejidad de la comunicación aleatoria, como la caja PR, ^[5] o algunas cajas PR ruidosas que cumplen algunas condiciones. ^{[6] [7] [8]}

Complejidad distributiva

Un enfoque para estudiar la complejidad de la comunicación aleatoria es a través de la complejidad distributiva.

Dada una distribución conjunta de las entradas de ambos jugadores, la complejidad distributiva correspondiente de una función es el costo mínimo de un protocolo determinista tal que , donde las entradas se muestrean de acuerdo con . ${\displaystyle \mu }$ ${\displaystyle f}$ ${\displaystyle R}$ ${\displaystyle \Pr[f(x,y)=R(x,y)]\geq 2/3}$ ${\displaystyle \mu }$

El principio minimax de Yao ^[9] (un caso especial del teorema minimax de von Neumann ) establece que la complejidad de comunicación aleatoria de una función es igual a su complejidad distributiva máxima, donde el máximo se toma sobre todas las distribuciones conjuntas de las entradas (no necesariamente distribuciones de productos). !).

El principio de Yao se puede utilizar para demostrar límites inferiores a la complejidad de la comunicación aleatoria de una función: diseñar la distribución conjunta adecuada y demostrar un límite inferior a la complejidad distributiva. Dado que la complejidad distributiva afecta a protocolos deterministas, esto podría ser más fácil que demostrar directamente un límite inferior en protocolos aleatorios.

Como ejemplo, consideremos la función disjunta DISJ: cada una de las entradas se interpreta como un subconjunto de y DISJ( x , y )=1 si los dos conjuntos son disjuntos. Razborov ^[10] demostró un límite inferior en la complejidad de la comunicación aleatoria al considerar la siguiente distribución: con probabilidad 3/4, muestree dos conjuntos aleatorios disjuntos de tamaño , y con probabilidad 1/4, muestree dos conjuntos aleatorios de tamaño con una intersección única . ${\displaystyle \{1,\dots ,n\}}$ ${\displaystyle \Omega (n)}$ ${\displaystyle n/4}$ ${\displaystyle n/4}$

Complejidad de la información

Un enfoque poderoso para el estudio de la complejidad distributiva es la complejidad de la información. Iniciado por Bar-Yossef, Jayram, Kumar y Sivakumar, ^[11] el enfoque fue codificado en el trabajo de Barak, Braverman, Chen y Rao ^[12] y por Braverman y Rao. ^[13]

La complejidad de la información (interna) de un protocolo R (posiblemente aleatorio) con respecto a una distribución μ se define de la siguiente manera. Sean entradas aleatorias muestreadas de acuerdo con μ , y sea Π la transcripción de R cuando se ejecuta en las entradas . La complejidad de la información del protocolo es ${\displaystyle (X,Y)\sim \mu }$ ${\displaystyle X,Y}$

${\displaystyle \operatorname {IC} _{\mu }(R)=I(\Pi ;Y|X)+I(\Pi ;X|Y),}$

donde I denota información mutua condicional . El primer sumando mide la cantidad de información que Alice aprende sobre los aportes de Bob a partir de la transcripción, y el segundo mide la cantidad de información que Bob aprende sobre los aportes de Alice.

La complejidad de la información del error ε de una función f con respecto a una distribución μ es la complejidad de la información mínima de un protocolo para f cuyo error (con respecto a μ ) es como máximo ε .

Braverman y Rao demostraron que información es igual a comunicación amortizada. Esto significa que el costo de resolver n copias independientes de f es aproximadamente n veces la complejidad de la información de f . Esto es análogo a la conocida interpretación de la entropía de Shannon como la longitud de bits amortizada necesaria para transmitir datos desde una fuente de información determinada. La prueba de Braverman y Rao utiliza una técnica conocida como "compresión de protocolo", en la que un protocolo eficiente en información se "comprime" en un protocolo eficiente en comunicación.

Las técnicas de complejidad de la información permiten calcular la complejidad de comunicación exacta (hasta el primer orden) de la disjunción de un conjunto . ^[14] ${\displaystyle 1.4923\ldots n}$

Las técnicas de complejidad de la información también se han utilizado para analizar formulaciones extendidas, lo que demuestra un límite inferior esencialmente óptimo para la complejidad de los algoritmos basados ​​en programación lineal que resuelven aproximadamente el problema de camarilla máxima . ^[15]

La encuesta de Omri Weinstein de 2015 ^[16] analiza el tema.

Complejidad de la comunicación cuántica

La complejidad de la comunicación cuántica intenta cuantificar la reducción posible de la comunicación mediante el uso de efectos cuánticos durante una computación distribuida.

Se han propuesto al menos tres generalizaciones cuánticas de la complejidad de la comunicación; para un estudio, véase el texto sugerido por G. Brassard.

El primero es el modelo de comunicación qubit , en el que 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 a las partes se les permite manipular un suministro ilimitado de estados cuánticos entrelazados como parte de sus protocolos. Al realizar mediciones de 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 una complejidad de 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 para todos los pares entre la suma del número de bits intercambiados y la longitud de codificación de la palabra de Oracle. ${\displaystyle f(x,y)}$ ${\displaystyle (x,y)}$

Visto de otra manera, esto equivale a cubrir todas las entradas 1 de la matriz 0/1 mediante rectángulos 1 combinatorios (es decir, submatrices no contiguas y 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 rectángulos 1 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 al rango no negativo de una matriz no negativa. ^[17]

Complejidad de comunicación de errores ilimitados

En la configuración de error ilimitado, Alice y Bob tienen acceso a una moneda privada y a sus propias entradas . En este escenario, Alice tiene éxito si responde con el valor correcto de con una 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. ${\displaystyle (x,y)}$ ${\displaystyle f(x,y)}$ ${\displaystyle f(x,y)}$

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 cuenta para la complejidad de la comunicación, es fácil argumentar que calcular cualquier función tiene complejidad de comunicación. ^[18] 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. ^[19] ${\displaystyle O(1)}$

Aunque sutiles, los límites inferiores de este modelo son extremadamente fuertes. Más específicamente, está claro que cualquier límite a los problemas de esta clase implica inmediatamente límites equivalentes a los problemas en el modelo determinista y en los modelos de monedas públicas y privadas, pero tales límites también son válidos inmediatamente para los modelos de comunicación no deterministas y los modelos de comunicación cuántica. ^[20]

Forster ^[21] fue el primero en demostrar 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 . ^[22] ${\displaystyle \langle x,y\rangle }$ ${\displaystyle \Omega (n)}$ ${\displaystyle f:\{0,1\}^{n}\times \{0,1\}^{n}\to \{0,1\}}$ ${\displaystyle \Omega (n)}$

Levantamiento

El levantamiento es una técnica general en la teoría de la complejidad en la que un límite inferior de una medida simple de complejidad se "eleva" a un límite inferior de una medida más difícil.

Esta técnica fue iniciada en el contexto de la complejidad de la comunicación por Raz y McKenzie, ^[23] quienes demostraron el primer teorema de elevación de la consulta a la comunicación y utilizaron el resultado para separar la jerarquía NC monótona .

Dadas una función y un gadget , su composición se define de la siguiente manera: ${\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}$ ${\displaystyle g\colon \{0,1\}^{a}\times \{0,1\}^{b}\to \{0,1\}}$ ${\displaystyle f\circ g\colon \{0,1\}^{na}\times \{0,1\}^{nb}\to \{0,1\}}$

${\displaystyle (f\circ g)(x,y)=f(g(x_{1,1}\cdots x_{1,a},y_{1,1}\cdots y_{1,b}),\dots ,g(x_{n,1}\cdots x_{n,a},y_{n,1}\cdots y_{n,b})).}$

En palabras, se divide en bloques de longitud y se divide en bloques de longitud . El dispositivo se aplica varias veces en los bloques y las salidas se alimentan . Diagramáticamente: ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle y}$ ${\displaystyle n}$ ${\displaystyle b}$ ${\displaystyle n}$ ${\displaystyle f}$

En este diagrama, cada una de las entradas tiene una longitud de un bit y cada una de las entradas tiene una longitud de b bits. ${\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{n}}$ ${\displaystyle \mathbf {y} _{1},\dots ,\mathbf {y} _{n}}$

Un árbol de decisión de profundidad para se puede traducir a un protocolo de comunicación cuyo costo es : cada vez que el árbol consulta un bit, el valor correspondiente de se calcula utilizando un protocolo óptimo para . Raz y McKenzie demostraron que esto es óptimo hasta un factor constante cuando es el llamado "dispositivo de indexación", en el que tiene longitud (para una constante c suficientemente grande ), tiene longitud y es el -ésimo bit de . ${\displaystyle \Delta }$ ${\displaystyle f}$ ${\displaystyle \Delta \cdot D(g)}$ ${\displaystyle g}$ ${\displaystyle g}$ ${\displaystyle g}$ ${\displaystyle x}$ ${\displaystyle c\log n}$ ${\displaystyle y}$ ${\displaystyle n^{c}}$ ${\displaystyle g(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$

La prueba del teorema de elevación de Raz-McKenzie utiliza el método de simulación, en el que se utiliza un protocolo para la función compuesta para generar un árbol de decisión para . Göös, Pitassi y Watson ^[24] dieron una exposición de la prueba original. Desde entonces, varios trabajos han demostrado teoremas similares con diferentes dispositivos, como el producto interno. ^[25] El dispositivo más pequeño que se puede manejar es el dispositivo de indexación con . ^[26] Göös, Pitassi y Watson ampliaron la técnica de Raz-McKenzie a protocolos aleatorios. ^[27] ${\displaystyle f\circ g}$ ${\displaystyle f}$ ${\displaystyle c=1+\epsilon }$

Una simple modificación del teorema de elevación de Raz-McKenzie proporciona un límite inferior del logaritmo del tamaño de un árbol de protocolo para computación , donde es la profundidad del árbol de decisión óptimo para . Garg, Göös, Kamath y Sokolov extendieron esto a la configuración tipo DAG ^[28] y utilizaron su resultado para obtener límites inferiores del circuito monótono. La misma técnica también ha dado lugar a aplicaciones para demostrar la complejidad . ^[29] ${\displaystyle \Delta \cdot D(g)}$ ${\displaystyle f\circ g}$ ${\displaystyle \Delta }$ ${\displaystyle f}$

Un tipo diferente de elevación se ejemplifica con el método de matriz de patrones de Sherstov, ^[30] que proporciona un límite inferior a la complejidad de la comunicación cuántica de , donde g es un dispositivo de indexación modificado, en términos del grado aproximado de f . El grado aproximado de una función booleana es el grado mínimo de un polinomio que aproxima la función en todos los puntos booleanos hasta un error aditivo de 1/3. ${\displaystyle f\circ g}$

En contraste con la prueba de Raz-McKenzie que utiliza el método de simulación, la prueba de Sherstov toma un testigo dual del grado aproximado de f y da un límite inferior a la complejidad de la consulta cuántica al usar el método de discrepancia generalizada . El testigo dual para el grado aproximado de f es un testigo de límite inferior para el grado aproximado obtenido mediante la dualidad LP . Este testigo dual se incorpora a otros objetos que constituyen datos para el método de discrepancia generalizada. ${\displaystyle f\circ g}$

Otro ejemplo de este enfoque es el trabajo de Pitassi y Robere, ^[31] en el que una brecha algebraica se eleva a un límite inferior en la medida de rango de Razborov . El resultado es un límite inferior fuertemente exponencial en la complejidad del circuito monótono de una función explícita, obtenido mediante la caracterización de Karchmer-Wigderson ^[32] del tamaño del circuito monótono en términos de complejidad de la comunicación.

Problemas abiertos

Considerando una matriz de entrada 0 o 1 , se sabe que el número mínimo de bits intercambiados para calcular de manera determinista en el peor de los casos está limitado 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á limitada 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 computable en tiempo polinómico en el tamaño de la matriz, dicho límite superior permitiría aproximar la complejidad de comunicación de la matriz en tiempo polinómico. Sin embargo, tenga en cuenta que el tamaño de la matriz en sí es exponencial en el tamaño de la entrada. ${\displaystyle M_{f}=[f(x,y)]_{x,y\in \{0,1\}^{n}}}$ ${\displaystyle f}$ ${\displaystyle D(f)}$ ${\displaystyle M_{f}}$ ${\displaystyle D(f)}$ ${\displaystyle M_{f}}$ ${\displaystyle (M_{f})}$ ${\displaystyle (M_{f})}$

Para un protocolo aleatorio, se conjeturó que el número de bits intercambiados en el peor de los casos, R(f), estaba relacionado polinómicamente con la siguiente fórmula:

${\displaystyle \log \min({\textrm {rank}}(M'_{f}):M'_{f}\in \mathbb {R} ^{2^{n}\times 2^{n}},(M_{f}-M'_{f})_{\infty }\leq 1/3).}$

Estas conjeturas de rango logarítmico son valiosas porque reducen la cuestión de la complejidad de comunicación de una matriz a una cuestión de filas (columnas) linealmente independientes de la matriz. Esta versión particular, llamada Conjetura de rango logarítmico aproximado, fue refutada recientemente por Chattopadhyay, Mande y Sherif (2019) ^[33] utilizando un contraejemplo sorprendentemente simple. Esto revela que la esencia del problema de complejidad de la comunicación, por ejemplo en el caso EQ anterior, es descubrir en qué parte de la matriz están las entradas, para saber si son equivalentes.

Aplicaciones

Los límites inferiores de la complejidad de la comunicación se pueden utilizar para demostrar los límites inferiores de la complejidad de los árboles de decisión , los circuitos VLSI , las estructuras de datos, los algoritmos de transmisión , las compensaciones espacio-temporales para las máquinas de Turing y más. ^[2]

Conitzer y Sandholm ^[34] estudiaron la complejidad de la comunicación de algunas reglas de votación comunes , que son esenciales en organizaciones políticas y no políticas. La complejidad de la compilación es una noción estrechamente relacionada, que puede verse como una complejidad de comunicación de ronda única.

Ver también

• Problema de Gap-Hamming

Notas

1. Yao, AC (1979), "Algunas cuestiones de complejidad relacionadas con la computación distributiva", Proc. Del 11 STOC , 14 : 209-213
2. Kushilevitz, Eyal; Nisan, Noam (1997). Complejidad de la comunicación . Prensa de la Universidad de Cambridge. ISBN 978-0-521-56067-2.
3. R. Cleve, W. van Dam, M. Nielsen y A. Tapp, Quantum Computing and Quantum Communications (Springer Berlin Heidelberg, Berlín, Heidelberg, 1999) págs.
4. M. Navascués, Y. Guryanova, MJ Hoban y A. Acín, Nature Communications 6, 6288 (2015).
5. W. van Dam, Complejidad de la comunicación y la no localidad, Ph.d. tesis, Universidad de Oxford (1999).
6. G. Brassard, H. Buhrman, N. Linden, AA M ́ethot, A. Tapp y F. Unger, Phys. Rev. Lett. 96, 250401 (2006).
7. N. Brunner y P. Skrzypczyk, Phys. Rev. Lett. 102, 160403 (2009).
8. P. Botteron, A. Broadbent y M.-O. Proulx, arXiv:2302.00488.
9. Yao, Andrew Chi-Chih (1977). "Cálculos probabilísticos: hacia una medida unificada de complejidad". 18º Simposio Anual sobre Fundamentos de la Informática (sfcs 1977) . IEEE. doi :10.1109/SFCS.1977.24. ISSN  0272-5428.
10. Razborov, Alejandro (1992). "Sobre la complejidad distributiva de la desunión". Informática Teórica . 106 : 385–390. doi : 10.1016/0304-3975(92)90260-M . Consultado el 1 de diciembre de 2023 .
11. Bar-Yossef, Ziv; Jayram, TS; Kumar, Ravi; Sivakumar, D. (2004). "Un enfoque de estadísticas de información para el flujo de datos y la complejidad de la comunicación" (PDF) . Revista de Ciencias de la Computación y de Sistemas . 68 : 702–732. doi : 10.1016/j.jcss.2003.11.006 . Consultado el 1 de diciembre de 2023 .
12. Barac, Booz ; Braverman, Marcos ; Chen, Xi; Rao, Anup (2013). "Cómo comprimir la comunicación interactiva" (PDF) . Revista SIAM de Computación . 42 (3): 1327-1363. doi :10.1137/100811969.
13. Hombre valiente, Mark ; Rao, Anup (2014). «Información es igual a comunicación amortizada» (PDF) . Transacciones IEEE sobre teoría de la información . 60 (10): 6058–6069. doi :10.1109/TIT.2014.2347282.
14. Hombre valiente, Mark ; Garg, Ankit; Pankrátov, Denis; Weinstein, Omri (junio de 2013). STOC '13: Actas del cuadragésimo quinto simposio anual de ACM sobre Teoría de la Computación . Palo Alto, California: ACM. págs. 151-160. doi :10.1145/2488608.2488628.
15. Hombre valiente, Mark ; Moitra, Ankur (1 de junio de 2013). "Un enfoque de complejidad de la información para formulaciones extendidas". STOC '13: Actas del cuadragésimo quinto simposio anual de ACM sobre Teoría de la Computación . Palo Alto, California: ACM. págs. 161-170. doi :10.1145/2488608.2488629.
16. Weinstein, Omri (junio de 2015). "La complejidad de la información y la búsqueda de la compresión interactiva". Noticias ACM SIGACT . 46 (2): 41–64. doi : 10.1145/2789149.2789161 . Consultado el 1 de diciembre de 2023 .
17. Yannakakis, M. (1991). "Expresar problemas de optimización combinatoria mediante programas lineales". J. Computación. Sistema. Ciencia . 43 (3): 441–466. doi :10.1016/0022-0000(91)90024-y.
18. Lovett, Shachar, CSE 291: Complejidad de la comunicación, protocolos de error ilimitado de invierno de 2019 (PDF) , consultado el 9 de junio de 2019
19. 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.
20. Sherstov, Alexander A. (octubre de 2008). "La complejidad ilimitada de la comunicación de errores de las funciones simétricas". 2008 49º Simposio anual del IEEE sobre fundamentos de la informática . págs. 384–393. doi :10.1109/focs.2008.20. ISBN 978-0-7695-3436-7. S2CID  9072527.
21. Forster, Jürgen (2002). "Un límite inferior lineal de la complejidad de la comunicación probabilística de errores ilimitados". Revista de Ciencias de la Computación y de Sistemas . 65 (4): 612–625. doi : 10.1016/S0022-0000(02)00019-3 .
22. Alon, N.; Frankl, P.; Rodl, V. (octubre de 1985). "Realización geométrica de sistemas establecidos y complejidad de comunicación probabilística". 26º Simposio Anual sobre Fundamentos de la Informática (SFCS 1985) . Portland, Oregón, EE. UU.: IEEE. págs. 277–280. CiteSeerX 10.1.1.300.9711 . doi :10.1109/SFCS.1985.30. ISBN  9780818606441. S2CID  8416636.
23. Raz, corrió ; McKenzie, Pierre (1999). "Separación de la jerarquía NC monótona". Combinatoria . 19 : 403–435. doi :10.1007/s004930050062.
24. Göös, Mika; Pitassi, Toniann ; Watson, Thomas (2018). "Comunicación determinista versus número de partición". Revista SIAM de Computación . 74 (6): 2435–2450. doi :10.1137/16M1059369.
25. Chattopadhyay, Arkadev; Koucký, Michal; Loff, Bruno; Mukhopadhyay, Sagnik (2019). "Teoremas de simulación mediante propiedades pseudoaleatorias". Complejidad computacional . 28 (4): 617–659. arXiv : 1704.06807 . doi : 10.1007/s00037-019-00190-7 .
26. Lovett, Shachar; Meka, Raghu; Mertz, Ian; Pitassi, Toniann ; Zhang, Jiapeng (200). «Levantamiento con Girasoles» (PDF) . 13° Congreso de Innovaciones en Informática Teórica (ITCS 2022) . vol. 215. Procedimientos internacionales de informática de Leibniz (LIPIcs). págs. 104:1-104:24. doi :10.4230/LIPIcs.ITCS.2022.104.
27. Göös, Mika; Pitassi, Toniann ; Watson, Thomas (2017). "Elevación de consultas a comunicaciones para BPP". 58.º Simposio anual del IEEE de 2017 sobre fundamentos de la informática (FOCS) . Berkeley, California: IEEE. arXiv : 1703.07666 . doi :10.1109/FOCS.2017.21.
28. Garg, Ankit; Göös, Mika; Kamath, pritish; Sokolov, Dmitry (2020). "Límites inferiores del circuito monótono desde la resolución". Teoría de la Computación . 16 : 13:1–13:30. doi : 10.4086/toc.2020.v016a013 .
29. de Rezende, Susana; Meir, o; Nordström, Jakob; Pitassi, Toniann ; Robere, Robere; Vinyals, Marc (2020). "Levantamiento con dispositivos y aplicaciones simples para circuitos y prueba de complejidad". 2020 61.º Simposio anual del IEEE sobre fundamentos de la informática (FOCS) . Conferencia virtual: IEEE. págs. 24-30. arXiv : 2001.02144 . doi :10.1109/FOCS46700.2020.00011.
30. Sherstov, Alejandro (2011). "El método de la matriz de patrones". Revista SIAM de Computación . 40 (6): 1969-2000. doi : 10.1137/080733644.
31. Pitassi, Toniann ; Robere, Robert (2017). "Límites inferiores fuertemente exponenciales para la computación monótona" (PDF) . STOC 2017: Actas del 49º Simposio anual ACM SIGACT sobre teoría de la informática . Montreal: ACM. págs. 1246-1255. doi :10.1145/3055399.3055478.
32. Karchmer, Mauricio; Wigderson, Avi (1990). "Los circuitos monótonos para la conectividad requieren una profundidad superlogarítmica" (PDF) . Revista SIAM de Matemática Discreta . 3 (2): 255–265. doi :10.1137/0403021.
33. Chattopadhyay, Arkadev; Mande, Nikhil S.; Sherif, Suhail (2019). "La conjetura del rango logarítmico aproximado es falsa". 2019, Actas del 51º Simposio Anual ACM sobre Teoría de la Computación: 42-53.https://doi.org/10.1145/3313276.3316353
34. Conitzer, Vicente; Sandholm, Tuomas (5 de junio de 2005). "Complejidad comunicativa de las reglas comunes de votación". Actas de la sexta conferencia ACM sobre comercio electrónico . CE '05. Nueva York, NY, EE.UU.: Association for Computing Machinery: 78–87. doi :10.1145/1064009.1064018. ISBN 978-1-59593-049-1.

Referencias

• Rao, Anup; Yehudayoff, Amir (2020). Complejidad y aplicaciones de la comunicación . Cambridge: Prensa de la Universidad de Cambridge. ISBN 9781108671644.
• Kushilevitz, Eyal; Nisan, Noam (2006). Complejidad de la comunicación . Cambridge: Prensa de la Universidad de Cambridge. 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. Computadora. Ciencia. 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 Estadounidense de Matemáticas, 2004. 129-137.
• AC Yao, "Algunas cuestiones de complejidad relacionadas con la informática distribuida", Proc. del 11º 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.