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 R-C, 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 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: 1. R-KS and R-Kt 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. 2. EXP = NP(R)Kt. 3. PSPACE = ZPP(R)KS subset of P-RC. 4. The Discrete Log, Factoring, and several lattice problems are solvable in (BPPKT)-K-R. Our hardness result for PSPACE gives rise to fairly natural problems that are complete for PSPACE under <= (p)(T) reductions, but not under <= m(l)(og) reductions. Our techniques also allow us to show that all computably enumerable sets are reducible to R-C via P/poly-truth-table reductions. This provides the first "efficient" reduction of the halting problem to R-C.