Проблемы коммуникации, для которых неизвестна теорема о прямой сумме

10

Это старая открытая проблема, справедлива ли теорема прямой суммы для детерминированной сложности коммуникации, то есть, является ли решение независимых случаев задачи в раз сложнее, чем решение одного случая. [FKNN95] показал следующие результаты:TT

  • Отрицательный результат: есть частичная функция (из-за [O90]), чья детерминированная сложность связи равна , но вычисление ее на независимых экземплярах имеет сложность .Θ(журналN)TΘ(T+журналTжурналN)
  • Положительный результат: для каждой функции , если детерминированная коммуникационная сложность равна сложность вычисления на независимых экземплярах должна быть не менее .еесеTΩ(T(с-журналN))

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

У меня вопрос: есть ли другие примеры проблем, для которых теорема сложности детерминированной коммуникации неизвестна или даже не известна (кроме функции из [O90])?

Ссылки:

[FKNN95] Томас Федер, Эяль Кушилевиц, Мони Наор, Ноам Нисан: Амортизированная сложность общения. SIAM J. Comput. 24 (4): 736-750 (1995)

[O90] Два сообщения почти оптимальны для передачи информации. Алон Орлицкий. PODC, стр. 219-232. ACM, (1990)

Или меир
источник

Ответы:

5

Я думаю, что могу предложить проблему, которая не широко известна, но для которой я заинтересован. Предположим, у нас есть перестановок в . Алиса, Боб и Кэрол получают первый, второй и третий элементы всех перестановок соответственно. Цель состоит в том, чтобы вычислить , где - знак перестановки (может принимать -1 или +1). Меня интересует сложность коммуникации в модели NiH.NπяS3ΠяsгN(πя)sгN(πя)πя

Некоторое время назад я пытался применить теорему о прямой сумме, но здесь у нас есть некоторые препятствия в зависимости от вклада разных участников. Я до сих пор не знаю, имеет ли место нижняя граница для этой проблемы.Ω(N)

Всеволод Опарин
источник