This paper is motivated by a conjecture \cite{cie,adfht} 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 \cite{adfht} 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 \$\Ppoly\$, 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\$.