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 > 0$, then there is $O(2^{\varepsilon n})$ algorithm for $P_1$ for each $\varepsilon > 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 > 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...
SERF-reducibility and subexponential algorithms
cc.complexity theory;reference request
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 > 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>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 > 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>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.