SERF-reducibility and subexponential algorithms I have a question concerning the SERF-reducibility of Impagliazzo, Paturi and Zane and subexponential algorithms. The definition of SERF-reducibility gives the following:


  If $P_1$ is SERF-reducible to $P_2$ and there $O(2^{\varepsilon n})$ algorithm for $P_2$ for each $\varepsilon &gt; 0$, then there is $O(2^{\varepsilon n})$ algorithm for $P_1$ for each $\varepsilon &gt; 0$. (Hardness parameter for both problems is denoted by $n$.)


Some sources seem to imply that the following also holds:


  If $P_1$ is SERF-reducible to $P_2$ and there $O(2^{o(n)})$ algorithm for $A_2$, then there is $O(2^{o(n)})$ algorithm for $P_1$.


My question is, does this latter claim actually hold and if it does, is there a write-up of the proof somewhere?

As a background, I've been trying to understand the area around the Exponential Time Hypothesis. IPZ define subexponential problems as ones that have $O(2^{\varepsilon n})$ algorithm for each $\varepsilon &gt; 0$, but this apparently is not sufficient in the light of the current knowledge to imply the existence of a subexponential algorithm for the problem. The same gap seems to be present in the SERF reducibility, but I am partially expecting that I am missing something here...
EDIT: As pointed out by Ryan in the comments, a problem may have a nonuniform algorithm with running time $O(2^{\epsilon n})$ for any constant $\epsilon &gt; 0$ (the algorithm has access to $\epsilon$) but no uniform $2^{o(n)}$ time algorithm.

As a SERF reduction is a family of Turing reductions, one for each $\epsilon&gt;0$, I conclude that they can only be used to obtain $O(2^{\epsilon n})$ time algorithms from $O(2^{\epsilon n})$ or $2^{o(n)}$ time algorithms.



The following Theorem is proved by Chen et al. [2009].

Theorem 2.4. Let $f(k)$ be a nondecreasing and unbounded function, and let $Q$ be a parameterized problem. Then the following statements are equivalent:
(1) $Q$ can be solved in time $O(2^{\delta f(k)}p(n))$ for any constant $\delta &gt; 0$, where $p$ is a polynomial;
(2) $Q$ can be solved in time $2^{o(f(k))} q(n)$, where $q$ is a polynomial.

Taking $f(k)=n$ we obtain that a problem has a $O(2^{\epsilon n})$ time algorithm for every $\epsilon&gt;0$ if and only if it has a $2^{o(n)}$ time algorithm.

It is mentioned in the paper by Chen et al. that this equivalence had been intuitively used before but that it was causing some confusion among researchers.