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 non-uniform reductions. These sets are provably not complete under the usual many-one reductions. Let R/sub K/, R/sub Kt/, R/sub KS/, R/sub KT/ be the sets of strings x having complexity at least |x|/2, according to the usual Kolmogorov complexity measure K, Levin's time-bounded Kolmogorov complexity Kt [27], a space-bounded Kolmogorov measure KS, and the time-bounded Kolmogorov complexity measure KT that was introduced in [4], respectively. Our main results are: 1. R/sub KS/ and R/sub Kt/ are complete for PSPACE and EXP, respectively, under P/poly-truth-table reductions. 2. EXP = NP/sup R(Kt)/. 3. PSPACE = ZPP/sup R(KS)/ /spl sube/ P/sup R(K)/. 4. The Discrete Log, Factoring, and several lattice problems are solvable in BPP/sup R(KT)/.

Authors

• Eric Allender
• Harry Buhrman
• Michal Koucký 0001
• Dieter van Melkebeek
• Detlef Ronneburger

Keywords

• Polynomials
• Artificial intelligence
• Lattices
• Engineering profession
• Circuits
• Random String
• High Complexity
• Complex Class
• Examples Of Sets
• Input Size
• Main Techniques
• Polynomial-time Algorithm
• String Length
• Input Length
• Boolean Function
• Input Fractions
• Non-deterministic Polynomial-time
• Turing Machine
• Contraposition
• Hardness Results
• Discrete Logarithm
• Proof Let
• Uniform Reduction