Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic

摘要

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 $cal C$ defined in terms of polynomial-time truth-table reducibility to $RK$ (the set of Kolmogorov-random strings) that lies between $BPP$ and $PSPACE$. The results in this paper were obtained, as part of an investigation of whether this upper bound can be improved, to show $$ BPP subseteq {cal C} subseteq PSPACE cap Ppoly. quadquadquad(*)$$ In fact, we conjecture that ${cal C} = BPP = Polytime$, 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 $Polytime$. 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 (by Allender, Buhrman, Friedman and Loff) that infinitely many of these statements are, in fact, independent of those extensions of $PA$, we present these results in the hope that related ideas may yet contribute to a proof of ${cal C} = BPP$, and because this work did serve as a springboard for subsequent work in the area.