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

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) fornece$cc(R)$$R$ $pp(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 ) .$R$$\log_2(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=3$$c=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 .$R$$cc(R)/(2-o(1)) \ge \log_2(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 ?$c$$c \log_2L$

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.

$cc(R)\le 2\log_2(pp(R))$$\le$

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.

$\times$$\times$$\times$$\times$

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.

$c\le 2$$c \le 1.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.