Complejidad de la comunicación multipartita

En informática teórica , la complejidad de la comunicación multipartita es el estudio de la complejidad de la comunicación en un entorno donde hay más de 2 jugadores.

En el tradicional juego de comunicación entre dos partes , introducido por Yao (1979), ^[1] dos jugadores, P ₁ y P _2, intentan calcular una función booleana.

${\displaystyle f(x_{1},x_{2}):\{0,1\}^{n}\to \{0,1\},\ x_{1},x_{2}\in \{0,1\}^{n'},\ 2n'=n}$

El jugador P ₁ conoce el valor de x ₂ , P ₂ conoce el valor de x ₁ , pero P _i no conoce el valor de x _i , para i  = 1, 2.

En otras palabras, los jugadores conocen las variables del otro, pero no las suyas propias. El número mínimo de bits que los jugadores deben comunicar para calcular f es la complejidad de comunicación de f , denotada por  κ ( f ).

El juego de comunicación multipartidista, definido en 1983, ^[2] es una poderosa generalización del caso de dos partes: aquí los jugadores conocen todas las aportaciones de los demás, excepto las suyas propias. Debido a esta propiedad, a veces este modelo se llama modelo de "números en la frente", ya que si los jugadores estuvieran sentados alrededor de una mesa redonda, cada uno con su propia entrada en la frente, entonces cada jugador vería la entrada de todos los demás, excepto los suyos propios.

La definición formal es la siguiente: jugadores: tienen la intención de calcular una función booleana ${\displaystyle k}$ ${\displaystyle P_{1},P_{2},...,P_{k}}$

${\displaystyle f(x_{1},x_{2},\ldots ,x_{n}):\{0,1\}^{n}\to \{0,1\}}$

En el conjunto de variables hay una partición fija de clases , y el jugador conoce todas las variables, excepto aquellas en , para . Los jugadores tienen un poder computacional ilimitado y se comunican con la ayuda de una pizarra, vista por todos los jugadores. ${\displaystyle S=\{x_{1},x_{2},...,x_{n}\}}$ ${\displaystyle A}$ ${\displaystyle k}$ ${\displaystyle A_{1},A_{2},...,A_{k}}$ ${\displaystyle P_{1}}$ ${\displaystyle A_{i}}$ ${\displaystyle i=1,2,...,k}$

El objetivo es calcular ), de modo que al final del cálculo, todos los jugadores conozcan este valor. El costo del cálculo es el número de bits escritos en la pizarra para la entrada y partición dadas . El costo de un protocolo multipartito es el número máximo de bits comunicados para cualquiera del conjunto {0,1} ⁿ y la partición dada . La complejidad de la comunicación entre partes, de una función , con respecto a la partición , es el mínimo de costos de los protocolos entre partes que computan . La complejidad de la comunicación simétrica del partido se define como ${\displaystyle f(x_{1},x_{2},...,x_{n}}$ ${\displaystyle x=(x_{1},x_{2},...,x_{n})}$ ${\displaystyle A=(A_{1},A_{2},...,Ax_{n})}$ ${\displaystyle x}$ ${\displaystyle A}$ ${\displaystyle k}$ ${\displaystyle C_{A}^{(k)}(f)}$ ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle k}$ ${\displaystyle f}$ ${\displaystyle k}$ ${\displaystyle f}$

${\displaystyle C^{(k)}(f)=\max _{A}C_{A}^{(k)}(f)}$

donde el máximo se toma sobre todas las k -particiones del conjunto . ${\displaystyle x=(x_{1},x_{2},...,x_{n})}$

Límites superior e inferior

Para un límite superior general tanto para dos como para más jugadores, supongamos que A ₁ es una de las clases más pequeñas de la partición A ₁ , A ₂ ,..., A _k . Entonces P ₁ puede calcular cualquier función booleana de S con | Un ₁ | + 1 bits de comunicación: P ₂ anota el | Un ₁ | bits de A ₁ en la pizarra, P ₁ lo lee, calcula y anuncia el valor . Entonces, se puede escribir lo siguiente: ${\displaystyle f(x)}$

${\displaystyle C^{(k)}(f)\leq {\bigg \lfloor }{n \over k}{\bigg \rfloor }+1.}$

La función de Producto Interno Generalizado (GIP) ^[3] se define de la siguiente manera: Sean vectores de bits y la matriz de tiempos , con columnas como vectores. Entonces es el número de filas de la matriz , tomadas en módulo 2. En otras palabras, si los vectores corresponden a los vectores característicos de los subconjuntos de un conjunto base de elementos, entonces GIP corresponde a la paridad de la intersección de estos subconjuntos. . ${\displaystyle y_{1},y_{2},...,y_{k}}$ ${\displaystyle n}$ ${\displaystyle Y}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle y_{1},y_{2},...,y_{k}}$ ${\displaystyle GIP(y_{1},y_{2},...,y_{k})}$ ${\displaystyle Y}$ ${\displaystyle y_{1},y_{2},...,y_{k}}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle k}$

Se demostró ^[3] que

${\displaystyle C^{(k)}(GIP)\geq c{n \over 4^{k}},}$

con una constante  c  > 0.

Un límite superior en la complejidad de la comunicación multipartita de GIP muestra ^[4] que

${\displaystyle C^{(k)}(GIP)\leq c{n \over 2^{k}},}$

con una constante c  > 0.

Para una función booleana general f , se puede limitar la complejidad de la comunicación multipartita de f utilizando su norma L ₁ ^[5] de la siguiente manera: ^[6]

${\displaystyle C^{(k)}(f)=O{\Bigg (}k^{2}\log(nL_{1}(f)){\Bigg \lceil }{nL_{1}^{2}(f) \over 2^{k}}{\Bigg \rceil }{\Bigg )}}$

Complejidad de la comunicación multipartita y generadores pseudoaleatorios

Se basó la construcción de un generador de números pseudoaleatorios en el límite inferior BNS para la función GIP. ^[3]

1. Yao, Andrew Chi-Chih (1979), "Algunas cuestiones de complejidad relacionadas con la computación distributiva", Actas del 11º Simposio ACM sobre Teoría de la Computación (STOC '79) , págs. 209-213, doi : 10.1145/800135.804414 , S2CID  999287.
2. Chandra, Ashok K .; Furst, Merrick L.; Lipton, Richard J. (1983), "Protocolos multipartitos", Actas del 15º Simposio ACM sobre Teoría de la Computación (STOC '83) , págs. 94–99, doi :10.1145/800061.808737, ISBN 978-0897910996, S2CID  18180950.
3. Babai, László ; Nisán, Noam ; Szegedy, Márió (1992), "Protocolos multipartitos, generadores pseudoaleatorios para espacio de registro y compensaciones de espacio-tiempo", Journal of Computer and System Sciences , 45 (2): 204–232, doi :10.1016/0022-0000(92 )90047-M, SEÑOR  1186884.
4. Grolmusz, Vince (1994), "El límite inferior de BNS para protocolos multipartitos es casi óptimo", Información y Computación , 112 (1): 51–54, doi : 10.1006/inco.1994.1051 , MR  1277711.
5. Bruck, Jehoshua; Smolensky, Roman (1992), "Funciones de umbral polinómico, funciones AC0 y normas espectrales" (PDF) , SIAM Journal on Computing , 21 (1): 33–42, doi :10.1137/0221003, MR  1148813.
6. Grolmusz, V. (1999), "Análisis armónico, aproximación real y complejidad de comunicación de funciones booleanas", Algorithmica , 23 (4): 341–353, CiteSeerX 10.1.1.53.6729 , doi :10.1007/PL00009265, SEÑOR  1673395, S2CID  26779824 .