wielostronna złożoność komunikacji „Ustaw problem z partycją”

13

W aplikacji, którą rozważam, muszę znać złożoność komunikacyjną następującego problemu:

Biorąc pod uwagę , niech będzie zbiorem liczb całkowitych od do . Alicja, Bob Carol każdy odbiera podzbiór , oznaczony jako , i , odpowiednio. Chcą sprawdzić, czy , i tworzą partycję , czyli są one rozłączne, a ich związek jest . $n$ $S$ $1$ $n$ $S$ $A$ $B$ $C$ $A$ $B$ $C$ $S$ $S$

Szczególnie interesuje mnie sprawa 3 stron, ale inne przypadki również byłyby interesujące. Należy zauważyć, że w przypadku 2 stron problem jest równoważny problemowi RÓWNOŚĆ, więc ma dolną granicę dla protokołów deterministycznych, ale górną granicę dla protokołów losowych. $\Omega(n)$ $O(\log n)$

Moje pytanie brzmi, czy ten problem jest znany wcześniej. Jeśli znasz jakieś problemy, które mogą być powiązane, chciałbym również wiedzieć.

cc.complexity-theory communication-complexity

— Danu
źródło

17

Następuje liniowa dolna granica deterministycznego CC poprzez ustalenie, że jeden z zestawów będzie pusty.

$3n$ $2^{3n}-1$ $O(\log n)$ $O(\log n)$

— Noam
źródło

2^{n}

$2^n$

n

$n$

2^{n} - 1

$2^{n}-1$

1

Zastanawiam się nad nieco innym pytaniem, które wydaje się powiązane. Co byłoby dobrym źródłem informacji na temat losowej górnej granicy w powyższej odpowiedzi?

— Keren
źródło

1

może powinieneś opublikować kolejne pytanie?

— Suresh Venkat,

Aby uzyskać odpowiedź na mój problem, możesz przejrzeć losowy protokół rozwiązania problemu równości, aby uzyskać pomysł. Na przykład przykład 3.5 w książce Nissana-Kushilevitza. Chyba główną ideą jest używanie odcisków palców.

— Danu,