Power from Random Strings Download as PS


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 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, a space-bounded Kolmogorov measure KS, and a new time-bounded Kolmogorov complexity measure KT, respectively.

Our main results are:

Our hardness result for PSPACE gives rise to fairly natural problems that are complete for PSPACE under polynomial-time Turing reductions, but not under logarithmic-space many-one 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.