Optimal NP solvers

Question

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$?

Answer 1

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$.)