4 ms·
The Fastest and Shortest Algorithm for All Well-Defined Problems: https://arxiv.org/abs/cs/0206022 https://arxiv.org/abs/cs/0206022 Abstract: An algorithm M is
by theemathas 10y ago
The Fastest and Shortest Algorithm for All Well-Defined Problems: https://arxiv.org/abs/cs/0206022 https://arxiv.org/abs/cs/0206022
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.
The catch is that the constants in the big-O are enormous.
- zelah 10y agoI vote twice for this one!
- palashkulsh 10y agoAny laymen explanation ? Not able to grasp the concept.
- deleted 10y ago[deleted]
- pwdisswordfish 10y agoFirst you vote once, and then you vote again.
- theemathas 10y agoIt does two things concurrently: (1) search for an algorithm along with proofs for its correctness and time upper bound (2) run the fastest algorithm found so far, possibly aborting an slower algorithm when a faster one is found. Everything is scheduled so it's asymptotically optimal. However, there's an added cost to search for algorithms. This cost is exponential in the proof length, but constant for each problem since it is independent from the inputs. Of course, this constant is ridiculously huge.
- AstralStorm 10y agoFunny thing is, you can offload most of this to compile time, which is what Isabelle is doing, but then you miss out on guaranteed optimal runtime. Also the proof database may not be complete anyway.
- palashkulsh 10y ago@theemathas thanks, @pwdisswordfish - nice one :D
- AstralStorm 10y agoIt is only an existential proof, the algorithm has never been implemented. The closest that comes to it is the proof searcher in Isabelle. (blast method)