loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02)
Power from Random Strings
Vancouver, BC, Canada
November 16-November 19
ISBN: 0-7695-1822-2
ASCII Text
x 
 
Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger, "Power from Random Strings," Foundations of Computer Science, IEEE Annual Symposium on, pp. 669, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002.
 
 
BibTex
x
 
@article{ 10.1109/SFCS.2002.1181992,
author = {Eric Allender and Harry Buhrman and Michal Koucký and Dieter van Melkebeek and Detlef Ronneburger},
title = {Power from Random Strings},
journal ={Foundations of Computer Science, IEEE Annual Symposium on},
volume = {0},
year = {2002},
issn = {0272-5428},
pages = {669},
doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1181992},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, IEEE Annual Symposium on
TI - Power from Random Strings
SN - 0272-5428
SP
EP
A1 - Eric Allender,
A1 - Harry Buhrman,
A1 - Michal Koucký,
A1 - Dieter van Melkebeek,
A1 - Detlef Ronneburger,
PY - 2002
KW - null
VL - 0
JA - Foundations of Computer Science, IEEE Annual Symposium on
ER -
 
Eric Allender, Rutgers University
Harry Buhrman, CWI and University of Amsterdam
Michal Koucký, Rutgers University
Dieter van Melkebeek, University of Wisconsin
Detlef Ronneburger, Rutgers University

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 RK; RKt; RKS;RKT be the sets of strings x having complexity at least {{\left| x \right|} \mathord{\left/ {\vphantom {{\left| x \right|} 2}} \right. \kern-\nulldelimiterspace} 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. RKS and RKt are complete for PSPACE and EXP, respectively, under P/poly-truth-table reductions.
  • 2. EXP = NPRKt.
  • 3. PSPACE = ZPP^{R_{ks} } \subseteq P^{R_k }.
  • 4. The Discrete Log, Factoring, and several lattice problems are solvable in BPPRKT.

    • Citation:
    Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger, "Power from Random Strings," focs, pp.669, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002
    Usage of this product signifies your acceptance of the Terms of Use.