# 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 > 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...

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.

• Just a note: there are some other conditions that need to be assumed for their proof to work. For one, $f$ must be efficiently computable. Secondly, there must be a single uniform algorithm $A$ which achieves $2^{\delta f(k)}$ for each $\delta$ (think of $\delta$ as another input to $A$). It is entirely possible that without these conditions, a problem can satisfy (1) but not (2). Commented Dec 2, 2011 at 4:24
• Right. Taking Theorem 2.4 out of its context, these two conditions were lost. In the paper, footnote 1 gives the condition on $f$ and the second condition is given in Remark 2. Commented Dec 2, 2011 at 9:49
• This pretty much answers all my questions about this! Thank you very much. As an interesting remark, while it seems that SERF-reductions do not preserve the existence of subexponential algorithms, it would seem that the Sparsification Lemma of IPZ in fact is sufficiently strong to give us a $2^{o(n)}$ algorithm to k-SAT if there is $2^{o(m)}$ algorithm. Commented Dec 2, 2011 at 11:11
• A final note in case someone stumbles on this later: apparently some sources use "nonuniform" definition of subexponential time (for all $\varepsilon > 0$ there is a $O(2^{\varepsilon n})$ algorithm) and others use "uniform" definition (there is $2^{o(n)}$ algorithm.) In particular IPZ use the former. For the latter, you have to alter the definition of SERF reduction so that the parameter $\varepsilon$ is given to the reduction as input; compare with the above theorem of Chen et al. For details, see e.g. Chapter 16 of Parameterized Complexity Theory (2006) by Flum and Grohe. Commented Dec 14, 2011 at 9:23
• Also it seems that Flum and Grohe give a proof of the theorem in the answer in their book; see Lemma 16.1. Commented Dec 14, 2011 at 9:28