随机查询复杂度竟能击败证书复杂度

Randomized query complexity can beat certificate complexity

计算复杂性领域长期存在一个悬而未决的问题：是否存在总布尔函数，其随机查询复杂度 R(f) 显著小于证书复杂度 C(f)？Shalev Ben-David 和 Robin Kothari 的最新研究给出了肯定答案。他们成功构造了一个函数，证明了 R(f) 可以达到 O~(sqrt{C(f)})，这一结果在对数因子内已达到最优。更令人兴奋的是，该函数在量子查询复杂度 Q(f) 上也表现优异，达到了 O~(C(f)^{1/4}) 的近乎最优水平。这项突破不仅解决了理论难题，也为理解随机与量子算法的边界提供了关键视角。