期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Can complexity classes be characterized in terms of efficient reducibility to the (undecidable) set of Kolmogorov-random strings? Although this might seem improbable, a series of papers has recently provided evidence that this may be the case. In particular, it is known that there is a class of problems C defined in terms of polynomial-time truth-table reducibility to RK (the set of Kolmogorov-random strings) that lies between BPP and PSPACE. In this paper, we investigate improving
this upper bound from PSPACE to (PSPACE P/poly).
More precisely, we present a collection of true statements in the language of arithmetic, (each provable in ZF) and show that if these statements can be proved in certain extensions of Peano arithmetic, then
BPP C PSPACE P/poly.
We conjecture that C is equal to P, and discuss the possibility this might be an avenue for trying to prove the equality of BPP and P.
