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

- Published in 2002
- Added on

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.

## Links

- http://www.hutter1.net/ai/pfastprg.htm
- http://arxiv.org/abs/cs.CC/0206022
- https://arxiv.org/pdf/cs/0206022.pdf

## Other information

- key
- Hutter2002
- type
- article
- date_added
- 2012-08-14
- date_published
- 2002-09-14
- 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 = {}, date_added = {2012-08-14}, date_published = {2002-09-14}, urls = {http://www.hutter1.net/ai/pfastprg.htm,http://arxiv.org/abs/cs.CC/0206022,https://arxiv.org/pdf/cs/0206022.pdf}, collections = {Attention-grabbing titles,Basically computer science}, url = {http://www.hutter1.net/ai/pfastprg.htm http://arxiv.org/abs/cs.CC/0206022 https://arxiv.org/pdf/cs/0206022.pdf}, urldate = {2012-08-14}, year = 2002, 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 }