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 M_p*
4. The Fast Algorithm M_p*
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).

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.",
}