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:

1. Introduction
2. Applicability
3. The Fast Algorithm
4. Time Analysis
5. Assumptions on the Machine Model
6. Algorithmic Complexity
7. Generalizations
8. Summary & Conclusions
 previous  home  search LaTeX (37kb)   PostScript (196kb)   PDF (164kb)   arXiv.org contact    up    next

### BibTeX Entry

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