  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 [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.

Computational Complexity;Logic in Computer Science