Многопартийная коммуникационная сложность «Задача разделения раздела»

13

В рассматриваемом приложении мне необходимо знать сложность связи следующей проблемы:

Для данного пусть будет множеством целых чисел от до . Алиса, Боб и Кэрол каждый получает подмножество , обозначенное , и соответственно. Они хотят , чтобы проверить , является ли , и образуют разбиение , то есть, они не пересекаются и их объединение . $n$ $S$ $1$ $n$ $S$ $A$ $B$ $C$ $A$ $B$ $C$ $S$ $S$

Я особенно заинтересован в случае 3 сторон, но другие случаи были бы также интересны. Обратите внимание, что для случая 2 сторон задача эквивалентна проблеме РАВЕНСТВА, поэтому она имеет нижнюю границу для детерминированных протоколов, но верхнюю границу для рандомизированных протоколов. $\Omega(n)$ $O(\log n)$

У меня вопрос, известна ли эта проблема раньше? Если вы знаете какие-либо проблемы, которые могут быть связаны, мне было бы интересно также знать.

cc.complexity-theory communication-complexity Дан
источник

17

Далее следует линейная нижняя граница детерминированного CC, фиксируя, что один из наборов будет пустым.

Для рандомизированной логарифмической верхней границы, сначала обратите внимание, что эту проблему можно свести к задаче, задающей вопрос : точно ли сумма трех $3n$ битных чисел равна $2^{3n}-1$ . Эта проблема может быть решена в $O(\log n)$ рандомизированной коммуникации игроками, работающими в режиме случайного $O(\log n)$ -битного простого числа.

Ноам
источник

Разве вы не можете вместо этого использовать

битные числа и получить алгоритм, который работает и в потоковой модели? Чтобы это работало, вам также необходимо убедиться, что общее количество элементов является правильным, но это легко сделать. Выполняет уничтожение единиц, поэтому сумма

степеней двух равна

тогда и только тогда, когда существует ровно одна копия каждой степени двойки.

2^{n}

$2^n$

n

$n$

2^{n} - 1

$2^{n}-1$

Уоррен Шуди

1

Я смотрю на немного другой вопрос, который кажется связанным. Что может быть хорошим ориентиром для деталей о рандомизированной верхней границе в ответе выше?

Керен
источник

1

может быть, вы должны опубликовать еще один вопрос?

Суреш Венкат

Для ответа на мою проблему вы можете посмотреть на случайный протокол, чтобы решить проблему равенства, чтобы получить представление. Например, пример 3.5 в книге Ниссана-Кушилевича. Основная идея состоит в том, чтобы использовать дактилоскопию, я думаю.

Дану

Многопартийная коммуникационная сложность «Задача разделения раздела»

Ответы: