Complexidade de comunicação

A noção de complexidade de comunicação foi introduzida por Yao em 1979, que investigou o seguinte problema envolvendo duas partes (Alice e Bob). Alice recebe uma cadeia x de n bits e Bob outra cadeia y de n bits, e o objetivo é que um deles (digamos, Bob) compute uma certa função f(x,y) com a menor quantidade de comunicação entre eles. Note que não estamos preocupados com o número de passos da computação, ou com o tamanho da memória (informática) utilizada. Complexidade de comunicação tenta quantificar quanta comunicação é necessário para essas computações distribuídas.

Claro que eles podem conseguir com Alice enviando sua cadeia inteira para Bob, que então computa a função, mas a ideia aqui é encontrar maneiras inteligentes de calcular f com menos de n bits de comunicação.

Esse problema abstrato é relevante em vários contextos: no design de circuitos VSLI, por exemplo, deseja-se minimizar a energia utilizada diminuindo a quantidade de sinal elétricos necessários entre os diferentes componentes durante uma computação distribuída. O problema também é relevante no estudo de estruturas de dados, e na otimização de redes de computadores. Para um panorama da área, veja o livro de Kushilevitz e Nisan.

Definição Formal

Seja $f$: X $\times$ Y $\rightarrow$ Z onde assumimos o caso típico em que $X=Y=\{0,1\}^{n}$ e $Z=\{0,1\}$. Alice manda uma cadeia de n bits $x$ $\in$ X enquanto Bob manda uma cadeia de n bits $y$ $\in$ Y. Comunicando-se um com o outro bit-a-bit (adotando algum protocolo de comunicação), Alice e Bob querem computar o valor de $f(x,y)$ tal que pelo menos uma das partes saiba o valor ao fim da comunicação. Neste momento a resposta pode ser enviada de volta então ao custo de um bit extra, as duas partes saberão a resposta. A complexidade de comunicação do pior caso desse protocol de comunicação, denotado por $D(f)$, é então definida como

$D(f)=$ número mínimo de bits trocados entre Alice e Bob no pior caso

Usando a definição acima, é útil pensar na função $f$ como uma matriz $A$ (chamada de matriz de entrada) onde cada linha da matriz corresponde a $x$$\in$ X e cada coluna corresponde a $y$ $\in$ Y. Uma entrada na matriz de entrada é $A_{\mathrm {x,y} }=f(x,y)$. Inicialmente tanto Alice como Bob tem uma cópia de toda a matriz A (assumindo que a função $f$ é conhecida pelos dois). Então, o problema de computar o valor da função pode ser reformulado como “zerar” a entrada correspondente da matriz. Esse problema pode ser solucionado se algum dos dois conhece tanto $x$ e $y$. No início da comunicação, o número de escolhas para o valor da função sobre as entradas é o tamanho da matriz, ou seja, $2^{2n}$. Então, quando cada parte troca um bit com a outra, o número de escolhas para a resposta diminui a medida que isso elimina um conjunto de linhas/colunas resultando numa submatriz de A.

Mais formalmente, um conjunto R $\subseteq$ X $\times$ Y é chamado retângulo (combinatorial) se sempre que $(x_{1},y_{1})$ $\in$ R e $(x_{2},y_{2})$ $\in$ R então $(x_{1},y_{2})$ $\in$ R. De forma equivalente, R também pode ser visto como uma submatriz da matriz de entrada A tal que R = M $\times$ N onde M $\subseteq$ X e N $\subseteq$ Y. Considere o caso quando $k$ bits já foram trocados entre as partes. Agora, para um dado $h$\in</math> $\{0,1\}^{k}$, vamos definir uma matriz

$T_{\mathrm {h} }=\{(x,y):$ os k-bits trocados na entrada $(x,y)$ são $h\}$

Então, $T_{\mathrm {h} }$ $\subseteq$ X $\times$ Y, e $T_{\mathrm {h} }$ é um retângulo e submatriz de A.

Exemplo: EQ

Nós consideramos o caso em que Alice e Bob tentam determinar se ambos possuem a mesma string. Isto é, estamos tentando determinar se $x$ é igual a $y$. É fácil provar que o problema da igualdade sempre requer o envio de $n$ bits no pior caso se quiser-se ter certeza absoluta de que $x$ e $y$ são iguais. Considere o caso simples de $x$ e $y$ possuírem 3 bits. A função de igualdade neste caso pode ser representada pela matriz abaixo. As linhas representam todas as possibilidades de $x$, as colunas representam as possibilidades de $y$.

EQ	000	001	010	011	100	101	110	111
000	1	0	0	0	0	0	0	0
001	0	1	0	0	0	0	0	0
010	0	0	1	0	0	0	0	0
011	0	0	0	1	0	0	0	0
100	0	0	0	0	1	0	0	0
101	0	0	0	0	0	1	0	0
110	0	0	0	0	0	0	1	0
111	0	0	0	0	0	0	0	1

Como você pode ver, a função apenas retorna 1 quando $x$ é igual a $y$ (ou seja, na diagonal). Também é razoavelmente fácil ver como enviando um único bit divide suas possibilidades pela metade. Se você sabe que o primeiro bit de $y$ é 1, é necessário apenas considerar metade das colunas (em que $y$ pode ser igual a 100, 101, 110, ou 111).

Teorema: $D(EQ)=n$.

Prova. Assuma que $D(EQ)\leq n-1$. Isso significa que existe um $(x,x)$ e um $(x',x')$ com o mesmo histórico, $h$. Como esse histórico define um retângulo, $f(x,x')$ também deve ser 1. Por definição $x\neq x'$ e nós sabemos que igualdade apenas é verdadeira para $(a,b)$ quando $a=b$. Deste modo, nós temos uma contradição.

Intuitivamente, para $D(EQ)$ menor que $n$, precisamos definir um retângulo na matriz EQ de tamanho maior que uma célula. Todas as células nesse retângulo devem conter 1 para podermos generalizar que esse retângulo é igual a 1. Não é possível formar tal retângulo na matriz de igualdade.

Complexidade de comunicação aleatória

Na definição acima, estamos preocupados com o número de bits que devem ser transmitidos de forma determinística entre duas partes. Se ambas as partes tenham acesso a um gerador de números aleatórios, eles podem determinar o valor de $f$ com muito menos informações trocadas? Yao, em seu artigo seminal responde a esta pergunta, definindo complexidade de comunicação aleatória.

Um protocolo aleatório $R$ para uma função $f$ tem erro de dois lados.

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

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

Um protocolo aleatório é um protocolo determinístico que usa uma cadeia aleatória extra além de sua entrada normal. Há dois modelos para isso: uma “cadeia pública” é uma cadeia que é conhecida por ambas às partes previamente, enquanto uma “cadeia privada” é gerada por uma parte e deve ser comunicada à outra parte. O Teorema apresentado abaixo mostra que qualquer protocolo de cadeia pública pode ser simulado por um protocolo de cadeia privada que usa O(log n) bits adicionais comparado ao original.

Note que nas desigualdades de probabilidades acima, a saída do protocolo é entendida como dependendo “apenas” da cadeia aleatória; ambas cadeias x e y permanecem fixas. Em outras palavras, se R(x,y) produz g(x,y,r) ao usar uma cadeia aleatória r, então g(x,y,r) = f(x,y) por pelo menos metade de todas as escolhas para a cadeia r.

A complexidade aleatória é definida simplesmente como o número de bit trocados em tal protocolo.

Note que também é possível definir um protocolo aleatório com erro de um lado, e sua complexidade é definida similarmente.

Exemplo: EQ

Voltando ao exemplo anterior de EQ, se corretude não é necessária, Alice e Bob podem verificar igualdade utilizando apenas O(log n) mensagens. Considere o seguinte protocolo: Assuma que ambos Alice e Bob possuem acesso a mesmo cadeia aleatória $z\in \{0,1\}^{n}$.. Alice computa $z\cdot x$ e envia esse bit (vamos chamá-lo de b) para Bob. Então Bob compara b a $z\cdot y$. Se eles são iguais, então Bob aceita, dizendo que x é igual a y. Caso contrário, ele rejeita.

Claramente, se $x=y$, então $z\cdot x=z\cdot y$, logo $Prob_{z}[Aceitar]=1$.. Se x não é igual a y, ainda é possível que $z\cdot x=z\cdot y$, o que poderia dar a Bob a resposta errada. Como isso acontece?

Se x e y não são iguais, então eles devem diferir em alguns locais:

$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}$

Onde $x$ e $y$ batem, $z_{i}*x_{i}=z_{i}*c_{i}=z_{i}*y_{i}$, então estes termos afetam a igualdade dos produtos escalares. Podemos seguramente ignorar esses termos e olhar apenas para onde $x$ e $y$ diferem. Além disso, podemos trocar os bits $x_{i}$ e $y_{i}$ sem mudar se os produtos escalares são iguais ou não. Isso significa que podemos mudar bits para que $x$ contenha apenas zeros e $y$ contenha apenas uns:

$x'=00\ldots 0$

$y'=11\ldots 1$

$z'=z_{1}z_{2}\ldots z_{n'}$

Note que $z'\cdot x'=0$ e $z'\cdot y'=\Sigma _{i}z'_{i}$. Agora, a pergunta é: para alguma cadeia aleatória $z'$, qual a probabilidade de que $\Sigma _{i}z'_{i}=0$? Dado que cada $z'_{i}$ é igualmente provavél de ser $0$ ou $1$, essa probabilidade é apenas $1/2$. Deste modo, quando $x$ não é igual a $y$, $Prob_{z}[Aceitar]=1/2$. O algoritmo pode ser repetido várias vezes para melhorar sua precisão. Isso cumpre os requerimentos para um algoritmo de comunicação aleatória.

Isso mostra que se Alice e Bob compartilham uma cadeia aleatória de comprimento n, eles podem enviar um bit um para o outro para computar $EQ(x,y)$. Na próxima seção, é mostrado que Alice e Bob podem trocar apenas O(log n) bits que são tão bons como compartilhar uma cadeia aleatória de comprimento n. Uma vez que isso é mostrado, segue-se que EQ pode ser computada em O(log n) mensagens.

Protocolo público vs protocolo privado

É mais fácil criar protolocos aleatórios quando ambas as partes têm acesso à mesma cadeia aleatória (protocolo de cadeia compartilhada). Ainda é possível utilizar esses protocolos mesmo quando as duas partes não compartilham uma mesma cadeia aleatória (protocolo de cadeia privada) com um pequeno custo de comunicação. Qualquer protocolo aleatório de cadeia compartilhada usando uma cadeia de $n$ bits pode ser simulado por um protocolo de cadeia privada que usa O(log n) bits extras.

Intuitivamente, podemos encontrar algum conjunto de cadeias que tem aleatoriedade suficiente para rodar o protocolo aleatório com apenas um pequeno aumento no erro. Esse conjunto pode ser compartilhado de antemão, e ao invés de enviar uma cadeia aleatória, Alice e Bob precisam apenas concordar em qual cadeia escolher do conjunto compartilhado. Esse conjunto é pequeno o suficiente para que a escolha pode ser comunicada de forma eficiente. Segue-se uma prova formal.

Considere um protocolo aleatório P com uma taxa máxima de erro de 0,1. Seja $R$ 100$n$ cadeias de comprimento n, numeradas $r_{1},r_{2},\dots ,r_{100n}$. Dado tal $R$, defina um novo protocolo $P'_{R}$ que aleatoriamente escolhe algum $r_{i}$ e então roda P usando $r_{i}$ como a cadeia aleatória compartilhada. Leva O(log 100n) = O(log n) bits para comunicar a escolha de $r_{i}$.

Definimos $p(x,y)$ e $p'_{R}(x,y)$ como as probabilidades de que $P$ e $P'_{R}$ computem o valor correto para a entrada $(x,y)$.

Para um $(x,y)$ fixo, podemos usar a desigualdade de [Hoeffding para obter a seguinte equação:

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

Desta forma quando não temos $(x,y)$ fixo:

$\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$

A última igualdade acima se mantém porque existem $2^{2n}$ pares $(x,y)$ diferentes. Como a probabilidade não é igual a 1, há algum $R_{0}$ de modo que para todo $(x,y)$:

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

Como $P$ possui probabilidade de erro de no máximo 0,1, $P'_{R_{0}}$ pode ter no máximo 0,2 de probabilidade de erro.

Complexidade de comunicação quântica

A complexidade de comunicação quântica tenta quantificar a redução de comunicação possível usando efeitos quânticos durante computação distribuída.

Pelo menos três generalizações quânticas de complexidade de comunicação foram propostas; para um levantamento ver o texto sugerido por G. Brassard.

A primeira é que um modelo de comunicação qubit, em que as partes podem usar comunicação quântica ao invés da comunicação clássica, por exemplo trocando fótons através de uma fibra ótica.

Num segundo modelo a comunicação ainda é feita com bits clássicas, mas as partes são permitidas a manipular um suprimento ilimitado de estados quânticamente entrelaçados como parte de seus protocolos. Realizando mediçoes em seus estados entrelaçados, as partes podem economizar na comunicação clássica durante a computação distribuída.

O terceiro modelo envolve acesso a entrelaçamento previamente compartilhado além da comunicação qubit, e é o menos explorado dos três modelos quânticos.

Complexidade de comunicação não-determinística

Na complexidade de comunicação não-determinística, Alice e Bob têm acesso a um oráculo. Após receber a palavra do oráculo, as partes comunicam-se para inferir f(x,y). A complexidade de comunicação não-determinística é então o máximo sobre todos os pares (x,y) sobre a soma do número de bits trocados e o comprimento da codificação da palavra do oráculo.

Visto de outra forma, isso equivale a cobrir todas os entradas 1 da matriz 0/1 por 1-retângulos combinatórios (ou seja, submatrizes não convexas, não contínuas, cujas entradas são todas um (ver Kushilevitz e Nisan ou Dietzfelbinger et al. )).A complexidade de comunicação não-determinística é o logaritmo binário do número de retângulos cobrindo a matriz: o número mínimo de 1-retângulos combinatórios necessários para cobrir todas as entradas 1 da matriz, sem cobrir nenhuma entrada 0.

Complexidade de comunicação não-determinística ocorre como uma maneira de obter limitantes inferiores para complexidade de comunicação determinística (ver Dietzfelbinger et al.), mas também na teoria das matrizes não-negativas, onde ela fornece um limitante inferior no posto não-negativo de uma matriz não-negativa.

Problemas em aberto

Considerando-se uma matriz de entrada $M_{f}=[f(x,y)]_{x,y\in \{0,1\}^{n}}$, o número mínimo de bits trocados para calcular f deterministicamente no pior caso, $D(f)$, é limitado inferiormente pelo logaritmo do posto da matriz $M_{f}$. A conjectura do logaritmo do posto propõe que a complexidade de comunicação, $D(f)$, de $M_{f}$ é limitada superiormente por uma força constante do logaritmo do posto de $M_{f}$. Como D(f) é limitada tanto inferior como superiormente por um polinômio do log posto de $(M_{f})$, pode-se dizer que D(f) é polinomialmente relacionado ao log posto$(M_{f})$. Uma vez que o posto de uma matriz é computável em tempo polinomial no tamanho da matriz, tal limitante superior poderia permitir à complexidade de comunicação da matriz ser aproximada em tempo polinomial. Note que, no entanto, o tamanho da própria matriz é exponencial no tamanho da entrada.

Para um protocolo aleatório, o número de bits trocados no pior caso, R(f), é conjecturado como polinomialmente relacionado à seguinte fórmula:

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

Tais conjecturas log posto são valiosas porque elas reduzem a questão da complexidade de comunicação de uma matriz à questão das linhas linearmente independentes (colunas) da matriz. Isso revela que a essência do problema da complexidade de comunicação, por exemplo no caso EQ acima, é descobrir onde na matriz estão as entradas, a fim de descobrir se elas são equivalentes.

Aplicações

Limitantes inferiores na complexidade de comunicação podem ser usados para provar limitantes inferiores em modelos de árvore de decisão, circuitos VSLI, estruturas de dados, algoritmos de transmissão, trade-off de espaço-tempo para Máquinas de Turing e outros.

Referências

• Kushilevitz, E. and N. Nisan. Communication complexity. Cambridge University Press, 1997.
• Brassard, G. Quantum communication complexity: a survey. http://arxiv.org/abs/quant-ph/0101005
• Dietzfelbinger, M., J. Hromkovic, J., and G. Schnitger, "A comparison of two lower-bound methods for communication complexity", Theoret. Comput. Sci. 168, 1996. 39-51.
• Raz, Ran. "Circuit and Communication Complexity." In Computational Complexity Theory. Steven Rudich and Avi Wigderson, eds. American Mathematical Society Institute for Advanced Study, 2004. 129-137.
• A. C. Yao, "Some Complexity Questions Related to Distributed Computing", Proc. of 11th STOC, pp. 209–213, 1979. 14
• I. Newman, Private vs. Common Random Bits in Communication Complexity, Information Processing Letters 39, 1991, pp. 67–71.