A complexidade da comunicação ou complexidade da comunicação é um conceito estudado na ciência da computação teórica . O dispositivo abstrato clássico é o seguinte: Alice e Bob têm uma mensagem cada um e desejam calcular uma nova mensagem a partir de suas mensagens, transmitindo um mínimo de informações um para o outro. Por exemplo, Alice e Bob recebem uma palavra cada e devem decidir se receberam a mesma palavra; eles podem, é claro, enviar sua palavra um ao outro e comparar, mas o objetivo é minimizar o número de mensagens.
Usar um recurso de comunicação é o ato de enviar informações para outro. Alice pode, portanto, enviar a primeira letra de sua palavra para bob, isso tem um custo de 1.
O objetivo da teoria da complexidade da comunicação é, portanto, calcular quais são os recursos de comunicação necessários para realizar certas tarefas em um contexto de computação distribuída . Ao contrário da teoria clássica da complexidade , não contamos os recursos necessários para os cálculos ( tempo e espaço, por exemplo).
Este conceito foi definido em 1979 por Andrew Yao e é usado em particular para o estudo de algoritmos on-line e o projeto de circuitos VLSI .
Deixe três conjuntos , e , e uma função , normalmente e . Alice obtém um item de e Bob obtém um item de , e eles querem calcular (Alice e Bob são chamados de "jogadores").
Um protocolo que calcula é uma decomposição de etapas. Em cada etapa, Alice (resp. Bob) calcula de acordo com sua entrada e os bits já trocados e decide encerrar porque ela concluiu o cálculo ou enviar um bit para Bob (resp. Alice). Um protocolo é geralmente representado na forma de uma árvore. Um exemplo é dado abaixo. Os nós da árvore são rotulados se é Alice quem calcula ou se é Bob. As arestas são rotuladas como 1 se o bit enviado for 1 e zero se for zero.
Dependendo dos modelos, pode-se aceitar um protocolo correto apenas com boa probabilidade ou mesmo usando bits quânticos. Também existem generalizações com mais de dois jogadores.
A complexidade de um protocolo é o número de bits trocados no pior caso. Na árvore que representa o protocolo, a complexidade do protocolo é a profundidade da árvore.
No exemplo anterior, o protocolo tem um custo de três.
No caso determinístico, a complexidade de comunicação de uma função , denotada , é o número de bits trocados usando um protocolo determinístico. Este é o conceito mais clássico e o mais restritivo dos três conceitos aqui definidos.
No caso probabilístico, notamos a complexidade (para randomizado ). Nesse caso, Alice e Bob podem usar fontes de bits aleatórios para fazer seus cálculos (como nos algoritmos probabilísticos ), e o protocolo é considerado satisfatório se a probabilidade de uma resposta correta for maior do que uma certa constante. Dependendo do modelo, os jogadores podem compartilhar suas fontes de bits aleatórios (falamos de protocolo de moeda pública ) ou não ( protocolo de moeda privada ).
Existem vários modelos de complexidade de comunicação usando noções de computação quântica , em particular trocando qubits em vez de bits, ou mesmo compartilhando qubits emaranhados .
Na teoria da complexidade mais clássica, provar limites inferiores na dificuldade dos problemas pode ser muito difícil, como ilustrado pelo problema P = NP . Às vezes, é fácil obter limites inferiores para a complexidade da comunicação. Existem dois métodos clássicos para isso.
Um rectângulo combinatória é o produto de um subconjunto de e um subconjunto de tal modo que:
Um protocolo cria uma partição retângulo combinatória graças ao fato de que o conjunto de elementos é um retângulo combinatório. Ao chamar (rep. ) O conjunto de elementos de (resp. ) Tal como um elemento de (rep. ), Todos os elementos ( , ) têm a mesma resposta. A ideia é que (resp. ) Conduza à folha para os nós de Alice (resp. Bob).
Portanto, se provarmos que não há partição em menos de n retângulos combinatórios, o custo mínimo de um protocolo é de pelo menos .
A classificação da matriz acima também é uma fonte de limites inferiores.
A propriedade do Logrank é a seguinte:
o custo mínimo de um protocolo éO inverso é uma conjectura e não foi demonstrado até o momento.
Queremos calcular , que é igual a 1 se e 0 caso contrário.
Um protocolo simples é para Alice enviar a Bob e Bob calcular o resultado e enviá-lo de volta. Esse protocolo tem um custo de (Alice envia bits e Bob deve enviar um). A árvore deste protocolo é o exemplo dado anteriormente.
Podemos mostrar que este protocolo é ótimo no caso determinístico (o que podemos mostrar graças à propriedade usando retângulos combinatórios acima), mas há um protocolo mais eficiente no caso probabilístico (que usa uma função hash).
Queremos calcular , que é igual a 1 se (onde e são interpretados como uma matriz de conjuntos de definição de Booleanos) e 0 caso contrário.
Um protocolo simples é, como antes, Alice enviar a Bob e Bob retornar o resultado. A complexidade é novamente .
Este protocolo é ótimo no caso determinístico, mas existe um algoritmo melhor no caso probabilístico (mas também linear).
A complexidade da comunicação foi inventada em 1979 por Andrew Yao no artigo Algumas questões de complexidade relacionadas à computação distribuída . Yao recebeu o Prêmio Turing em 2000 por seu trabalho, particularmente nesta área.
Os resultados da complexidade da comunicação são usados no campo teórico para fazer a ligação entre os limites inferiores resultantes de diferentes modelos computacionais, como máquinas de Turing , árvores de decisão, programas de ramificação etc. ; vimos um exemplo acima.
Também é possível obter limites para algoritmos de mineração de dados e algoritmos online .
Um exemplo de aplicação da complexidade da comunicação é uma prova de limite inferior do número de estados de um autômato finito .
Supomos que temos um autômato que reconhece a linguagem . Podemos então construir um protocolo com bits de comunicação:
No entanto, vimos que para resolver , precisamos de pelo menos bits de comunicação, portanto , portanto ,