TY - GEN
T1 - Reductions to the set of random strings
T2 - 37th International Symposium on Mathematical Foundations of Computer Science 2012, MFCS 2012
AU - Allender, Eric
AU - Buhrman, Harry
AU - Friedman, Luke
AU - Loff, Bruno
PY - 2012
Y1 - 2012
N2 - This paper is motivated by a conjecture [1,5] 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 in [5] 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.
AB - This paper is motivated by a conjecture [1,5] 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 in [5] 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.
UR - http://www.scopus.com/inward/record.url?scp=84865013329&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84865013329&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-32589-2_11
DO - 10.1007/978-3-642-32589-2_11
M3 - Conference contribution
AN - SCOPUS:84865013329
SN - 9783642325885
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 88
EP - 99
BT - Mathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012, Proceedings
Y2 - 27 August 2012 through 31 August 2012
ER -