Non-Incremental Universal Search for problems with quickly verifiable solutions (Levin 1973)

• View n-th bitstring (0,1,01,10,11,100,…) as a possible program for a universal Turing machine.

• Until problem solved: for all n: execute one instruction of n-th bitstring every 2n steps on average.

• Asymptotically optimal: Suppose unknown fastest program solves problem of size k within f(k) steps.

• Lsearch will take at most O(2n f(k)) = O(f(k)) steps.

Previous slide

Next slide

Back to first slide

View graphic version