Let C(x) and K(x) denote plain and prefix Kolmogorov complexity, respectively, and let R_C and R_K denote the sets of strings that are ``random'' according to these measures; both R_K and R_C are undecidable. Earlier work has shown that every set in NEXP is in NP relative to both R_K and R_C, and that every set in BPP is polynomial-time truth-table reducible to both R_K and R_C [Allender, Buhrman, Koucky],[Buhrman,Fortnow,Koucky,Loff].

(All of these inclusions hold, no matter which
``universal'' Turing machine one uses in the definitions of C(x) and K(x).) Since each machine U gives rise to a slightly different measure C_U or K_U, these inclusions can be stated as:

** BPP is contained in \DEC intersect \bigcap_U {A : A \pttred R_{C_U}}.
** NEXP is contained in \DEC intersect \bigcap_U NP^{R_{C_U}}.
** BPP is contained in \DEC intersect \bigcap_U {A : A \pttred R_{K_U}}.
** NEXP is contained in \DEC intersect \bigcap_U NP^{R_K_U}.

(Here, \DEC denotes the class of decidable sets.)

It remains unknown whether \DEC is EQUAL to \DEC intersect \bigcap_U {A : A \pttred R_C_U}.

In this paper, we present the first upper bounds on the complexity of sets that are efficiently reducible to R_K. We show:

** BPP \subseteq \DEC \cap \bigcap_U {A : A \pttred R_K_U} \subseteq PSPACE.
** NEXP \subseteq \DEC \cap \bigcap_U NP^{R_K_U}\subseteq EXPSPACE.

This also provides the first quantitative limits on the applicability of uniform derandomization techniques.