Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > UNIVERSAL SEARCH:
Reports tagged with Universal Search:
TR10-034 | 7th March 2010
Luca Trevisan

The Program-Enumeration Bottleneck in Average-Case Complexity Theory

Three fundamental results of Levin involve algorithms or reductions
whose running time is exponential in the length of certain programs. We study the
question of whether such dependency can be made polynomial.

(1) Levin's ``optimal search algorithm'' performs at most a constant factor more slowly
than any other fixed ... more >>>




ISSN 1433-8092 | Imprint