Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 12 down vote accepted

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

share|cite|improve this answer
Thanks a lot for your answer! – Squark Dec 16 '12 at 21:37
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|})$ – Squark Dec 17 '12 at 6:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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