The Fastest and Shortest Algorithm for All Well-Defined Problems
| dc.creator | Hutter, Marcus | |
| dc.date | 2002-06-14 | |
| dc.date.accessioned | 2026-07-07T03:18:31Z | |
| dc.date.available | 2026-07-07T03:18:31Z | |
| dc.description | 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$. | |
| dc.description | 12 pages, 1 figure | |
| dc.identifier | https://arxiv.org/abs/cs/0206022 | |
| dc.identifier | http://arxiv.org/abs/cs/0206022 | |
| dc.identifier | International Journal of Foundations of Computer Science, Vol.13, No.3, June 2002, 431-443 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31146 | |
| dc.subject | Computational Complexity | |
| dc.subject | Logic in Computer Science | |
| dc.subject | F.2.3 | |
| dc.title | The Fastest and Shortest Algorithm for All Well-Defined Problems | |
| dc.type | text |