<p><strong>EDIT:</strong> 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.</p>

<p>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.</p>

<hr>

<p>The following Theorem is proved by <a href="http://www.cdm.depaul.edu/SoC/research/Documents/Kanj01.pdf">Chen et al. [2009]</a>.</p>

<p><strong>Theorem 2.4</strong>. Let $f(k)$ be a nondecreasing and unbounded function, and let $Q$ be a parameterized problem. Then the following statements are equivalent:<br>
(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;<br>
(2) $Q$ can be solved in time $2^{o(f(k))} q(n)$, where $q$ is a polynomial.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-12-02T04:24:30.627Z
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).
Ryan Williams
CC BY-SA 3.0
2011-12-02T09:49:10.113Z
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.
Serge Gaspers
CC BY-SA 3.0
2011-12-02T11:11:38.580Z
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.
Janne H. Korhonen
CC BY-SA 3.0
2011-12-14T09:23:10.303Z
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.
Janne H. Korhonen
CC BY-SA 3.0
2011-12-14T09:28:27.073Z
Also it seems that Flum and Grohe give a proof of the theorem in the answer in their book; see Lemma 16.1.
Janne H. Korhonen
CC BY-SA 3.0
2011-12-02T01:16:22.723Z
2011-12-02T10:27:11.857Z
2011-12-02T10:27:11.857Z
Serge Gaspers
<p>I have a question concerning the SERF-reducibility of <a href="http://cseweb.ucsd.edu/~russell/ipz.pdf">Impagliazzo, Paturi and Zane</a> and subexponential algorithms. The definition of SERF-reducibility gives the following:</p>

<blockquote>
  <p>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$.)</p>
</blockquote>

<p>Some sources seem to imply that the following also holds:</p>

<blockquote>
  <p>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$.</p>
</blockquote>

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

<p>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...</p>

<cc.complexity-theory><reference-request>
SERF-reducibility and subexponential algorithms
Janne H. Korhonen
# SERF-reducibility and subexponential algorithms

(Asked by: username_0 on 2011-12-01)

I have a question concerning the SERF-reducibility of [Impagliazzo, Paturi and Zane](http://cseweb.ucsd.edu/~russell/ipz.pdf) 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...

**Tags:** cc.complexity-theory, reference-request


---

## 1 answers

### Answer by username_1 on 2011-12-02. Score: 8 | Accepted answer

**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]](http://www.cdm.depaul.edu/SoC/research/Documents/Kanj01.pdf).

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

> **Comments:**
> **username_2**: 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).  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_0**: Also it seems that Flum and Grohe give a proof of the theorem in the answer in their book; see Lemma 16.1.  

---

