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 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 suele enunciarse 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 tanto de como , 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 si Bob envía 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 se relaciona con la cantidad de computación realizada por Alice o Bob, o el tamaño de la memoria utilizada, ya que generalmente no asumimos nada sobre la potencia computacional de Alice o Bob. ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle n}$

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 disminuyendo la cantidad de señales eléctricas que pasan entre los diferentes componentes durante un cómputo distribuido. El problema también es relevante en el estudio de las estructuras de datos y en la optimización de redes informáticas. Para estudios generales sobre este campo, consulte los libros de texto de Rao y Yehudayoff (2020) y Kushilevitz y Nisan (2006).

Definición 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í un bit a la vez (adoptando algún protocolo de comunicación que se acuerda de antemano), Alice y Bob desean calcular el valor de tal manera 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 vuelta de modo que, al costo de un bit adicional, ambas partes conocerán la respuesta. La complejidad de comunicación del peor caso de este problema de comunicación de calcular , denotada 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 (asumiendo que ambas partes conocen la función ). Luego, 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 tanto y . Al comienzo 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 resultan en 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 denomina rectángulo (combinatorio) si siempre que y entonces . De manera equivalente, es un rectángulo combinatorio si se puede expresar como para algunos y . Consideremos el caso en el que ya se han intercambiado bits entre las partes. 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

Consideremos el caso en el que Alice y Bob intentan determinar si sus cadenas de entrada son iguales o no. Formalmente, definamos la función de igualdad , denotada , por if . Como demostramos a continuación, cualquier resolución de protocolo de comunicación determinista 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 por la matriz siguiente. 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 solo se evalúa como 1 cuando es igual (es decir, está 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 de 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

Demostración. Supongamos que . Esto significa que existen tales 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 y sabemos que la igualdad solo es verdadera para 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 para probar los límites inferiores de la comunicación determinista se denomina técnica del conjunto engañoso . ^[2]

Complejidad de comunicación aleatoria

En la definición anterior, nos ocupamos de la cantidad de bits que se deben transmitir de manera determinista entre dos partes. Si ambas partes tienen acceso a un generador de números aleatorios, ¿pueden determinar el valor de con mucho menos información intercambiada? Yao, en su artículo seminal ^[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. Existen 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 ser comunicada a la otra parte. Un teorema presentado a continuación muestra que cualquier protocolo de cadena pública puede ser simulado por un protocolo de cadena privada que utiliza O(log n) bits adicionales en comparación con el original.

Nótese que en las desigualdades de probabilidad anteriores, se entiende que el resultado del protocolo depende únicamente de la cadena aleatoria; ambas cadenas x e y permanecen fijas. En otras palabras, si R ( x , y ) produce g ( x , y , r ) cuando se utiliza la cadena aleatoria r , entonces g ( x , y , r ) = f ( x , y ) para al menos 2/3 de todas las opciones para la cadena r .

La complejidad aleatoria se define simplemente como la cantidad 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 solo mensajes ⁠ ⁠ ${\displaystyle O(\log n)}$ . Considere el siguiente protocolo: Suponga que Alice y Bob tienen acceso a la misma cadena aleatoria . Alice calcula y envía este bit (llamémoslo b ) a Bob. (El es 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, rechaza. ${\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. ¿Cómo sucede 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}}}$

Donde x e y coinciden, por lo que esos términos afectan a los productos escalares por igual. Podemos ignorar esos términos con seguridad y observar solo dónde difieren x e y . Además, podemos intercambiar los bits sin cambiar si los productos escalares son iguales o no. Esto significa que podemos intercambiar bits para que x contenga solo ceros e 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 una 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 simplemente . Por lo tanto, cuando x no es igual a y , . El algoritmo se puede repetir muchas veces para aumentar su precisión. Esto cumple con los requisitos de un algoritmo de comunicación aleatorio. ${\displaystyle 1/2}$ ${\displaystyle Prob_{z}[Accept]=1/2}$

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

Ejemplo: GH

Para otro ejemplo 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 les gustaría determinar si las cadenas son muy similares o no lo son. En particular, les gustaría encontrar un protocolo de comunicación que requiera la transmisión de la menor cantidad posible de bits 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 determinista y estricto de índices que Alice y Bob se transmiten entre sí, entonces imagine tener un par de cadenas que en ese conjunto difieren en posiciones. Si ocurre otro desacuerdo en cualquier posición que no se transmite, esto afecta el resultado de y, por lo tanto, daría como resultado 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 ocasiones (en instancias aleatorias extraídas uniformemente al azar de ), ¿podemos entonces salirnos con la nuestra con un protocolo con menos bits? Resulta que la respuesta, algo sorprendente, es no, debido a un resultado de Chakrabarti y Regev en 2012: ellos muestran que para instancias aleatorias, cualquier procedimiento que sea correcto al menos en ocasiones 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 sencilla 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 un pequeño costo de comunicación. Cualquier protocolo aleatorio de cadena compartida que utilice cualquier cantidad de cadenas aleatorias se puede simular mediante un protocolo de cadena privado que utilice O(log n) bits adicionales.

Intuitivamente, podemos encontrar un conjunto de cadenas que contenga suficiente aleatoriedad para ejecutar el protocolo aleatorio con solo un pequeño aumento del error. Este conjunto se puede compartir de antemano y, en lugar de extraer 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 se pueda comunicar de manera eficiente. A continuación, se presenta una prueba formal.

Consideremos un protocolo aleatorio P con una tasa de error máxima de 0,1. Sean cadenas de longitud n , numeradas . Dado un , definamos un nuevo protocolo que escoja aleatoriamente algunas 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 un fijo , 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í que cuando no tenemos fijo: ${\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 diferentes pares . 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. Al utilizar ese recurso, Alice y Bob pueden correlacionar su información y, de ese modo, 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 escenario posible 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, de manera más general, las correlaciones casi cuánticas ^[4], mientras que, por el contrario, se ha demostrado que otros recursos colapsan la complejidad de comunicación aleatoria, como la PR-box ^[5] o algunas PR-boxes ruidosas que satisfacen 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 distribucional máxima, donde el máximo se toma sobre todas las distribuciones conjuntas de las entradas (¡no necesariamente distribuciones de producto!).

El principio de Yao se puede utilizar para demostrar límites inferiores a la complejidad de 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 concierne a los protocolos deterministas, esto podría ser más fácil que demostrar un límite inferior a los protocolos aleatorios directamente.

Como ejemplo, consideremos la función de disyunción 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 comunicación aleatoria al considerar la siguiente distribución: con probabilidad 3/4, muestree dos conjuntos disjuntos aleatorios 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 información (interna) de un protocolo (posiblemente aleatorio) R con respecto a una distribución μ se define de la siguiente manera. Sean entradas aleatorias muestreadas según μ y sea Π la transcripción de R cuando se ejecuta en las entradas . La complejidad de 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 la entrada de Bob a partir de la transcripción, y el segundo mide la cantidad de información que Bob aprende sobre la entrada de Alice.

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

Braverman y Rao demostraron que la información equivale a comunicación amortizada. Esto significa que el costo de resolver n copias independientes de f es aproximadamente n veces la complejidad de información de f . Esto es análogo a la interpretación bien conocida de la entropía de Shannon como la longitud de bits amortizada necesaria para transmitir datos desde una fuente de información dada. 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 disyunción de conjuntos . ^[14] ${\displaystyle 1.4923\ldots n}$

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

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

Complejidad de la comunicación cuántica

La complejidad de la comunicación cuántica intenta cuantificar la reducción de la comunicación posible 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 un resumen de ellas, véase 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 se sigue realizando con bits clásicos, pero las partes pueden manipular una cantidad ilimitada 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ómputo distribuido.

El tercer modelo implica el acceso a un entrelazamiento previamente compartido además de la comunicación qubit , y es el menos explorado de los tres modelos cuánticos.

Complejidad de comunicación no determinista

En la 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 comunicación no determinista es entonces el máximo de todos los pares sobre la suma del número de bits intercambiados y la longitud de codificación de la palabra del oráculo. ${\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, no convexas, cuyas entradas son todas uno (véase Kushilevitz y Nisan o Dietzfelbinger et al.)). La complejidad de comunicación no determinista es el logaritmo binario del número de rectángulos que cubren 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 comunicación no determinista se presenta como un medio para obtener límites inferiores para la complejidad de comunicación determinista (ver Dietzfelbinger et al.), pero también en la teoría de matrices no negativas, donde proporciona un límite inferior para el rango no negativo de una matriz no negativa. ^[17]

Complejidad de comunicación sin límites de error

En la configuración de error ilimitado, Alice y Bob tienen acceso a una moneda privada y a sus propias entradas . En esta configuración, 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)}$

Cabe señalar que el requisito de que la moneda sea privada es esencial. En particular, si la cantidad de bits públicos compartidos entre Alice y Bob no se tienen en cuenta en la complejidad de la comunicación, es fácil argumentar que el cálculo de cualquier función tiene complejidad de comunicación. ^[18] Por otra parte, ambos modelos son equivalentes si la cantidad de bits públicos utilizados por Alice y Bob se tiene en cuenta en 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, es claro que cualquier límite en problemas de esta clase implica inmediatamente límites equivalentes en problemas en el modelo determinista y los modelos de monedas privadas y públicas, pero dichos límites también se cumplen 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 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

La elevación 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 desarrollada por primera vez en el contexto de la complejidad de la comunicación por Raz y McKenzie ^[23] , quienes demostraron el primer teorema de elevación de consulta a comunicación y utilizaron el resultado para separar la jerarquía NC monótona .

Dada 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 introducen en . Diagrama: ${\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 a bits 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, se calcula el valor correspondiente de 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 una longitud (para una constante suficientemente grande c ), tiene una longitud , y es el bit -ésimo 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 extendieron la técnica de Raz-McKenzie a protocolos aleatorios. ^[27] ${\displaystyle f\circ g}$ ${\displaystyle f}$ ${\displaystyle c=1+\epsilon }$

Una modificación simple del teorema de elevación de Raz-McKenzie proporciona un límite inferior de en el logaritmo del tamaño de un árbol de protocolo para calcular , donde es la profundidad del árbol de decisión óptimo para . Garg, Göös, Kamath y Sokolov extendieron esto al entorno tipo DAG , ^{[28] y usaron su resultado para obtener límites inferiores} de circuito monótono . La misma técnica también ha producido 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 mediante el método de matriz de patrones de Sherstov, ^[30] que proporciona un límite inferior para la complejidad de 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}$

A diferencia de la prueba de Raz-McKenzie que utiliza el método de simulación, la prueba de Sherstov toma un testigo dual para el grado aproximado de f y proporciona un límite inferior para la complejidad de consulta cuántica de 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 a través de 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 se eleva una brecha algebraica 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, obtenida a través de la caracterización de Karchmer-Wigderson ^[32] del tamaño del circuito monótono en términos de complejidad de comunicación.

Problemas abiertos

Considerando una matriz de entrada de 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á acotado desde abajo por el logaritmo del rango de la matriz . La conjetura del rango logarítmico propone que la complejidad de comunicación, , está acotada desde arriba por una potencia constante del logaritmo del rango de . Dado que D(f) está acotada desde arriba y desde abajo por polinomios de rango logarítmico , podemos decir que D(f) está relacionada polinómicamente 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 aproximarse a 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 polinomialmente 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 la 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 la complejidad de la comunicación, por ejemplo en el caso de EQ anterior, es averiguar dónde están las entradas en la matriz, para averiguar si son equivalentes.

Aplicaciones

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

Conitzer y Sandholm ^[34] estudiaron la complejidad comunicacional de algunas reglas de votación comunes , que son esenciales en organizaciones políticas y no políticas. La complejidad de compilación es un concepto estrechamente relacionado, que puede verse como una complejidad comunicacional de una sola ronda.

Véase también

• Problema de Gap-Hamming

Notas

1. Yao, AC (1979), "Algunas cuestiones de complejidad relacionadas con la computación distributiva", Proc. Of 11th STOC , 14 : 209–213
2. Kushilevitz, Eyal; Nisan, Noam (1997). Complejidad de la comunicación . Cambridge University Press. ISBN 978-0-521-56067-2.
3. Cleve, Richard; Van Dam, Wim; Nielsen, Michael; Tapp, Alain (1999). "Enredo cuántico y complejidad de comunicación de la función de producto interno". Computación cuántica y comunicaciones cuánticas. Apuntes de clase en informática. Vol. 1509. págs. 61–74. doi :10.1007/3-540-49208-9_4. ISBN 978-3-540-65514-5.
4. Navascués, Miguel; Guryanova, Yelena; Hoban, Matty J.; Acín, Antonio (2015). "Correlaciones casi cuánticas". Comunicaciones de la naturaleza . 6 : 6288. arXiv : 1403.4621 . Código Bib : 2015NatCo...6.6288N. doi : 10.1038/ncomms7288. PMID  25697645.
5. W. van Dam, No localidad y complejidad de la comunicación, tesis doctoral, 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 la complejidad". 18.º Simposio anual sobre fundamentos de la informática (sfcs 1977) . IEEE. doi :10.1109/SFCS.1977.24. ISSN  0272-5428.
10. Razborov, Alexander (1992). "Sobre la complejidad distributiva de la disyunción". Theoretical Computer Science . 106 (2): 385–390. doi : 10.1016/0304-3975(92)90260-M .
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) . Journal of Computer and System Sciences . 68 (4): 702–732. doi :10.1016/j.jcss.2003.11.006 . Consultado el 1 de diciembre de 2023 .
12. Barak, Boaz ; Braverman, Mark ; Chen, Xi; Rao, Anup (2013). "Cómo comprimir la comunicación interactiva" (PDF) . Revista SIAM de Informática . 42 (3): 1327–1363. doi :10.1137/100811969.
13. Braverman, Mark ; Rao, Anup (2014). "La información equivale a comunicación amortizada". IEEE Transactions on Information Theory . 60 (10): 6058–6069. arXiv : 1106.3595 . doi :10.1109/TIT.2014.2347282.
14. Braverman, Mark ; Garg, Ankit; Pankratov, Denis; Weinstein, Omri (junio de 2013). STOC '13: Actas del cuadragésimo quinto simposio anual de la ACM sobre teoría de la computación . Palo Alto, CA: ACM. págs. 151–160. doi :10.1145/2488608.2488628. ISBN . 978-1-4503-2029-0.
15. Braverman, 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 la ACM sobre teoría de la computación . Palo Alto, CA: ACM. págs. 161–170. doi :10.1145/2488608.2488629.
16. Weinstein, Omri (junio de 2015). "Complejidad de la información y la búsqueda de la compresión interactiva". ACM SIGACT News . 46 (2): 41–64. doi :10.1145/2789149.2789161 . Consultado el 1 de diciembre de 2023 .
17. Yannakakis, M. (1991). "Expresión de problemas de optimización combinatoria mediante programas lineales". J. Comput. Syst. Sci . 43 (3): 441–466. doi :10.1016/0022-0000(91)90024-y.
18. Lovett, Shachar, CSE 291: Communication Complexity, Winter 2019 Unbounded-error protocols (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 de la comunicación de errores sin límites de las funciones simétricas". 49.° Simposio anual IEEE sobre fundamentos de la informática de 2008. 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 en la complejidad de la comunicación probabilística de error ilimitado". Journal of Computer and System Sciences . 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 de conjuntos y complejidad de comunicación probabilística". 26.º Simposio anual sobre fundamentos de la informática (SFCS 1985) . Portland, OR, EE. UU.: IEEE. pp. 277–280. CiteSeerX 10.1.1.300.9711 . doi :10.1109/SFCS.1985.30. ISBN.  9780818606441.S2CID8416636  .​
23. Raz, Ran ; McKenzie, Pierre (1999). "Separación de la jerarquía NC monótona". Combinatorica . 19 (3): 403–435. doi :10.1007/s004930050062.
24. Göös, Mika; Pitassi, Toniann ; Watson, Thomas (2018). "Comunicación determinista vs. 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 a través de 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). "Levantando con girasoles" (PDF) . 13.ª Conferencia sobre innovaciones en informática teórica (ITCS 2022) . Vol. 215. Leibniz International Proceedings in Informatics (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". 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) . Berkeley, CA: IEEE. arXiv : 1703.07666 . doi :10.1109/FOCS.2017.21.
28. Garg, Ankit; Göös, Mika; Kamath, Pritish; Sokolov, Dmitry (2020). "Límites inferiores de circuitos monótonos a partir de la resolución". Teoría de la computación . 16 : 13:1–13:30. doi : 10.4086/toc.2020.v016a013 .
29. de Rezende, Susanna; Meir, Or; Nordström, Jakob; Pitassi, Toniann ; Robere, Robere; Vinyals, Marc (2020). "Levantamiento con dispositivos simples y aplicaciones a la complejidad de circuitos y pruebas". 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) . Conferencia virtual: IEEE. págs. 24–30. arXiv : 2001.02144 . doi :10.1109/FOCS46700.2020.00011.
30. Sherstov, Alexander (2011). "El método de la matriz de patrones". Revista SIAM de Computación . 40 (6): 1969–2000. arXiv : 0906.4291 . doi :10.1137/080733644.
31. Pitassi, Toniann ; Robere, Robert (2017). "Límites inferiores fuertemente exponenciales para computación monótona" (PDF) . STOC 2017: Actas del 49.° Simposio anual ACM SIGACT sobre teoría de la computación . 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áticas Discretas . 3 (2): 255–265. doi :10.1137/0403021.
33. Chattopadhyay, Arkadev; Mande, Nikhil S.; Sherif, Suhail (2019). "La conjetura del rango aproximado logarítmico es falsa". 2019, Actas del 51.º Simposio anual de la ACM sobre teoría de la computación: 42-53. https://doi.org/10.1145/3313276.3316353
34. Conitzer, Vincent; Sandholm, Tuomas (5 de junio de 2005). "Complejidad de comunicación de las reglas de votación comunes". Actas de la sexta conferencia de la ACM sobre comercio electrónico. EC '05. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 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: Cambridge University Press. ISBN 9781108671644.
• 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: un estudio. 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. Comput. Sci. 168, 1996. 39-51.
• Raz, Ran . "Complejidad de circuitos y comunicaciones". En Computational Complexity Theory. Steven Rudich y Avi Wigderson, eds. Instituto de Estudios Avanzados de la Sociedad Matemática Estadounidense, 2004. 129-137.
• AC Yao, "Algunas cuestiones de complejidad relacionadas con la computación distribuida", Actas 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. 67–71.