- Authors: E. Allender, H. Buhrman, M. Koucky, D. van Melkebeek, and
D. Ronneburger.
- Reference: SIAM Journal on Computing, 35: 1467-1493, 2006.
- Comment regarding KT and circuit size.
- 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 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:
- 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 = NPRKt.
- PSPACE = ZPPRKS and is a subset of
PRC.
- The Discrete Log, Factoring, and several lattice problems
are solvable in BPPRKT.
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.
