TY - JOUR

T1 - The fastest and shortest algorithm for all well-defined problems

AU - Hutter, Marcus

PY - 2002

Y1 - 2002

N2 - An algorithm M is described that solves any well-defined problem p as quickly a 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 the most efficient program computing some function f is also among the shortest programs provably computing f.

AB - An algorithm M is described that solves any well-defined problem p as quickly a 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 the most efficient program computing some function f is also among the shortest programs provably computing f.

KW - Acceleration

KW - Algorithmic Information Theory

KW - Blum's Speed-up Theorem

KW - Computational Complexity

KW - Kolmogorov Complexity

KW - Levin Search

UR - http://www.scopus.com/inward/record.url?scp=1642393842&partnerID=8YFLogxK

U2 - 10.1142/S0129054102001199

DO - 10.1142/S0129054102001199

M3 - Article

SN - 0129-0541

VL - 13

SP - 431

EP - 443

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

IS - 3

ER -