Лучшая сложность общения нижняя граница дизъюнктивности

14

Хорошо известно, что никакой детерминированный двухсторонний протокол не может решить проблему дизъюнктивности (DISJ) на битных входах без отправки n + 1 бит в худшем случае (см., Например, книгу Kushilevitz and Nisan). Для рандомизированных протоколов с ограниченной ошибкой нижняя граница δ n для некоторой константы δ была также показана в основной статье Разборова [Razborov92]. Мой вопрос:NN+1δNδ

Какое наиболее известное явное значение настоящее время (верхняя и нижняя границы)?δ

Кроме того, есть ли вера в фактическое значение ?δ

[Разборов92] Александр А. Разборов: О распределительной сложности несвязности. Теор. Вычи. Sci. 106 (2): 385-390 (1992), doi: 10.1016 / 0304-3975 (92) 90260-M.

Дан
источник
7
Вам известно о содержании этой недавней статьи? eccc.hpi-web.de/report/2012/171 . Авторы вычисляют δ точно как некоторую постоянную около 0,4827.
Йонатан N
2
@Yonatan Сделать ответ?
Юваль Фильмус
@YonatanN Я не знаю об этой недавней газете. Большое спасибо за указатель!
Дану
4
Будьте осторожны, n + 1 для детерминированных протоколов и легко доказать, более поздние статьи для рандомизированных!
domotorp

Ответы:

16

δ

Сама константа была найдена с использованием системы компьютерной алгебры, и, насколько я знаю, ее нельзя выразить просто.

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