TY - JOUR
T1 - Reductions to the set of random strings
T2 - The resource-bounded case
AU - Allender, Eric
AU - Buhrman, Harry
AU - Friedman, Luke
AU - Loff, Bruno
PY - 2014/8/19
Y1 - 2014/8/19
N2 - This paper is motivated by a conjecture [All12, ADF+13] 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 [ADF+13l] 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 [All12, ADF+13] 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 [ADF+13l] 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=84940330291&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84940330291&partnerID=8YFLogxK
U2 - 10.2168/LMCS-10(3:5)2014
DO - 10.2168/LMCS-10(3:5)2014
M3 - Article
SN - 1860-5974
VL - 10
JO - Logical Methods in Computer Science
JF - Logical Methods in Computer Science
IS - 3
ER -