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


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

  • $\begingroup$ 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|})$ $\endgroup$
    – Vanessa
    Commented Dec 17, 2012 at 6:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.