Случайность обходит сертификаты: давняя задача теории сложности решена

Randomized query complexity can beat certificate complexity

Шалев Бен-Дэвид и Робин Котари построили тотальную булеву функцию, у которой рандомизированная сложность запросов R(f) = O~(sqrt{C(f)}), что оптимально с точностью до логарифмических множителей. Это отвечает на давний открытый вопрос: может ли R(f) быть существенно меньше сертификатной сложности C(f). Та же функция имеет квантовую сложность Q(f) = O~(C(f)^{1/4}), что также почти оптимально.