Towards a practical universal search

Universal Search is an asymptotically optimal way of searching the space of programs computing solution candidates for quickly verifiable problems. Despite the algorithm’s simplicity and remarkable theoretical prop-erties, a potentially huge constant slowdown factor has kept it from being used much in practice. Here we greatly bias the search with domain-knowledge, essen-tially by assigning short codes to programs consist-ing of few but powerful domain-specific instructions. This greatly reduces the slowdown factor and makes the method practically useful. We also show that this approach, when encoding random seeds, can signifi-cantly reduce the expected search time of stochastic domain-specific algorithms. We further present a con-crete study where Practical Universal Search (PUnS) is successfully used to combine algorithms for solving satisfiability problems