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 idéia aqui é encontrar maneiras inteligentes de calcular f com menos de n bits de comunicação.