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 nonuniform reductions. These sets are provably not complete under the usual many-one reductions. Let RC, RKt, RKS, RKT be the sets of strings x having complexity at least $|x|/2$, according to the usual Kolmogorov complexity measure C, Levin's time-bounded Kolmogorov complexity Kt [L. Levin, Inform. and Control, 61 (1984), pp. 15-37], a space-bounded Kolmogorov measure KS, and a new time-bounded Kolmogorov complexity measure KT, respectively. Our main results are as follows: {remunerate} RKS and RKt are complete for PSPACE and { EXP}, respectively, under P/poly-truth-table reductions. Similar results hold for other classes with PSPACE-robust Turing complete sets. EXP = NP^RKt. PSPACE = ZPP^RKS ⊆ P^RC. The Discrete Log, Factoring, and several lattice problems are solvable in BPP^RKT. {remunerate} Our hardness result for PSPACE gives rise to fairly natural problems that are complete for PSPACE under ≤ᵖT reductions, but not under ≤ˡᵒᵍₘ reductions. Our techniques also allow us to show that all computably enumerable sets are reducible to RC via P/poly-truth-table reductions. This provides the first "efficient" reduction of the halting problem to RC.