%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 }