科学・技術
ランダム化クエリ複雑性は証明書複雑性を上回ることができる
Randomized query complexity can beat certificate complexity (arxiv.org)
要約
計算複雑性理論における長年の未解決問題に対し、ランダム化クエリ複雑性（R(f)）と証明書複雑性（C(f)）の間にR(f) << C(f)となるブール関数が存在するかどうかが問われていました。本研究では、R(f) = O~(sqrt{C(f)})となる関数を構築し、これは対数因子を除いて最適であることが示されました。さらに、この関数は量子クエリ複雑性Q(f)についてもQ(f) = O~(C(f)^{1/4})となり、これもほぼ最適であることが示唆されています。
全文翻訳
計算複雑性理論における長年の未解決問題は、R(f) << C(f)となる全域ブール関数fが存在するかどうかを問うものでした。ここで、R(f)とC(f)はそれぞれ、その境界誤差ランダム化クエリ複雑性および証明書複雑性を表します。
私たちはR(f) = O~(sqrt{C(f)})となる関数を構築しました。これは対数因子を除いて最適です。
同じ関数は、Q(f) = O~(C(f)^{1/4})も満たします。ここで、Q(f)はfの境界誤差量子クエリ複雑性であり、これもほぼ最適です。