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 impra

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