Хорошо известно, что никакой детерминированный двухсторонний протокол не может решить проблему дизъюнктивности (DISJ) на битных входах без отправки n + 1 бит в худшем случае (см., Например, книгу Kushilevitz and Nisan). Для рандомизированных протоколов с ограниченной ошибкой нижняя граница δ n для некоторой константы δ была также показана в основной статье Разборова [Razborov92]. Мой вопрос:
Какое наиболее известное явное значение настоящее время (верхняя и нижняя границы)?
Кроме того, есть ли вера в фактическое значение ?
[Разборов92] Александр А. Разборов: О распределительной сложности несвязности. Теор. Вычи. Sci. 106 (2): 385-390 (1992), doi: 10.1016 / 0304-3975 (92) 90260-M.
Ответы:
Сама константа была найдена с использованием системы компьютерной алгебры, и, насколько я знаю, ее нельзя выразить просто.
источник