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.

Theorem 2.7 in the original version has been revised, and is now Proposition 5. New theorems (Theorems 4 and 11) have been added, making explicit some items that were discussed implicitly in the text of the original version. The exposition has been improved.

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.