- Authors: E. Allender, H. Buhrman, M. Koucky, D. van Melkebeek, and
D. Ronneburger.
- Reference: SIAM Journal on Computing, 35: 1467-1493, 2006.
- Earlier version:
- E. Allender, H. Buhrman, M. Koucky, D. van Melkebeek, and
D. Ronneburger.
Power from Random Strings.
In Proceedings of the 43rd Annual IEEE Symposium on Foundations of
Computer Science, pages 669-678, 2002.
Abstract
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_{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, a space-bounded Kolmogorov
measure KS, and a new time-bounded Kolmogorov complexity measure KT,
respectively.
Our main results are:
- 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.
- EXP = NP^{RKt}.
- PSPACE = ZPP^{RKS} and is a subset of
P^{RC}.
- The Discrete Log, Factoring, and several lattice problems
are solvable in BPP^{RKT}.
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 R_{C} via P/poly-truth-table reductions.
This provides the first ``efficient'' reduction of the halting problem
to R_{C}.