TY - JOUR
TI - Reductions to the set of random strings: The resource-bounded case
DO - https://doi.org/doi:10.7282/T3NS0WRJ
AU - Allender, Eric
AU - Buhrman, Harry
AU - Friedman, Luke
AU - Loff, Bruno
PY - 2014
T2 - Logical Methods in Computer Science
VL - 10
IS - 3
SP - 1
EP - 18
AB - 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 in [ADF+13] 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.
KW - Kolmogorov complexity
KW - Computational complexity
KW - BPP (Complexity)
LA - English
ER -