Chicago Journal of Theoretical Computer Science

Volume 2013

Article 5

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

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

Eric Allender
Rutgers University, New Brunswick, NJ
allender AT cs DOT rutgers DOT edu

George Davie
University of South Africa, Pretoria, South Africa
davieg AT unisa DOT ac DOT za

Luke Friedman
Rutgers University, New Brunswick, NJ
lbfried AT cs DOT rutgers DOT edu

Samuel B. Hopkins
University of Washington, Seattle, Washington
samhop AT uw DIT edu


Iddo Tzameret
Tsinghua University, Beijing, P.R. China
tzameret AT tsinghua DOT edu DOT cn

April 27, 2013


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.

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

DOI: 10.4086/cjtcs.2013.005

[] Article 4 [] Article 6
[back] Volume 2013 [back] Published articles
[CJCTS home]