Abstract
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 R K (the set of Kolmogorov-random strings) that lies between BPP and PSPACE [5, 4]. The results in this paper were obtained, as part of an investigation of whether this upper bound can be improved, to show BPP ⊆ C ⊆ PSPACE ∩ P/poly. (*) In fact, we conjecture that C = BPP = P, and we close this paper with a discussion of the possibility this might be an avenue for trying to prove the equality of BPP and P. In this paper, 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 (PA), then (*) holds. Although it was subsequently proved that infinitely many of these statements are, in fact, independent of those extensions of PA [1], we present these results in the hope that related ideas may yet contribute to a proof of C = BPP, and because this work did serve as a springboard for subsequent work in the area.