Это старая открытая проблема, справедлива ли теорема прямой суммы для детерминированной сложности коммуникации, то есть, является ли решение независимых случаев задачи в раз сложнее, чем решение одного случая. [FKNN95] показал следующие результаты:
- Отрицательный результат: есть частичная функция (из-за [O90]), чья детерминированная сложность связи равна , но вычисление ее на независимых экземплярах имеет сложность .
- Положительный результат: для каждой функции , если детерминированная коммуникационная сложность равна сложность вычисления на независимых экземплярах должна быть не менее .
Я не знаю каких-либо других общих положительных результатов по проблеме прямой суммы. Однако, похоже, что для конкретных задач, которые обычно рассматриваются в сложности коммуникации, например, равенство или несвязность, известна теорема о прямой сумме.
У меня вопрос: есть ли другие примеры проблем, для которых теорема сложности детерминированной коммуникации неизвестна или даже не известна (кроме функции из [O90])?
Ссылки:
[FKNN95] Томас Федер, Эяль Кушилевиц, Мони Наор, Ноам Нисан: Амортизированная сложность общения. SIAM J. Comput. 24 (4): 736-750 (1995)
[O90] Два сообщения почти оптимальны для передачи информации. Алон Орлицкий. PODC, стр. 219-232. ACM, (1990)