Randomized Query Complexity schlägt erstmals Certificate Complexity

Randomized query complexity can beat certificate complexity

Eine seit Langem offene Frage der Query Complexity lautet, ob es eine totale Boolean-Funktion f mit R(f) << C(f) gibt. Shalev Ben-David und Robin Kothari konstruieren nun eine Funktion mit R(f) = O~(sqrt{C(f)}), was bis auf Log-Faktoren optimal ist. Dieselbe Funktion erreicht zudem Q(f) = O~(C(f)^{1/4}) – ebenfalls nahezu optimal. Damit ist ein jahrzehntealtes Problem der Computational Complexity gelöst.