Un estudio reciente en el área de la complejidad computacional resuelve una pregunta abierta de larga data: la construcción de una función booleana total cuya complejidad de consulta aleatoria es significativamente menor que su complejidad de certificados. Los autores demuestran la existencia de una función f tal que su complejidad aleatoria R(f) es asintóticamente proporcional a la raíz cuadrada de su complejidad de certificados C(f), es decir, R(f) = O~(sqrt{C(f)}). Esta relación es óptima en términos de factores logarítmicos, estableciendo un límite inferior para la separación entre estos dos modelos de complejidad.
Además, la misma función presenta una complejidad de consulta cuántica Q(f) que es asintóticamente proporcional a la cuarta raíz de C(f), es decir, Q(f) = O~(C(f)^{1/4}). Este resultado también es casi óptimo, lo que sugiere que la ventaja de los algoritmos cuánticos sobre los clásicos en este contexto es limitada, aunque no nula. El trabajo contribuye a la comprensión de las relaciones fundamentales entre los diferentes modelos de complejidad, específicamente entre la aleatorización, la verificación de certificados y la computación cuántica. La investigación se enmarca en la teoría de la complejidad, un campo que estudia los recursos computacionales necesarios para resolver problemas y las limitaciones teóricas de los algoritmos. Este avance proporciona nuevas herramientas para analizar la eficiencia de los algoritmos y los protocolos de verificación en ciencias de la computación.