Complexidade de comunicação
Da Wikipédia, a enciclopédia livre
Da Wikipédia, a enciclopédia livre
A noção de complexidade de comunicação foi introduzida por Yao em 1979,[1] 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.
Seja : X Y Z onde assumimos o caso típico em que e . Alice manda uma cadeia de n bits X enquanto Bob manda uma cadeia de n bits Y. Comunicando-se um com o outro bit-a-bit (adotando algum protocolo de comunicação), Alice e Bob querem computar o valor de 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 , é então definida como
Usando a definição acima, é útil pensar na função como uma matriz (chamada de matriz de entrada) onde cada linha da matriz corresponde a X e cada coluna corresponde a Y. Uma entrada na matriz de entrada é . Inicialmente tanto Alice como Bob tem uma cópia de toda a matriz A (assumindo que a função é 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 e . 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, . 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 X Y é chamado retângulo (combinatorial) se sempre que R e R então R. De forma equivalente, R também pode ser visto como uma submatriz da matriz de entrada A tal que R = M N onde M X e N Y. Considere o caso quando bits já foram trocados entre as partes. Agora, para um dado \in</math> , vamos definir uma matriz
Então, X Y, e é um retângulo e submatriz de A.
Nós consideramos o caso em que Alice e Bob tentam determinar se ambos possuem a mesma string. Isto é, estamos tentando determinar se é igual a . É fácil provar que o problema da igualdade sempre requer o envio de bits no pior caso se quiser-se ter certeza absoluta de que e são iguais. Considere o caso simples de e possuírem 3 bits. A função de igualdade neste caso pode ser representada pela matriz abaixo. As linhas representam todas as possibilidades de , as colunas representam as possibilidades de .
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 é igual a (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 é 1, é necessário apenas considerar metade das colunas (em que pode ser igual a 100, 101, 110, ou 111).
Teorema: .
Prova. Assuma que . Isso significa que existe um e um com o mesmo histórico, . Como esse histórico define um retângulo, também deve ser 1. Por definição e nós sabemos que igualdade apenas é verdadeira para quando . Deste modo, nós temos uma contradição.
Intuitivamente, para menor que , 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.
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 com muito menos informações trocadas? Yao, em seu artigo seminal[1] responde a esta pergunta, definindo complexidade de comunicação aleatória.
Um protocolo aleatório para uma função tem erro de dois lados.
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.
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 .. Alice computa e envia esse bit (vamos chamá-lo de b) para Bob. Então Bob compara b a . Se eles são iguais, então Bob aceita, dizendo que x é igual a y. Caso contrário, ele rejeita.
Claramente, se , então , logo .. Se x não é igual a y, ainda é possível que , 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:
Onde e batem, , então estes termos afetam a igualdade dos produtos escalares. Podemos seguramente ignorar esses termos e olhar apenas para onde e diferem. Além disso, podemos trocar os bits e sem mudar se os produtos escalares são iguais ou não. Isso significa que podemos mudar bits para que contenha apenas zeros e contenha apenas uns:
Note que e . Agora, a pergunta é: para alguma cadeia aleatória , qual a probabilidade de que ? Dado que cada é igualmente provavél de ser ou , essa probabilidade é apenas . Deste modo, quando não é igual a , . 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 . 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.
É 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 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 100 cadeias de comprimento n, numeradas . Dado tal , defina um novo protocolo que aleatoriamente escolhe algum e então roda P usando como a cadeia aleatória compartilhada. Leva O(log 100n) = O(log n) bits para comunicar a escolha de .
Definimos e como as probabilidades de que e computem o valor correto para a entrada .
Para um fixo, podemos usar a desigualdade de [Hoeffding para obter a seguinte equação:
Desta forma quando não temos fixo:
A última igualdade acima se mantém porque existem pares diferentes. Como a probabilidade não é igual a 1, há algum de modo que para todo :
Como possui probabilidade de erro de no máximo 0,1, pode ter no máximo 0,2 de probabilidade de erro.
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.
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.[2]
Considerando-se uma matriz de entrada , o número mínimo de bits trocados para calcular f deterministicamente no pior caso, , é limitado inferiormente pelo logaritmo do posto da matriz . A conjectura do logaritmo do posto propõe que a complexidade de comunicação, , de é limitada superiormente por uma força constante do logaritmo do posto de . Como D(f) é limitada tanto inferior como superiormente por um polinômio do log posto de , pode-se dizer que D(f) é polinomialmente relacionado ao log posto. 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:
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.
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.