Quão difícil é comunicar?
Andreia Teixeira
27 de Maio
Complexidade de Comunicação
x
y
f(x,y)=?
Um Protocolo Simples
x
f(x,y) = z
Quantos bits são necessários para esta comunicação?
Complexidade de Comunicação
f: X  Y → {0,1}
Um protocolo P de domínio X  Y e contra-domínio {0,1} é uma
árvore binária, onde cada nó é etiquetado por uma função
av : X → {0,1} ou por uma função bv : Y → {0,1} e cada folha é
etiquetada com um elemento z  {0,1}.
Exemplo:
X = {x, x’, x’’, x’’’}
Y = {y, y’, y’’, y’’’}
f(x,y)
y
y'
y''
y'''
x
0
0
0
1
x'
0
0
0
1
x''
0
1
1
1
x'''
0
0
0
0
O Protocolo
a1(x)=0
a1(x’)=0
a1(x’’)=1
a1(x’’’)=1
0
1
b2(y)=0
b2(y’)=0
b2(y’’)=0
b2(y’’’)=1
0
O
b3(y)=1
b3(y’)=0
b3(y’’)=0
b3(y’’’)=0
1
0
1
a4(x)=0
a4(x’)=0
a4(x’’)=0
a4(x’’’)=1
1
0
1
O
1
O
O
f(x,y)
y
y'
y''
y'''
x
0
0
0
1
x'
0
0
0
1
x''
0
1
1
1
x'''
0
0
0
0
O Protocolo
a1(x)=0
a1(x’)=0
a1(x’’)=1
a1(x’’’)=1
0
1
b2(y)=0
b2(y’)=0
b2(y’’)=0
b2(y’’’)=1
0
O
b3(y)=1
b3(y’)=0
b3(y’’)=0
b3(y’’’)=0
1
0
1
a4(x)=0
a4(x’)=0
a4(x’’)=0
a4(x’’’)=1
1
0
1
O
1
O
O
f(x,y)
y
y'
y''
y'''
x
0
0
0
1
x'
0
0
0
1
x''
0
1
1
1
x'''
0
0
0
0
O Protocolo
a1(x)=0
a1(x’)=0
a1(x’’)=1
a1(x’’’)=1
0
1
b2(y)=0
b2(y’)=0
b2(y’’)=0
b2(y’’’)=1
0
O
b3(y)=1
b3(y’)=0
b3(y’’)=0
b3(y’’’)=0
1
0
1
a4(x)=0
a4(x’)=0
a4(x’’)=0
a4(x’’’)=1
1
0
1
O
1
O
O
f(x,y)
y
y'
y''
y'''
x
0
0
0
1
x'
0
0
0
1
x''
0
1
1
1
x'''
0
0
0
0
O Protocolo
a1(x)=0
a1(x’)=0
a1(x’’)=1
a1(x’’’)=1
0
1
b2(y)=0
b2(y’)=0
b2(y’’)=0
b2(y’’’)=1
0
O
b3(y)=1
b3(y’)=0
b3(y’’)=0
b3(y’’’)=0
1
0
1
a4(x)=0
a4(x’)=0
a4(x’’)=0
a4(x’’’)=1
1
0
1
O
1
O
O
f(x,y)
y
y'
y''
y'''
x
0
0
0
1
x'
0
0
0
1
x''
0
1
1
1
x'''
0
0
0
0
O Protocolo
a1(x)=0
a1(x’)=0
a1(x’’)=1
a1(x’’’)=1
0
1
b2(y)=0
b2(y’)=0
b2(y’’)=0
b2(y’’’)=1
0
O
b3(y)=1
b3(y’)=0
b3(y’’)=0
b3(y’’’)=0
1
0
1
a4(x)=0
a4(x’)=0
a4(x’’)=0
a4(x’’’)=1
1
0
1
O
1
O
O
f(x,y)
y
y'
y''
y'''
x
0
0
0
1
x'
0
0
0
1
x''
0
1
1
1
x'''
0
0
0
0
O Protocolo
a1(x)=0
a1(x’)=0
a1(x’’)=1
a1(x’’’)=1
0
1
b2(y)=0
b2(y’)=0
b2(y’’)=0
b2(y’’’)=1
0
O
O custo do Protocolo para o
input (x’’,y) é o tamanho do
caminho percorrido: 2.
b3(y)=1
b3(y’)=0
b3(y’’)=0
b3(y’’’)=0
1
0
1
a4(x)=0
a4(x’)=0
a4(x’’)=0
a4(x’’’)=1
1
0
1
O
1
O
O
Complexidade de Comunicação
O custo de um protocolo P , DP f, corresponde à altura da árvore
binária associada ao protocolo.
Para uma função f: X  Y  {0,1}, a complexidade de comunicação, D(f),
(determinística) de f é o min {DP f : P é um protocolo para f}.
Para toda a função f: X  Y  {0,1}, D(f) ≤ log |X| + 1.
Rectângulos Combinatórios
Dado um conjunto finito R, um rectângulo combinatório é um conjunto
A  B, onde A e B são subconjuntos de R.
Um rectângulo combinatório A  B é denominado z-monocromático se
tem o mesmo valor z (0 ou 1) para todo o a  A e b  B.
Rectângulos Combinatórios
Qualquer protocolo P para uma função f induz uma partição de
X  Y em rectângulos z-monocromáticos (z  {0,1}). O número destes
rectângulos é igual ao número de folhas de P.
f(x,y)
y
y'
y''
y'''
x
0
0
0
1
x'
0
0
0
1
x''
0
1
1
1
x'''
0
0
0
0
O Protocolo
a1(x)=0
a1(x’)=0
a1(x’’)=1
a1(x’’’)=1
0
1
b2(y)=0
b2(y’)=0
b2(y’’)=0
b2(y’’’)=1
0
O
b3(y)=1
b3(y’)=0
b3(y’’)=0
b3(y’’’)=0
1
0
1
a4(x)=0
a4(x’)=0
a4(x’’)=0
a4(x’’’)=1
1
0
1
O
1
O
O
f(x,y)
y
y'
y''
y'''
x
0
0
0
1
x'
0
0
0
1
x''
0
1
1
1
x'''
0
0
0
0
O Protocolo
a1(x)=0
a1(x’)=0
a1(x’’)=1
a1(x’’’)=1
0
1
b2(y)=0
b2(y’)=0
b2(y’’)=0
b2(y’’’)=1
0
O
b3(y)=1
b3(y’)=0
b3(y’’)=0
b3(y’’’)=0
1
0
1
a4(x)=0
a4(x’)=0
a4(x’’)=0
a4(x’’’)=1
1
0
1
O
1
O
O
f(x,y)
y
y'
y''
y'''
x
0
0
0
1
x'
0
0
0
1
x''
0
1
1
1
x'''
0
0
0
0
O Protocolo
a1(x)=0
a1(x’)=0
a1(x’’)=1
a1(x’’’)=1
0
1
b2(y)=0
b2(y’)=0
b2(y’’)=0
b2(y’’’)=1
0
O
b3(y)=1
b3(y’)=0
b3(y’’)=0
b3(y’’’)=0
1
0
1
a4(x)=0
a4(x’)=0
a4(x’’)=0
a4(x’’’)=1
1
0
1
O
1
O
O
f(x,y)
y
y'
y''
y'''
x
0
0
0
1
x'
0
0
0
1
x''
0
1
1
1
x'''
0
0
0
0
O Protocolo
a1(x)=0
a1(x’)=0
a1(x’’)=1
a1(x’’’)=1
0
1
b2(y)=0
b2(y’)=0
b2(y’’)=0
b2(y’’’)=1
0
O
b3(y)=1
b3(y’)=0
b3(y’’)=0
b3(y’’’)=0
1
0
1
a4(x)=0
a4(x’)=0
a4(x’’)=0
a4(x’’’)=1
1
0
1
O
1
O
O
f(x,y)
y
y'
y''
y'''
x
0
0
0
1
x'
0
0
0
1
x''
0
1
1
1
x'''
0
0
0
0
O Protocolo
a1(x)=0
a1(x’)=0
a1(x’’)=1
a1(x’’’)=1
0
1
b2(y)=0
b2(y’)=0
b2(y’’)=0
b2(y’’’)=1
0
O
b3(y)=1
b3(y’)=0
b3(y’’)=0
b3(y’’’)=0
1
0
1
a4(x)=0
a4(x’)=0
a4(x’’)=0
a4(x’’’)=1
1
0
1
O
1
O
O
f(x,y)
y
y'
y''
y'''
x
0
0
0
1
x'
0
0
0
1
x''
0
1
1
1
x'''
0
0
0
0
O Protocolo
a1(x)=0
a1(x’)=0
a1(x’’)=1
a1(x’’’)=1
0
1
b2(y)=0
b2(y’)=0
b2(y’’)=0
b2(y’’’)=1
0
O
b3(y)=1
b3(y’)=0
b3(y’’)=0
b3(y’’’)=0
1
0
1
a4(x)=0
a4(x’)=0
a4(x’’)=0
a4(x’’’)=1
1
0
1
O
1
O
O
f(x,y)
y
y'
y''
y'''
x
0
0
0
1
x'
0
0
0
1
x''
0
1
1
1
x'''
0
0
0
0
O Protocolo
a1(x)=0
a1(x’)=0
a1(x’’)=1
a1(x’’’)=1
0
1
b2(y)=0
b2(y’)=0
b2(y’’)=0
b2(y’’’)=1
0
O
b3(y)=1
b3(y’)=0
b3(y’’)=0
b3(y’’’)=0
1
0
1
a4(x)=0
a4(x’)=0
a4(x’’)=0
a4(x’’’)=1
1
0
1
O
1
O
O
f(x,y)
y
y'
y''
y'''
x
0
0
0
1
x'
0
0
0
1
x''
0
1
1
1
x'''
0
0
0
0
O Protocolo
a1(x)=0
a1(x’)=0
a1(x’’)=1
a1(x’’’)=1
0
1
b2(y)=0
b2(y’)=0
b2(y’’)=0
b2(y’’’)=1
0
O
b3(y)=1
b3(y’)=0
b3(y’’)=0
b3(y’’’)=0
1
0
1
a4(x)=0
a4(x’)=0
a4(x’’)=0
a4(x’’’)=1
1
0
1
O
1
O
O
f(x,y)
y
y'
y''
y'''
x
0
0
0
1
x'
0
0
0
1
x''
0
1
1
1
x'''
0
0
0
0
O Protocolo
a1(x)=0
a1(x’)=0
a1(x’’)=1
a1(x’’’)=1
0
1
b2(y)=0
b2(y’)=0
b2(y’’)=0
b2(y’’’)=1
0
O
b3(y)=1
b3(y’)=0
b3(y’’)=0
b3(y’’’)=0
1
0
1
a4(x)=0
a4(x’)=0
a4(x’’)=0
a4(x’’’)=1
1
0
1
O
1
O
O
f(x,y)
y
y'
y''
y'''
x
0
0
0
1
x'
0
0
0
1
x''
0
1
1
1
x'''
0
0
0
0
O Protocolo
a1(x)=0
a1(x’)=0
a1(x’’)=1
a1(x’’’)=1
0
1
b2(y)=0
b2(y’)=0
b2(y’’)=0
b2(y’’’)=1
0
O
b3(y)=1
b3(y’)=0
b3(y’’)=0
b3(y’’’)=0
1
0
1
a4(x)=0
a4(x’)=0
a4(x’’)=0
a4(x’’’)=1
1
0
1
O
1
O
O
f(x,y)
y
y'
y''
y'''
x
0
0
0
1
x'
0
0
0
1
x''
0
1
1
1
x'''
0
0
0
0
O Protocolo
a1(x)=0
a1(x’)=0
a1(x’’)=1
a1(x’’’)=1
0
1
b2(y)=0
b2(y’)=0
b2(y’’)=0
b2(y’’’)=1
0
O
b3(y)=1
b3(y’)=0
b3(y’’)=0
b3(y’’’)=0
1
0
1
a4(x)=0
a4(x’)=0
a4(x’’)=0
a4(x’’’)=1
1
0
1
O
1
O
f(x,y)
y
y'
y''
y'''
x
0
1
0
0
x'
0
1
0
0
x''
1
1
1
1
x'''
1
0
1
0
Exemplo
a1(x)=0
a1(x’)=0
a1(x’’)=0
a1(x’’’)=1
0
1
b2(y)=0
b2(y’)=1
b2(y’’)=0
b2(y’’’)=0
0
1
a4(x)=0
a4(x’)=0
a4(x’’)=1
a4(x’’’)=1
0
O
b3(y)=1
b3(y’)=0
b3(y’’)=1
b3(y’’’)=0
1
1
1
0
O
1
1
Propriedades
Seja P um protocolo e v um nó da árvore associada ao protocolo. Rv é o conjunto
dos inputs (x,y) que alcançam o nó v.
Se L é o conjunto das folhas de um protocolo P, então {Rl}lЄL é uma partição de
X  Y.
R ⊆ X  Y é um rectângulo se e só se
(x1,y1)  R e (x2,y2)  R ⇒ (x1,y2)  R
Propriedades
Seja P um protocolo e v um nó da árvore associada ao protocolo. Rv é o conjunto
dos inputs (x,y) que alcançam o nó v.
Se L é o conjunto das folhas de um protocolo P, então {Rl}lЄL é uma partição de
X  Y.
R ⊆ X  Y é um rectângulo se e só se
(x1,y1)  R e (x2,y2)  R ⇒ (x1,y2)  R
Minorante da D(f)
Se qualquer partição de X  Y em rectângulos monocromáticos
necessita de pelo menos t rectângulos então D(f) ≥ ⌈log t⌉.
Técnicas
•
Conjuntos Enganadores
•
Tamanho dos Rectângulos
•
Característica da Matriz
Conjuntos Enganadores
Seja f: X  Y → {0,1}. Um conjunto S ⊂ X  Y é denominado de conjunto enganador
(para f) se existe um valor z  {0,1} tal que
• Para todo (x,y)  S, f(x,y) = z.
• Para dois quaisquer pares distintos (x1,y1) e (x2,y2) em S,
f(x1,y2) ≠ z ou f(x2,y1) ≠ z.
Se f tem um conjunto enganador S de tamanho t, então D(f) ≥ log t.
Conjuntos Enganadores
Seja f: X  Y → {0,1}. Um conjunto S ⊂ X  Y é denominado de conjunto enganador
(para f) se existe um valor z  {0,1} tal que
• Para todo (x,y)  S, f(x,y) = z.
• Para dois quaisquer pares distintos (x1,y1) e (x2,y2) em S,
f(x1,y2) ≠ z ou f(x2,y1) ≠ z.
Se f tem um conjunto enganador S de tamanho t, então D(f) ≥ log t.
Conjuntos Enganadores
Exemplo: x, y
EQ(x,y) =

{0,1}n
1 se x = y
0 caso contrário
Um conjunto enganador de tamanho 2n é
S1={(α, α) : α

{0,1}n }
D(EQ) ≥ n. Considerando os 0-rectângulos monocromáticos,
concluímos que D(EQ) ≥ n+1.
Como D(EQ) ≤ n+1, temos que D(EQ) = n+1.
Tamanho dos Rectângulos
Seja μ uma distribuição de probabilidade de X  Y. Se qualquer rectângulo R
z-monocromático (z  {0,1}) tem medida μ(R) ≤ δ, então D(f) ≥ log 1/δ.
Exemplo: x, y
EQ(x,y) =

{0,1}n
1 se x = y
0 caso contrário
f(x,y)
x
x'
x''
x'''
…
x
1
0
0
0
x'
0
1
0
0
x'' x'''
0
0
0
0
1
0
0
1
…
Tamanho dos Rectângulos
Seja μ uma distribuição de probabilidade de X  Y. Se qualquer rectângulo R
z-monocromático (z  {0,1}) tem medida μ(R) ≤ δ, então D(f) ≥ log 1/δ.
Exemplo: x, y
EQ(x,y) =

{0,1}n
1 se x = y
0 caso contrário
f(x,y)
x
x'
x''
x'''
…
x
1
0
0
0
x'
0
1
0
0
x'' x'''
0
0
0
0
1 0
0
1
…
Como cada rectângulo R 1-monocromático tem dimensões 1 x 1,
temos que μ(R) ≤ 1/2n . Como existe, pelo menos um rectângulo 0monocromático, D(EQ) ≥ log 2n +1 = n + 1.
Como D(EQ) ≤ n+1, temos que D(EQ) = n+1.
Característica
Para qualquer função f:X  Y → {0,1}, D(f) ≥ log car(Mf) , onde Mf é a matriz
associada à função f.
Exemplo: x, y
EQ(x,y) =

{0,1}n
1 se x = y
0 caso contrário
M(EQ)=
1
0
0
0
…
0
1
0
0
0
0
1
0
0
0
0
1
Como M(EQ) = 2n , temos que D(EQ) ≥ n.
…
Característica
Para qualquer função f: X  Y → {0,1}, D(f) ≥ log car(f) , onde car(f) é a característica
da matriz associada à função f.
Exemplo: x, y
EQ(x,y) =

{0,1}n
1 se x = y
0 caso contrário
M(EQ)=
1
0
0
0
…
0
1
0
0
0
0
1
0
0
0
0
1
Como M(EQ) = 2n , temos que D(EQ) ≥ n.
…
Obrigada!
Complexidade de Comunicação
O custo de um protocolo P , DP f, corresponde à altura da árvore
binária associada ao protocolo.
Para uma função f: X  Y  {0,1}, a complexidade de comunicação, D(f),
(determinística) de f é o min {DP f : P é um protocolo para f}.
Para toda a função f: X  Y  {0,1}, D(f) ≤ log |x| + log |z|.
Propriedades
Prova: (⇒) Considere-se um rectângulo R, isto é, R= A  B, para A ⊆ X e B ⊆ Y.
Pretende-se mostrar que se (x1,y1) e (x2,y2) pertencem a R então (x1,y2)
também pertence a R. Se (x1,y1) Є R, então x1  A e y1  B. Do mesmo modo,
se (x2,y2)  R, então x2  A e y2  B. Portanto, os pares (x1,y2) e (x2,y1).
pertencem a A  B = R.
(⇐ ) Considerem-se os seguintes conjuntos:
A = { x: existe y tal que (x,y)  R} e B = { y: existe x tal que (x,y)  R}.
Por definição de A e B é, evidente, que R ⊆ A  B, pois se (x,y)  R, então x  A
e y  B e, portanto (x,y)  A  B.
Para se mostrar que A  B ⊆ R, considere-se
(x,y)  A  B. Como x  A, então existe y'  B tal que (x,y')  R. Analogamente,
como y  B, então existe x'  A tal que (x',y)  R. Logo (x,y')  R e (x',y)  R.
Assim, por hipótese resulta que (x,y)  R. Portanto A  B ⊆ R.
Conjuntos Enganadores
Prova:
Qualquer rectângulo R que contenha dois pontos distintos (x1,y1) e (x2,y2),
ambos pertencentes a S, também contém os pontos (x1,y2) e (x2,y1). No entanto,
S é um conjunto enganador, logo o valor de f em (x1,y1) e (x2,y2) é z e, pelo
menos, um dos pontos (x1,y2) ou (x2,y1) tem valor por f diferente de z. Logo R não
é monocromático. Assim, nenhum rectângulo monocromático contém mais do
que um elemento de S. Logo, são necessários, pelo menos, t rectângulos para
fazer uma partição de S. Logo vem que D(f) ≥ ⌈log t⌉.
Característica
Prova: Seja P um protocolo para a função f e seja L o conjunto de folhas para as
quais f(x,y)=1. Define-se uma matriz Ml para cada uma das folhas, de tal
maneira que Ml(x,y)=1 se (x,y)  Rl e Ml(x,y)=0 se (x,y)  Rl, onde os rectângulos
Rl correspondem aos pares (x,y) que ``terminam'' na folha l. A matriz da função
é a soma de todas as matrizes definidas para cada uma das folhas l  L, isto é,
Mf = ∑ Ml. Usando as propriedades da característica de uma matriz, vem que
car(Mf) ≤ ∑ car(Ml). Como car(Ml) = 1 vem que car(Mf) ≤ |L|. Qualquer protocolo
P tem de ter, pelo menos, car(Mf) folhas, logo D(f) ≥ ⌈log(car(Mf))⌉.