Published by the Department of Computer Science, The University of Chicago.

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 $\cal 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$. 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. \quad\quad\quad(*)$$ 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.

• The article: PDF (233 KB)
• Source material: ZIP (84 KB)
• BibTeX entry for this article (342 bytes)

Submitted March 7, 2013, revised April 23, 2013; published April 27, 2013.

© 2013 Eric Allender, George Davie, Luke Friedman, Samuel B. Hopkins, and Iddo Tzameret
Licensed under a Creative Commons Attribution License

Article 4

Article 6

Volume 2013

Published articles