previous home search |
LaTeX (37kb)
PostScript (196kb)
PDF (164kb)
arXiv.org |
contact up next |

## An effective Procedure for Speeding up Algorithms

Author:Marcus Hutter (2000-2001) Comments:10 LaTeX pages Subj-class:Computational Complexity; Artificial Intelligence; Learning ACM-class:F.2.3 Reference:Workshop on Mathematical Approaches to Biological Computation (MaBiC 2001)

Workshop on Algorithmic information theory (TAI 2001)Report-no:IDSIA-16-00-v1 and cs.CC/0102018 Paper:LaTeX (37kb) - PostScript (196kb) - PDF (164kb) - arXiv.org Slides:PostScript - PDF Remark:Extended version: The Fastest and Shortest Algorithm for All Well-Defined Problems

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

Abstract:The provably asymptotically fastest algorithm within a factor of 5 for formally described problems will be constructed. The main idea is to enumerate all programs provably equivalent to the original problem by enumerating all proofs. The algorithm could be interpreted as a generalization and improvement of Levin search, which is, within a multiplicative constant, the fastest algorithm for inverting functions. Blum's speed-up theorem is avoided by taking into account only programs for which a correctness proof exists. Furthermore, it is shown that the fastest program that computes a certain function is also one of the shortest programs provably computing this function. To quantify this statement, the definition of Kolmogorov complexity is extended, and two new natural measures for the complexity of a function are defined.

Contents:

- Introduction
- Applicability
- The Fast Algorithm
- Time Analysis
- Assumptions on the Machine Model
- Algorithmic Complexity
- Generalizations
- Summary & Conclusions

previous home search |
LaTeX (37kb)
PostScript (196kb)
PDF (164kb)
arXiv.org |
contact up next |

@Article{Hutter:00speed, author = "Marcus Hutter", number = "IDSIA-16-00-v1", institution = "Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA)", title = "An effective Procedure for Speeding up Algorithms", year = "10 pages, 2001", journal = "Presented at the 3rd Workshop on Algorithmic Information Theory (TAI-2001)", keywords = "Acceleration, Computational Complexity, Algorithmic Information Theory, Blum's Speed-up, Levin Search.", http = "http://www.hutter1.net/ai/pspeed.htm", url = "http://arxiv.org/abs/cs.CC/0102018", ftp = "http://www.idsia.ch/idsiareport/IDSIA-16-00-v1.ps.gz", abstract = "The provably asymptotically fastest algorithm within a factor of 5 for formally described problems will be constructed. The main idea is to enumerate all programs provably equivalent to the original problem by enumerating all proofs. The algorithm could be interpreted as a generalization and improvement of Levin search, which is, within a multiplicative constant, the fastest algorithm for inverting functions. Blum's speed-up theorem is avoided by taking into account only programs for which a correctness proof exists. Furthermore, it is shown that the fastest program that computes a certain function is also one of the shortest programs provably computing this function. To quantify this statement, the definition of Kolmogorov complexity is extended, and two new natural measures for the complexity of a function are defined.", }

previous home search |
LaTeX (37kb)
PostScript (196kb)
PDF (164kb)
arXiv.org |
contact up next |