3 ms·

> 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 l

> 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. So this solves any problem that you can formally specify with the same complexity as the best algorithm? This sounds too good to be true, what's the catch?

krackers 5y ago
This prior discussion [1] on levin complexity might be relevant. I think the catch is basically that there's a huge constant out in front which makes this impractical. IIUC, in the case of levin search, the reason for this huge constant is that at a high-level that the algorithm functions as follows (for the specific case of solving 3-sat) for an input x of size n, enumerate all TMs 1..n and simulate each on x for a certain number of steps (fixed function of n). If any one of them produce a satisfying assignment, output that assignment. You can see why this is a type of universal search: if the optimal algorithm is say polynomial (e.g. we assume that P=NP), then the above algorithm is also close to polynomial of one higher degree (as simulation is only a log factor) and by definition always outputs a satisfying assignment. The catch is that it only works if n is large enough to allow it to "discover" the right TM, and in the worst-case the minimum value of n for which the algorithm starts to work is the index of the encoding of a 3-sat algorithm, which is probably quite long. (A natural question to ask is that if such an TM index can be discovered, why not just use that TM directly? I believe it's because levin algorithm doesn't guarantee that the TM that we discover which produces a satisfying assignment is necessarily a valid TM for all inputs x. It could just be we got lucky and found a TM which worked only for this specific case.) [1] https://news.ycombinator.com/item?id=27045091 https://news.ycombinator.com/item?id=27045091

krackers 5y ago

This prior discussion [1] on levin complexity might be relevant. I think the catch is basically that there's a huge constant out in front which makes this impractical. IIUC, in the case of levin search, the reason for this huge constant is that at a high-level that the algorithm functions as follows (for the specific case of solving 3-sat) for an input x of size n, enumerate all TMs 1..n and simulate each on x for a certain number of steps (fixed function of n). If any one of them produce a satisfying assignment, output that assignment. You can see why this is a type of universal search: if the optimal algorithm is say polynomial (e.g. we assume that P=NP), then the above algorithm is also close to polynomial of one higher degree (as simulation is only a log factor) and by definition always outputs a satisfying assignment. The catch is that it only works if n is large enough to allow it to "discover" the right TM, and in the worst-case the minimum value of n for which the algorithm starts to work is the index of the encoding of a 3-sat algorithm, which is probably quite long. (A natural question to ask is that if such an TM index can be discovered, why not just use that TM directly? I believe it's because levin algorithm doesn't guarantee that the TM that we discover which produces a satisfying assignment is necessarily a valid TM for all inputs x. It could just be we got lucky and found a TM which worked only for this specific case.) [1] https://news.ycombinator.com/item?id=27045091 https://news.ycombinator.com/item?id=27045091