We investigate the question of whether one can characterize complexity
classes (such as PSPACE or NEXP) in terms of efficient
reducibility to the set of Kolmogorov-random strings R_C.
We show that this question cannot be posed without explicitly dealing
with issues raised by the choice of universal
machine in the definition of Kolmogorov complexity. Among other results,
we show that although for every universal machine U, there are very
complex sets that are poly-time dtt-reducible to R_{C_U}, it is nonetheless true that
P = the set of all decidable sets in the intersection, over all
universal machines U, of the sets that are poly-time dtt-reducible to
R_{C_U}.

We also show for a
broad class of reductions that the sets reducible to R_C have small
circuit complexity.