Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR12-028 | 8th March 2013 14:54

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

RSS-Feed




Revision #1
Authors: Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, Iddo Tzameret
Accepted on: 8th March 2013 14:54
Downloads: 3203
Keywords: 


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.

The results in this paper were obtained, as part of an investigation of
whether this upper bound can be improved, to show
BPP $\subseteq$ C \subseteq (PSPACE $\cap$ 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, 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.



Changes to previous version:

Rewriting for improved clarity, better exposition and motivation.


Paper:

TR12-028 | 30th March 2012 19:06

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





TR12-028
Authors: Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, Iddo Tzameret
Publication: 30th March 2012 19:06
Downloads: 3365
Keywords: 


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. In this paper, we investigate improving
this upper bound from PSPACE to (PSPACE $\cap$ 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 $\subseteq C \subseteq$ PSPACE $\cap$ 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.



ISSN 1433-8092 | Imprint