La complejidad de la comunicación multipartita de "Establecer problema de partición"

13

En una aplicación que estoy considerando, necesito saber la complejidad de comunicación del siguiente problema:

Dado , sea el conjunto de enteros de a . Alice, Bob y Carol reciben cada uno un subconjunto de , denotado por , y , respectivamente. Ellos quieren comprobar si , y forman una partición de , es decir, son disjuntos y su unión es . $n$ $S$ $1$ $n$ $S$ $A$ $B$ $C$ $A$ $B$ $C$ $S$ $S$

Estoy particularmente interesado en el caso de 3 partes, pero otros casos también serían interesantes. Tenga en cuenta que para el caso de 2 partes, el problema es equivalente al problema de IGUALDAD, por lo que tiene un límite inferior de para protocolos deterministas, pero un límite superior de para protocolos aleatorios. $\Omega(n)$ $O(\log n)$

Mi pregunta es si este problema se conoce antes. Si conoce algún problema que pueda estar relacionado, también me interesaría saberlo.

cc.complexity-theory communication-complexity Danu
fuente

17

Un límite inferior lineal en CC determinista sigue fijando uno de los conjuntos para que esté vacío.

Para un límite superior logarítmico aleatorizado, primero tenga en cuenta que este problema puede reducirse al problema preguntando si la suma de tres números de $3n$ bits es exactamente $2^{3n}-1$ . Este puede ser resuelto en comunicación aleatoria $O(\log n)$ por los jugadores que operan en un modo aleatorio $O(\log n)$ -bit prime.

Noam
fuente

¿No puede usar números de

bits y obtener un algoritmo que también funcione en un modelo de transmisión? Para que esto funcione, también debe verificar que el número total de elementos sea correcto, pero eso es fácil de hacer. Transporta los destruidos, por lo que la suma de

potencias de dos es igual a

si y solo si hay exactamente una copia de cada potencia de dos.

2^{n}

$2^n$

n

$n$

2^{n} - 1

$2^{n}-1$

Warren Schudy

1

Estoy investigando una pregunta ligeramente diferente, que parece estar relacionada. ¿Cuál sería una buena referencia para obtener detalles sobre el límite superior aleatorizado en la respuesta anterior?

Keren
fuente

1

tal vez deberías publicar otra pregunta?

Suresh Venkat

Para la respuesta a mi problema, puede mirar el protocolo aleatorizado para resolver el problema de igualdad para tener una idea. Por ejemplo, Ejemplo 3.5 en el libro de Nissan-Kushilevitz. La idea principal es usar huellas digitales, supongo.

Danu

La complejidad de la comunicación multipartita de "Establecer problema de partición"

Respuestas: