The Fastest and Shortest Algorithm for All Well-Defined Problems
M. Hutter. International Journal of Foundations of Computer Science, (2002)
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
%0 Journal Article
%1 Hutter:2002
%A Hutter, Marcus
%D 2002
%J International Journal of Foundations of Computer Science
%K Acceleration, Algorithmic Blum's Complexity, Computational Information Kolmogorov Levin Search. Speed-up Theorem, Theory,
%P 431-443
%T The Fastest and Shortest Algorithm for All Well-Defined Problems
%V 13
%X 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
@article{Hutter:2002,
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},
added-at = {2009-06-26T15:25:19.000+0200},
author = {Hutter, Marcus},
biburl = {https://www.bibsonomy.org/bibtex/27caed12d9addad214fec4fba7d1623db/butz},
description = {diverse cognitive systems bib},
interhash = {c02103ada017a6dec2c5743900d90880},
intrahash = {7caed12d9addad214fec4fba7d1623db},
journal = {International Journal of Foundations of Computer Science},
keywords = {Acceleration, Algorithmic Blum's Complexity, Computational Information Kolmogorov Levin Search. Speed-up Theorem, Theory,},
owner = {martin},
pages = { 431-443},
timestamp = {2009-06-26T15:25:37.000+0200},
title = {The Fastest and Shortest Algorithm for All Well-Defined Problems},
volume = 13,
year = 2002
}