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/Surveyin 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 algorithmMis described that solves any well-defined problempas quickly as the fastest algorithm computing a solution top, save for a factor of 5 and low-order additive terms.Moptimally distributes resources between the execution of provably correctp-solving programs and an enumeration of all proofs, including relevant proofs of program correctness and of time bounds on program runtimes.Mavoids Blum's speed-up theorem by ignoring programs without correctness proof.Mhas 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 functionfis also among the shortest programs provably computingf.

Contents:

- Introduction & Main Result
- Levin Search
- Applicability of the Fast Algorithm
M_{p*}- The Fast Algorithm
M_{p*}- Time Analysis
- Assumptions on the Machine Model
- Algorithmic Complexity and the Shortest Algorithm
- Generalizations
- 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 |

@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 |