previous  home  search  LaTeX (37kb)   PostScript (196kb)   PDF (164kb)   Html/Gif   CiteSeer   contact    up    next  

The Fastest and Shortest Algorithm for All Well-Defined Problems


Author: Marcus Hutter (2000)
Comments: 12 pages
Subj-class: Computational Complexity; Artificial Intelligence; Learning
ACM-class: F.2.3
Reference: International Journal of Foundations of Computer Science, 13:3 (2002) 431-443
Report-no: IDSIA-16-00 and cs.CC/0206022
Paper: LaTeX (37kb)  -  PostScript (196kb)  -  PDF (164kb)  -  Html/Gif
Slides: PostScript - PDF
Review/Survey in guide.supereva.it (cached)
Remark: This is an extended version of An effective Procedure for Speeding up Algorithms

Keywords: Acceleration, Computational Complexity, Algorithmic Information Theory, Kolmogorov Complexity, Blum's Speed-up Theorem, Levin Search.

Abstract: An algorithm M is described that solves any well-defined problem p as quickly as the fastest algorithm computing a solution to p, save for a factor of 5 and low-order additive terms. M optimally distributes resources between the execution of provably correct p-solving programs and an enumeration of all proofs, including relevant proofs of program correctness and of time bounds on program runtimes. M avoids Blum's speed-up theorem by ignoring programs without correctness proof. M has broader applicability and can be faster than Levin's universal search, the fastest method for inverting functions save for a large multiplicative constant. An extension of Kolmogorov complexity and two novel natural measures of function complexity are used to show that the most efficient program computing some function f is also among the shortest programs provably computing f.

Contents:

  1. Introduction & Main Result
  2. Levin Search
  3. Applicability of the Fast Algorithm Mp*
  4. The Fast Algorithm Mp*
  5. Time Analysis
  6. Assumptions on the Machine Model
  7. Algorithmic Complexity and the Shortest Algorithm
  8. Generalizations
  9. Summary & Outlook
Reviewer: I propose to accept the paper as is. This is an excellent result, unexpected.
(More than 500 downloads in the first week after the announcement).
 previous  home  search  LaTeX (37kb)   PostScript (196kb)   PDF (164kb)   Html/Gif   CiteSeer   contact    up    next  

BibTeX Entry

@Article{Hutter:01fast,
  author =       "Marcus Hutter",
  title =        "The Fastest and Shortest Algorithm for All Well-Defined Problems",
  journal =      "International Journal of Foundations of Computer Science",
  publisher =    "World Scientific",
  volume =       "13",
  number =       "3",
  pages =        "431--443",
  month =        jun,
  year =         "2002",
  keywords =     "Acceleration, Computational Complexity,
                  Algorithmic Information Theory, Kolmogorov Complexity, Blum's
                  Speed-up Theorem, Levin Search.",
  url =          "http://www.hutter1.net/ai/pfastprg.htm",
  url2 =         "http://arxiv.org/abs/cs.CC/0206022",
  ftp =          "ftp://ftp.idsia.ch/pub/techrep/IDSIA-16-00.ps.gz",
  abstract =     "An algorithm M is described that solves any well-defined problem
                  p as quickly as the fastest algorithm computing a solution to
                  p, save for a factor of 5 and low-order additive terms. M
                  optimally distributes resources between the execution of provably
                  correct p-solving programs and an enumeration of all proofs,
                  including relevant proofs of program correctness and of time
                  bounds on program runtimes. M avoids Blum's speed-up theorem by
                  ignoring programs without correctness proof. M has broader
                  applicability and can be faster than Levin's universal search, the
                  fastest method for inverting functions save for a large
                  multiplicative constant. An extension of Kolmogorov complexity and
                  two novel natural measures of function complexity are used to show
                  that the most efficient program computing some function f is
                  also among the shortest programs provably computing f.",
}
      
 previous  home  search  LaTeX (37kb)   PostScript (196kb)   PDF (164kb)   Html/Gif   CiteSeer   contact    up    next