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/...

Full description

Saved in:
Bibliographic Details
Main Authors: Allender, E., Buhrman, H., Koucky, M., van Melkebeek, D., Ronneburger, D.
Format: Conference Proceeding
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Artificial intelligence
Circuits
Computer science
control theory
systems
Engineering profession
Exact sciences and technology
Lattices
Polynomials
Theoretical computing
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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)/.
ISSN:0272-5428
DOI:10.1109/SFCS.2002.1181992