Problemas de comunicação para os quais não se sabe que um teorema determinístico de soma direta

10

É um problema em aberto velho se um direto de soma teorema vale para a complexidade de comunicação determinística, isto é, se resolver instâncias independentes de um problema é t vezes mais difícil do que resolver uma única instância. [FKNN95] mostrou os seguintes resultados:tt

  • Resultado negativo: existe uma função parcial (devido a [O90]) cuja complexidade de comunicação determinística é , mas computá-la em t instâncias independentes possui complexidade Θ ( t + log t log n ) .Θ(registron)tΘ(t+registrotregistron)
  • Um resultado positivo: para todas as funções , se a complexidade determinística da comunicação de f é c , a complexidade da computação de f em t instâncias independentes é pelo menos Ω ( t ( ffcft.Ω(t(c-registron))

Não conheço outros resultados positivos gerais sobre o problema da soma direta. No entanto, parece que para problemas específicos que geralmente são considerados na complexidade da comunicação, por exemplo, igualdade ou disjunção, um teorema de soma direta é conhecido por manter.

Minha pergunta é: existem outros exemplos de problemas para os quais um teorema da complexidade da comunicação determinística não é conhecido por conter, ou mesmo conhecido por não conter (além da função de [O90])?

Referências:

[FKNN95] Tomás Feder, Eyal Kushilevitz, Moni Naor, Noam Nisan: complexidade de comunicação amortizada. SIAM J. Comput. 24 (4): 736-750 (1995)

[O90] Duas mensagens são quase ideais para transmitir informações. Alon Orlitsky. PODC, página 219-232. ACM, (1990)

Ou Meir
fonte

Respostas:

5

nπEuS3Eusgn(πEu)sgn(πEu)πEu

Ω(n)

Vsevolod Oparin
fonte