Power from random strings

We show that sets consisting of strings of high Kolmogorov complexity provide examples of sets that are complete for several complexity classes under probabilistic and non-uniform reductions. These sets are provably not complete under the usual many-one reductions. Let R_K, R_Kt, R_KS, R_KT be the sets of strings x having complexity at least |x|/2, according to the usual Kolmogorov complexity measure K, Levin´s time-bounded Kolmogorov complexity Kt [27], a space-bounded Kolmogorov measure KS, and the time-bounded Kolmogorov complexity measure KT that was introduced in [4], respectively. Our main results are: 1. R_KS and R_Kt are complete for PSPACE and EXP, respectively, under P/poly-truth-table reductions. 2. EXP = NP^R(Kt). 3. PSPACE = ZPP^R(KS) ⊆ P^R(K). 4. The Discrete Log, Factoring, and several lattice problems are solvable in BPP^R(KT).