Número da partição do protocolo e complexidade determinística da comunicação

22

Além da complexidade (determinística) da comunicação de uma relação R , outra medida básica para a quantidade de comunicação necessária é o número da partição do protocolo p p ( R ) . A relação entre essas duas medidas é conhecida até um fator constante. A monografia de Kushilevitz e Nisan (1997) fornececc(R)R pp(R)

cc(R)/3log2(pp(R))cc(R).

Em relação à segunda desigualdade, é fácil dar (uma família infinita de) relações com log 2 ( p p ( R ) ) = c c ( R ) .Rlog2(pp(R))=cc(R)

Em relação à primeira desigualdade, Doerr (1999) mostrou que podemos substituir o fator no primeiro limite por c = 2,223 . Até que ponto o primeiro limite pode ser aprimorado, se é que existe? c=3c=2.223

Motivação adicional da complexidade descritiva: Melhorar a constante resultará em um limite inferior aprimorado no tamanho mínimo de expressões regulares equivalentes a um DFA que descreve uma linguagem finita, veja Gruber e Johannsen (2008). 2.223

Embora não esteja diretamente relacionado a essa questão, Kushilevitz, Linial e Ostrovsky (1999) deram relações com c c ( R ) / ( 2 - o ( 1 ) ) log 2 ( r p ( R ) ) , onde r p ( R ) é o número da partição retangular .Rcc(R)/(2o(1))log2(rp(R))rp(R)

EDIT: Observe que a pergunta acima é equivalente à seguinte pergunta na complexidade do circuito booleano: Qual é a constante ideal tal modo que toda fórmula booleana DeMorgan de tamanho de folha L pode ser transformada em uma fórmula equivalente de profundidade no máximo c log 2 L ?cclog2L

Referências :

  • Kushilevitz, Eyal; Nisan, Noam: Complexidade da Comunicação. Cambridge University Press, 1997.
  • Kushilevitz, Eyal; Linial, Nathan; Ostrovsky, Rafail: A conjectura de matriz linear na complexidade da comunicação é falsa, Combinatorica 19 (2): 241-254, 1999.
  • Doerr, Benjamin: Complexidade da Comunicação e o Número da Partição de Protocolo, Relatório Técnico 99-28, Berichtsreihe des Mathematischen Seminars der Universität Kiel, 1999.
  • Gruber, Hermann; Johannsen, Jan: Limites inferiores ótimos no tamanho da expressão regular usando a complexidade da comunicação. In: Fundamentos das estruturas de ciência e computação de software 2008 (FoSSaCS 2008), LNCS 4962, 273-286. Springer.
Hermann Gruber
fonte
Não sabia da segunda referência, tentei pesquisar no Google e não encontrei uma versão online. Você tem um link?
Marcos Villagra
esta é a página inicial do autor? mpi-inf.mpg.de/~doerr
Marcos Villagra
Sim, esta é a página inicial do autor. O link do citeseerX que usei para baixar o artigo parece ter sumido. Você pode perguntar na sua biblioteca se eles podem obter uma cópia impressa; mas talvez seja melhor perguntar ao autor se ele deseja colocá-lo em sua página inicial ou no arxiv.
Hermann Gruber
2
A única coisa recente que pode ser útil que eu conheço é este documento lab2.kuis.kyoto-u.ac.jp/~kenya/MFCS2010.pdf .
precisa saber é o seguinte
2
Eu realmente não entendo o que você está oferecendo a recompensa. Você quer uma constante menor em vez de 3? Você citam o papel se Doerr onde é melhorado para 2.223 ...
domotorp

Respostas:

10

cc(R)2log2(pp(R))

Indireto, suponha que exista um R para o qual isso não seja verdade e tomemos o R com o menor pp (R) possível que viole a desigualdade. Basicamente, temos que mostrar que, usando dois bits, podemos reduzir pela metade o número de folhas em todos os quatro resultados da árvore de protocolos, e então terminamos usando a indução.

××××

Agora sabemos que L + R> 1/2, L, R <1/2 e sem perda de generalidade, podemos supor que L seja no máximo R. Também sabemos D = A + B + C <1/2. Segue-se que 2L + A + B <1, do qual sabemos que L + A <1/2 ou L + B <1/2, esses serão nossos dois casos.

Caso L + A <1/2: Primeiro Bob diz se sua entrada pertence a Y0 ou não. Caso contrário, temos no máximo D <1/2 folhas restantes. Se isso acontecer, Alice diz se sua entrada pertence ou não a XR. Caso contrário, temos no máximo L + A <1/2 folhas restantes. Se isso acontecer, então temos R <1/2 folhas restantes.

Caso L + B <1/2: Primeiro Alice diz se sua entrada pertence ou não a XR. Se isso acontecer, Bob diz se ele pertence a Y0 ou não, dependendo disso, temos R ou B restantes. Se a entrada de Alice não estiver no XR, ela informará se a entrada está em XL ou não. Se for, então temos L + B <1/2 folhas restantes. Caso contrário, temos no máximo D <1/2 folhas restantes.

Em todos os casos, terminamos. Diz-me o que pensas.

domotorp
fonte
1
2L+A+B1L+R+A+B+C=1C0LR
3

c2c1.73

Referências

Stasys Jukna. Complexidade da função booleana: avanços e fronteiras. Springer, 2012.

VM Khrapchenko. Sobre uma relação entre a complexidade e a profundidade. Metody Diskretnogo Analiza in Synthezis of Control Systems 32: 76–94, 1978.

Hermann Gruber
fonte
1
Este capítulo é sobre fórmulas e não a complexidade da comunicação, mas as provas são realmente parecidas. Esses problemas são equivalentes?
11116 Domotorp
Sim, esses problemas são equivalentes. A prova é via Karchmer-Wigderson-games. Veja, por exemplo, o Teorema 3.13 no livro de Jukna. (Observe que a equivalência vale para fórmulas DeMorgan, não para fórmulas gerais boolean sobre a base total.)
Hermann Gruber
Nos jogos de KW, o objetivo é encontrar uma coordenada diferente se a promessa é que f (x) difere de f (y), portanto é bem diferente da complexidade da comunicação em geral.
domotorp