complejidad de la comunicación entre múltiples partes

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 dos participantes.

En el juego de comunicación tradicional de dos partes , introducido por Yao (1979) , ^{[ 1 ]} dos jugadores, P ₁ y P ₂ 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 deben comunicar los jugadores para calcular f es la complejidad de comunicación de f , denotada por κ ( f ). 

El juego de comunicación multipartita, definido en 1983, ^{[ 2 ]} es una poderosa generalización del caso de dos partes: aquí los jugadores conocen todas las entradas de los demás, excepto la suya propia. Debido a esta propiedad, a veces este modelo se denomina 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 todas las entradas de los demás, excepto la suya propia.

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

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

En el set${\displaystyle S=\{x_{1},x_{2},...,x_{n}\}}$de variables hay una partición fija${\displaystyle A}$de${\displaystyle k}$clases${\displaystyle A_{1},A_{2},...,A_{k}}$y jugador${\displaystyle P_{i}}$conoce todas las variables, excepto aquellas en${\displaystyle A_{i}}$, para${\displaystyle i=1,2,...,k}$Los jugadores disponen de capacidad de cálculo ilimitada y se comunican mediante una pizarra visible para todos.

El objetivo es calcular${\displaystyle f(x_{1},x_{2},...,x_{n}}$), de tal manera que al final del cálculo, cada jugador conozca este valor. El costo del cálculo es el número de bits escritos en la pizarra para la entrada dada. ${\displaystyle x=(x_{1},x_{2},...,x_{n})}$y partición${\displaystyle A=(A_{1},A_{2},...,A_{n})}$El costo de un protocolo multipartito es el número máximo de bits comunicados para cualquier${\displaystyle x}$del conjunto {0,1} ⁿ y la partición dada${\displaystyle A}$. El${\displaystyle k}$-complejidad de la comunicación entre partes,${\displaystyle C_{A}^{(k)}(f)}$de una función${\displaystyle f}$, con respecto a la partición${\displaystyle A}$, es el mínimo de costos de esos${\displaystyle k}$protocolos de -parte que calculan${\displaystyle f}$. El${\displaystyle k}$-complejidad de comunicación simétrica entre partes de${\displaystyle f}$se define como

${\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})}$.

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 | A ₁ |  +  1 bits de comunicación: P ₂ escribe los | A ₁ | bits de A ₁ en la pizarra, P ₁ los lee y calcula y anuncia el valor.${\displaystyle f(x)}$Por lo tanto, se puede escribir lo siguiente:

${\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: Sea${\displaystyle y_{1},y_{2},...,y_{k}}$ser${\displaystyle n}$vectores de bits y deje${\displaystyle Y}$ser el${\displaystyle n}$veces${\displaystyle k}$matriz, con${\displaystyle k}$columnas como el${\displaystyle y_{1},y_{2},...,y_{k}}$vectores. Entonces${\displaystyle GIP(y_{1},y_{2},...,y_{k})}$es el número de filas de 1 en la matriz${\displaystyle Y}$, tomado módulo  2. En otras palabras, si los vectores${\displaystyle y_{1},y_{2},...,y_{k}}$corresponden a los vectores característicos de${\displaystyle k}$subconjuntos de un${\displaystyle n}$conjunto base de elementos, entonces GIP corresponde a la paridad de la intersección de estos${\displaystyle k}$subconjuntos.

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 acotar la complejidad de 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 )}}$

La construcción de un generador de números pseudoaleatorios se basó en la cota inferior BNS para la función GIP. ^{[ 3 ]}