14
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ 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). $\endgroup$
    – Ryan Williams
    Dec 2, 2011 at 4:24
  • $\begingroup$ 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. $\endgroup$
    – Serge Gaspers
    Dec 2, 2011 at 9:49
  • $\begingroup$ 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. $\endgroup$
    – Janne H. Korhonen
    Dec 2, 2011 at 11:11
  • 2
    $\begingroup$ 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. $\endgroup$
    – Janne H. Korhonen
    Dec 14, 2011 at 9:23
  • $\begingroup$ Also it seems that Flum and Grohe give a proof of the theorem in the answer in their book; see Lemma 16.1. $\endgroup$
    – Janne H. Korhonen
    Dec 14, 2011 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.