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

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

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|}q(t_P(n))$$

where $q$ 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(t^M_Q(n))$$

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(t^M_Q(n)) + g(|Q|)$$

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

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