# Optimal NP solvers

Fix $$X \subset \lbrace 0,1 \rbrace^* \times \lbrace 0,1 \rbrace^*$$ an NP-complete search problem e.g. the search form of SAT. Levin search provides an algorithm $$L$$ for solving $$X$$ which is optimal in some sense. Specifically, the algorithm is "Execute all possible programs $$P$$ in dovetailing on the input $$x$$, once some $$P$$ returns answer $$y$$ tests whether it's correct". It is optimal in the sense that given a program $$P$$ that solves $$X$$ with time complexity $$t_P(n)$$, the time complexity $$t_L(n)$$ of $$L$$ satisfies

$$t_L(n) < 2^{|P|}p(t_P(n))$$

where $$p$$ is a fixed polynomial which depends on the precise computation model

$$L$$'s optimality can be formulated in a somewhat stronger way. Namely, for every $$M \subset \lbrace 0,1 \rbrace^*$$ and $$Q$$ a program solving $$X$$ with promise $$M$$ in time $$t^M_Q(n)$$, the time complexity $$t_L^M(n)$$ of $$L$$ restricted to inputs in $$M$$ satisfies

$$t_L^M(n) < 2^{|Q|}q(n, t^M_Q(n))$$

where $$q$$ is a fixed polynomial. The crucial difference is that $$t^M_Q(n)$$ can be e.g. polynomial even if $$P \neq NP$$

The obvious "weakness" of $$L$$ is the large factor $$2^{|Q|}$$ in this bound. It is easy to see that if there is an algorithm satisfying a bound of the same form with $$2^{|Q|}$$ replaced by a polynomial in $$|Q|$$ then $$P = NP$$. This is because we can take $$Q$$ to be a program solving some given instance of $$X$$ by hard-coding the answer. Similarly, if $$2^{|Q|}$$ can be replaced by a sub-exponential function of $$|Q|$$ then the exponential time hypothesis is violated. However, the answer to following question is less obvious (to me):

Assuming the exponential time hypothesis and other well-known conjectures (e.g. non-degeneracy of the polynomial hierarchy, existence of one-way functions) if necessary, is there an algorithm $$A$$ solving $$X$$ s.t. for every $$M \subset \lbrace 0,1 \rbrace^*$$ and $$Q$$ a program solving $$X$$ with promise $$M$$ in time $$t^M_Q(n)$$, the time complexity $$t_A^M(n)$$ of $$A$$ restricted to inputs in $$M$$ satisfies

$$t_A^M(n) < f(|Q|)q(n, t^M_Q(n)) + g(|Q|)$$

where $$q$$ is polynomial, $$f$$ is sub-exponential and $$g$$ is arbitrary

If the answer is positive, can $$f$$ be polynomial? What is the growth rate of $$g$$ (clearly at least exponential under ETH)? If the answer is negative, can polynomial $$f$$ exist if ETH is wrong but $$P \neq NP$$?

Consider the following algorithm (a variant of Levin's algorithm):

Run the first $$n$$ algorithms in parallel. Additionally, run in parallel a brute-force algorithm that tries all possible solutions one by one. (Run all algorithms with the same speed.)

Stop when one of the algorithms finds a solution.

Consider two cases (given an input $$x$$ of length $$n$$):

• $$Q$$ is one of the first $$n$$ algorithms. Then the running time is $$O(n \cdot t^M_Q(n)) \cdot \mathrm{poly}(n)$$.

• $$Q$$ is not one of the first $$n$$ algorithms (thus $$n < 2^{|Q|}$$). Then the running time is bounded by the running time of the brute-force algorithm. We have that the running time is $$2^{n^{O(1)}} = 2^{2^{O(|Q|)}}$$.

We have $$t^M_A(n) \leq \mathrm{poly}(n) \cdot t^M_Q(n) + 2^{2^{O(|Q|)}}.$$

(Here, $$f(n)$$ is polynomial and $$g(n)$$ is double exponential in $$n$$; we can improve the dependance of $$g(n)$$ on $$n$$ by worsening the dependence of $$f(n)$$ on $$n$$.)

• There is a variant of this which satisfies a bound better in some sense, although it is not of the form I requested. Namely, instead of using a brute-force algorithm, run ordinary Levin search. This yields the same bound with the second term replaced by ~ $2^{|Q|}t^M_Q(2^{|Q|})$ – Vanessa Dec 17 '12 at 6:50