Es bien sabido que no existe un protocolo determinista de dos partes puede resolver el problema de disyunción (DISJ) en entradas -bit sin enviar bits en el peor de los casos (véase, por ejemplo, el libro de Kushilevitz y Nisan). Para protocolos aleatorios de error acotado, Razborov [Razborov92] también ha mostrado un límite inferior de , para alguna constante . Mi pregunta es:
¿Cuál es el valor explícito más conocido de actualmente (límites superior e inferior)?
Además, ¿hay alguna creencia en el valor real de ?
[Razborov92] Alexander A. Razborov: Sobre la complejidad distributiva de la desunión. Theor Comput Sci. 106 (2): 385-390 (1992) doi: 10.1016 / 0304-3975 (92) 90260-M
Respuestas:
La constante misma se encontró usando un sistema de álgebra computacional, y que yo sepa, no se puede expresar simplemente.
fuente