Power from Random Strings
Authors:
- Eric AllenderEAEric Allender
- Harry BuhrmanHBHarry Buhrman
- Michal KouckýMKMichal Koucký
- Dieter van MelkebeekDMDieter van Melkebeek
- Detlef RonneburgerDRDetlef Ronneburger
- 1 January 2006
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 35 (6) , 1467-1493
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 nonuniform reductions. These sets are provably not complete under the usual many-one reductions. Let ${{R_{\rm C}}}, {{R_{\rm Kt}}}, {{R_{\rm KS}}}, {{R_{\rm KT}}}$ be the sets of strings x having complexity at least $|x|/2$, according to the usual Kolmogorov complexity measure ${\mbox{\rm C}}$, Levin's time-bounded Kolmogorov complexity ${\mbox{\rm Kt}}$ [L. Levin, Inform. and Control, 61 (1984), pp. 15-37], a space-bounded Kolmogorov measure ${\mbox{\rm KS}}$, and a new time-bounded Kolmogorov complexity measure ${\mbox{\rm KT}}$, respectively. Our main results are as follows: \begin{remunerate} \item ${{R_{\rm KS}}}$ and ${{R_{\rm Kt}}}$ are complete for ${{\rm{PSPACE}}}$ and {\mbox{\rm EXP}}, respectively, under ${\mbox{\rm P/poly}}$-truth-table reductions. Similar results hold for other classes with ${{\rm{PSPACE}}}$-robust Turing complete sets. \item ${\mbox{\rm EXP}} = {\mbox{\rm NP}}^{{{R_{\rm Kt}}}}.$ \item ${{\rm{PSPACE}}} = {\mbox{\rm ZPP}}^{{{R_{\rm KS}}}} \subseteq {\mbox{\rm P}}^{{{R_{\rm C}}}}$. \item The Discrete Log, Factoring, and several lattice problems are solvable in ${\mbox{\rm BPP}}^{{{R_{\rm KT}}}}$. \end{remunerate} Our hardness result for ${{\rm{PSPACE}}}$ gives rise to fairly natural problems that are complete for ${{\rm{PSPACE}}}$ under ${\mbox{$\leq^{\rm p}_{\rm T}$}}$ reductions, but not under ${\mbox{$\leq^{\rm log}_{\rm m}$}}$ reductions. Our techniques also allow us to show that all computably enumerable sets are reducible to ${{R_{\rm C}}}$ via ${\mbox{\rm P/poly}}$-truth-table reductions. This provides the first "efficient" reduction of the halting problem to ${{R_{\rm C}}}$.
Keywords
This publication has 55 references indexed in Scilit:
- NL-printable sets and nondeterministic Kolmogorov complexityTheoretical Computer Science, 2006
- What can be efficiently reduced to the Kolmogorov-random strings?Annals of Pure and Applied Logic, 2006
- PRIMES is in PAnnals of Mathematics, 2004
- Reducing the complexity of reductionscomputational complexity, 2001
- Computational complexity via programming languages: constant factors do matterActa Informatica, 2000
- BPP has subexponential time simulations unlessEXPTIME has publishable proofscomputational complexity, 1993
- Rudimentary reductions revisitedInformation Processing Letters, 1991
- Non-deterministic exponential time has two-prover interactive protocolscomputational complexity, 1991
- On uniformity within NC1Journal of Computer and System Sciences, 1990
- How to Generate Cryptographically Strong Sequences of Pseudorandom BitsSIAM Journal on Computing, 1984