3
$\begingroup$

I have a question concerning the SERF-reducibility of Impagliazzo, Paturi and Zane and subexponential algorithms.

My question is: is a composition of two SERF reductions a SERF reduction? Are there a write-up of the proof somewhere?

Little work is here.

$\endgroup$
1
  • $\begingroup$ The answer follows almost directly from the definition. You got 2 families of Turing reductions, can you compose them into a single one? Hint from the paper: SERF-reducibility is transitive, $\endgroup$
    – chazisop
    Jan 26 at 17:13

1 Answer 1

3
$\begingroup$

In the paper you cite in your question it is already mentioned that SERF reductions are transitive, which typically follows from the closure of reductions under composition. Here's a proof:

According to the definition given, a SERF reduction $R$ is a collection of Turing reductions $\{ M_{\epsilon}^{A_{2}} \}_{\epsilon > 0}$ from the problem $A_{1}$ with complexity parameter $m_{1}$ to the problem $A_{2}$ with complexity parameter $m_{2}$ such that the following hold for each $\epsilon > 0$:

  1. $M_{\epsilon}^{A_{2}}$ runs in time at most $poly(|x|)2^{\epsilon m_{1}(x)}$.
  2. If $M_{\epsilon}^{A_{2}}$ queries $A_{2}$ on input $x'$, then $m_{2}(x') \in O( m_{1}(x) )$ and $|x'| = |x|^{O(1)}$.

The notion of complexity parameter is explained in section 1.1.2 of the paper and simply is a generalization of using the input or solution size to characterize the complexity and/or size of relevant quantities. E.g. for the problem $k$-SAT the complexity parameter could be the number of variables, the number of clauses or the binary length of the SAT expression.

Now, suppose we have $2$ SERF reductions $R_{1}$ from $A_{1}$ with complexity parameter $m_{1}$ to $A_{2}$ with complexity parameter $m_{2}$ and $R_{2}$ from $A_{2}$ to $A_{3}$ with complexity parameter $m_{3}$. We will define the composition in a meaningful way and show that it is also a SERF reduction from $A_{1}$ to $A_{3}$.

The composition of two SERF reductions must also be a collection, where we compose the two Turing reductions for each fixed $\epsilon > 0$.We need to check that the restriction of the definition still hold for each $\epsilon>0$.

To begin with, we can simply compose the two Turing reductions $M_{\epsilon}^{A_{2}}$ and $M_{\epsilon}^{A_{3}}$ to obtain $M_{\epsilon}^{'A_{3}}$. This is possible since Turing reductions are composable. In short, whenever $M_{\epsilon}^{A_{2}}$ queries $A_{2}$ on input $x'$, instead of using the oracle for $A_{2}$ we call $M_{\epsilon}^{A_{3}}$ on input $x'$. It remains only to see if the restrictions are respected:

Restriction 2: Since $R_{2}$ is a SERF reduction we have that each query $x''$ to $A_{3}$ in $M_{\epsilon}^{'A_{3}}$ satisfies $m_{3}(x'') \in O(m_{2}(x'))$ and $|x''| = |x'|^{O(1)}$ where $x'$ is the input to $M_{\epsilon}^{A_{3}}$. Now in turn since $R_{1}$ is a SERF reduction we know that $m_{2}(x') \in O(m_{1}(x))$ and $|x'| = |x|^{O(1)}$. Combining the two we have that $m_{3}(x'') \in O(m_{2}(x')) \in O(m_{1}(x))$ and $|x''| = |x'|^{O(1)} = |x|^{O(1)}$ so the restriction is satisfied.

Restriction 1: $M_{\epsilon}^{'A_{3}}$ may call $M_{\epsilon}^{A_{3}}$ at most once for each running step of $M_{\epsilon}^{A_{2}}$. $M_{\epsilon}^{A_{2}}$ runs in time $poly(|x|)2^{\epsilon m_{1}(x)}$. Each call to $M_{\epsilon}^{A_{3}}$ takes time at most $poly(|x'|)2^{\epsilon m_{2}(x')} = poly(|x|)2^{\epsilon c m_{1}(x)}$ where the equality follows from Restriction 2. Thus the running time in total is at most the product of the two, $poly(|x|)2^{\epsilon m_{1}(x)} * poly(|x|)2^{\epsilon c m_{1}(x)} $ = $poly(|x|)2^{\epsilon (1+c) m_{1}(x)}$ thus the restriction is satisfied.

Since this holds for all $\epsilon > 0$, it follows that the composition of two SERF reductions is also a SERF reduction and thus SERF reductions are transitive.

$\endgroup$
1
  • 1
    $\begingroup$ Oh, apologies I misread the original paper. This adds an additional complication that the composition created works for $\epsilon' = (1+c) \epsilon$. But since such a TM exists for each $\epsilon > 0$, we end up with a collection for all $\epsilon >0$ as needed. $\endgroup$
    – chazisop
    Feb 4 at 16:19

Your Answer

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

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