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-054 | 30th June 2014 17:06

Reductions to the set of random strings:the resource-bounded case

RSS-Feed




Revision #1
Authors: Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff
Accepted on: 30th June 2014 17:06
Downloads: 1130
Keywords: 


Abstract:

This paper is motivated by a conjecture that BPP can be characterized in terms of polynomial-time nonadaptive reductions to the set of Kolmogorov-random strings. In this paper we show that an approach laid out by [Allender et al] to settle this conjecture cannot succeed without significant alteration, but that it does bear fruit if we consider time-bounded Kolmogorov complexity instead.

We show that if a set A is reducible in polynomial time to the set of time-t-bounded Kolmogorov-random strings (for all large enough time bounds t), then A is in P/poly, and that if in addition such a reduction exists for any universal Turing machine one uses in the definition of Kolmogorov complexity, then A is in PSPACE.



Changes to previous version:

Improved exposition, minor corrections. This new version also appears on Arxiv, and will appear in a special issue of LMCS devoted to CiE 2012.


Paper:

TR12-054 | 2nd May 2012 11:48

Reductions to the set of random strings:the resource-bounded case





TR12-054
Authors: Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff
Publication: 2nd May 2012 11:48
Downloads: 3027
Keywords: 


Abstract:

This paper is motivated by a conjecture that BPP can be characterized in terms of polynomial-time nonadaptive reductions to the set of Kolmogorov-random strings. In this paper we show that an approach laid out by [Allender et al] to settle this conjecture cannot succeed without significant alteration, but that it does bear fruit if we consider time-bounded Kolmogorov complexity instead.

We show that if a set A is reducible in polynomial time to the set of time-t-bounded Kolmogorov-random strings (for all large enough time bounds t), then A is in P/poly, and that if in addition such a reduction exists for any universal Turing machine one uses in the definition of Kolmogorov complexity, then A is in PSPACE.



ISSN 1433-8092 | Imprint