Complexidade de comunicação

A noção de complexidade de comunicação foi introduzida por 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.