[My Computational Complexity Web Log] Universal Search
Psst. Want to know the fastest algorithm for factoring? I can give you an algorithm that is within a constant multiplicative factor of the best possible factoring algorithms.
Actually this is an idea due to Levin. Let p1, p2, ... be a list of all programs. On some input m simulate program p1 for half of your computation time, p2 for a quarter of the time, p3 for an eighth of the time, etc., until one of these programs outputs a factor of m. If pi is the fastest algorithm for factoring then our algorithm will run in time at most 2i times the running time of pi. The multiplicative factor 2i is independent of m but unfortunately could be quite large.
Marcus Hutter gives another algorithm that has a multiplicative factor of 5 but has a large additive constant. The trick is to spend some of your time searching for a proof that an algorithm is correct and runs in certain amount of time. You then only need to simulate the provably fastest algorithm found so far.
Hutter's algorithm works only as fast as the provably best algorithm with a provable running time. It could very well be the case that there is some good heuristic for factoring that does not have a provable running time or proof of correctness. Levin's technique will capture this case.
Of course, neither of these papers gives a practical algorithm as the constants involved go beyond huge. Nevertheless it is still interesting to see the theoretical possibilities of universal search.
Posted by Lance Fortnow to My Computational Complexity Web Log at 5/6/2003 6:58:21 AM
Powered by Blogger Pro