# The Fastest and Shortest Algorithm for All Well-Defined Problems

• Published in 2002
In the collections
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.

## Other information

key
Hutter2002
type
article
2012-08-14
date_published
2002-02-02
journal
International Journal of Foundations of Computer Science
keywords
Kolmogorov complexity,acceleration,algorithmic information theory,blum's speed-up theorem,computational complexity,levin search
number
3
pages
431--443
volume
13

### BibTeX entry

@article{Hutter2002,
key = {Hutter2002},
type = {article},
title = {The Fastest and Shortest Algorithm for All Well-Defined Problems},
author = {Hutter, Marcus},
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.

},
comment = {},
}