<p>Consider the following algorithm (a variant of Levin's algorithm):</p>
<blockquote>
<p>Run the first <span class="math-container">$n$</span> 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.)</p>
<p>Stop when one of the algorithms finds a solution.</p>
</blockquote>
<p>Consider two cases (given an input <span class="math-container">$x$</span> of length <span class="math-container">$n$</span>):</p>
<ul>
<li><p><span class="math-container">$Q$</span> is one of the first <span class="math-container">$n$</span> algorithms. Then the running time is <span class="math-container">$O(n \cdot t^M_Q(n)) \cdot \mathrm{poly}(n)$</span>.</p>
</li>
<li><p><span class="math-container">$Q$</span> is not one of the first <span class="math-container">$n$</span> algorithms (thus <span class="math-container">$n &lt; 2^{|Q|}$</span>). Then the running time is bounded by the running time of the brute-force algorithm. We have that the running time is  <span class="math-container">$2^{n^{O(1)}} = 2^{2^{O(|Q|)}}$</span>.</p>
</li>
</ul>
<p>We have
<span class="math-container">$$t^M_A(n) \leq \mathrm{poly}(n) \cdot t^M_Q(n)  + 2^{2^{O(|Q|)}}.$$</span></p>
<p>(Here, <span class="math-container">$f(n)$</span> is polynomial and <span class="math-container">$g(n)$</span> is double exponential in <span class="math-container">$n$</span>; we can improve the dependance of <span class="math-container">$g(n)$</span> on <span class="math-container">$n$</span> by worsening the dependence of <span class="math-container">$f(n)$</span> on <span class="math-container">$n$</span>.)</p>

CC BY-SA 3.0
2012-12-17T06:50:37.113Z
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
CC BY-SA 3.0
2012-12-16T06:45:14.980Z
2012-12-16T07:06:44.427Z
2020-06-17T09:38:08.363Z
Yury
<p>Fix <span class="math-container">$X \subset \lbrace 0,1 \rbrace^* \times \lbrace 0,1 \rbrace^*$</span> an NP-complete search problem e.g. the search form of SAT. Levin search provides an algorithm <span class="math-container">$L$</span> for solving <span class="math-container">$X$</span> which is optimal in some sense. Specifically, the algorithm is &quot;Execute all possible programs <span class="math-container">$P$</span> in dovetailing on the input <span class="math-container">$x$</span>, once some <span class="math-container">$P$</span> returns answer <span class="math-container">$y$</span> tests whether it's correct&quot;. It is optimal in the sense that given a program <span class="math-container">$P$</span> that solves <span class="math-container">$X$</span> with time complexity <span class="math-container">$t_P(n)$</span>, the time complexity <span class="math-container">$t_L(n)$</span> of <span class="math-container">$L$</span> satisfies</p>
<p><span class="math-container">$$t_L(n) &lt; 2^{|P|}p(t_P(n))$$</span></p>
<p>where <span class="math-container">$p$</span> is a fixed polynomial which depends on the precise computation model</p>
<p><span class="math-container">$L$</span>'s optimality can be formulated in a somewhat stronger way. Namely, for every <span class="math-container">$M \subset \lbrace 0,1 \rbrace^*$</span> and <span class="math-container">$Q$</span> a program solving <span class="math-container">$X$</span> with promise <span class="math-container">$M$</span> in time <span class="math-container">$t^M_Q(n)$</span>, the time complexity <span class="math-container">$t_L^M(n)$</span> of <span class="math-container">$L$</span> restricted to inputs in <span class="math-container">$M$</span> satisfies</p>
<p><span class="math-container">$$t_L^M(n) &lt; 2^{|Q|}q(n, t^M_Q(n))$$</span></p>
<p>where <span class="math-container">$q$</span> is a fixed polynomial. The crucial difference is that <span class="math-container">$t^M_Q(n)$</span> can be e.g. polynomial even if <span class="math-container">$P \neq NP$</span></p>
<p>The obvious &quot;weakness&quot; of <span class="math-container">$L$</span> is the large factor <span class="math-container">$2^{|Q|}$</span> in this bound. It is easy to see that if there is an algorithm satisfying a bound of the same form with <span class="math-container">$2^{|Q|}$</span> replaced by a polynomial in <span class="math-container">$|Q|$</span> then <span class="math-container">$P = NP$</span>. This is because we can take <span class="math-container">$Q$</span> to be a program solving some given instance of <span class="math-container">$X$</span> by hard-coding the answer. Similarly, if <span class="math-container">$2^{|Q|}$</span> can be replaced by a sub-exponential function of <span class="math-container">$|Q|$</span> then the exponential time hypothesis is violated. However, the answer to following question is less obvious (to me):</p>
<blockquote>
<p>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 <span class="math-container">$A$</span> solving <span class="math-container">$X$</span> s.t. for every <span class="math-container">$M \subset \lbrace 0,1 \rbrace^*$</span> and <span class="math-container">$Q$</span> a program solving <span class="math-container">$X$</span> with promise <span class="math-container">$M$</span> in time <span class="math-container">$t^M_Q(n)$</span>, the time complexity <span class="math-container">$t_A^M(n)$</span> of <span class="math-container">$A$</span> restricted to inputs in <span class="math-container">$M$</span> satisfies</p>
<p><span class="math-container">$$t_A^M(n) &lt; f(|Q|)q(n, t^M_Q(n)) + g(|Q|)$$</span></p>
<p>where <span class="math-container">$q$</span> is polynomial, <span class="math-container">$f$</span> is sub-exponential and <span class="math-container">$g$</span> is arbitrary</p>
</blockquote>
<p>If the answer is positive, can <span class="math-container">$f$</span> be polynomial? What is the growth rate of <span class="math-container">$g$</span> (clearly at least exponential under ETH)? If the answer is negative, can polynomial <span class="math-container">$f$</span> exist if ETH is wrong but <span class="math-container">$P \neq NP$</span>?</p>

<cc.complexity-theory><time-complexity><p-vs-np>
Optimal NP solvers
Vanessa
# Optimal NP solvers

(Asked by: username_0 on 2012-12-15)

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

**Tags:** cc.complexity-theory, time-complexity, p-vs-np

---

## 1 answers

### Answer by username_1 on 2012-12-16. Score: 12 | Accepted answer

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

> **Comments:**
> **username_0**: 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|})$  

---

