Computational Complexity

Tuesday, May 06, 2003

 
Universal Search

Posted by Lance

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 p₁, p₂, ... be a list of all programs. On some input m simulate program p₁ for half of your computation time, p₂ for a quarter of the time, p₃ for an eighth of the time, etc., until one of these programs outputs a factor of m. If p_i is the fastest algorithm for factoring then our algorithm will run in time at most 2ⁱ times the running time of p_i. The multiplicative factor 2ⁱ 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.

5:58 AM # 0 comments

Comment Feeds: This Post All