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$.
Additional Metadata
THEME Life Sciences (theme 5), Logistics (theme 3)
Publisher Springer
Editor B. Rovan , V. Sassone , P. Widmayer
Conference International Symposium on Mathematical Foundations of Computer Science
Allender, E, Buhrman, H, Friedman, L, & Loff Barreto, B. S. (2012). Reductions to the set of random strings:the resource-bounded case. In B Rovan, V Sassone, & P Widmayer (Eds.), Lecture Notes in Computer Science. Springer.