Complexidade de comunicação de várias partes do “Problema com a Partição de Conjunto”

13

Em um aplicativo que estou considerando, preciso conhecer a complexidade da comunicação do seguinte problema:

Dado , seja o conjunto de números inteiros de a . Alice, Bob e Carol recebem um subconjunto de , denotado por , e , respectivamente. Eles querem verificar se , e formam uma partição de , ou seja, eles são disjuntos e sua união é . $n$ $S$ $1$ $n$ $S$ $A$ $B$ $C$ $A$ $B$ $C$ $S$ $S$

Estou particularmente interessado no caso de três partes, mas outros casos também seriam interessantes. Observe que, no caso de duas partes, o problema é equivalente ao problema de IGUALDADE, portanto, possui limite inferior para protocolos determinísticos, mas limite superior para protocolos aleatórios. $\Omega(n)$ $O(\log n)$

Minha pergunta é se esse problema é conhecido antes. Se você conhece algum problema que possa estar relacionado, também gostaria de saber.

cc.complexity-theory communication-complexity Danu
fonte

17

Um limite inferior linear no CC determinístico segue fixando um dos conjuntos para estar vazio.

Para um limite superior logarítmico aleatório, observe primeiro que esse problema pode ser reduzido ao problema perguntando se a soma de três números de bits é exatamente . Este pode ser resolvido em randomizados comunicação pelos jogadores mod um aleatória operacionais bits prime. $3n$ $2^{3n}-1$ $O(\log n)$ $O(\log n)$

Noam
fonte

Você não pode usar números de bits e obter um algoritmo que também funciona em um modelo de streaming? Para fazer isso funcionar, você também precisa verificar se o número total de itens está correto, mas isso é fácil de fazer. Carrega destrói uns, então a soma de potências de dois é igual a se e somente se houver exatamente uma cópia de cada potência de duas.

2^{n}

$2^n$

n

$n$

2^{n} - 1

$2^{n}-1$

Warren Schudy 15/10/10

1

Estou analisando uma questão um pouco diferente, que parece relacionada. Qual seria uma boa referência para detalhes sobre o limite superior aleatório na resposta acima?

Keren
fonte

1

talvez você deva postar outra pergunta?

Suresh Venkat

Para a resposta para o meu problema, você pode olhar para o protocolo aleatório para resolver o problema de igualdade para ter uma idéia. Por exemplo, Exemplo 3.5 no livro de Nissan-Kushilevitz. A idéia principal é usar impressões digitais, eu acho.

Danu

Complexidade de comunicação de várias partes do “Problema com a Partição de Conjunto”

Respostas: