An effective Procedure for Speeding up Algorithms
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
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.",
}