<p>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:</p>
<p>According to the definition given, a SERF reduction <span class="math-container">$R$</span> is a collection of Turing reductions <span class="math-container">$\{ M_{\epsilon}^{A_{2}} \}_{\epsilon &gt; 0}$</span> from the problem <span class="math-container">$A_{1}$</span> with complexity parameter <span class="math-container">$m_{1}$</span> to the problem <span class="math-container">$A_{2}$</span> with complexity parameter <span class="math-container">$m_{2}$</span> such that the following hold for each <span class="math-container">$\epsilon &gt; 0$</span>:</p>
<ol>
<li><span class="math-container">$M_{\epsilon}^{A_{2}}$</span> runs in time at most <span class="math-container">$poly(|x|)2^{\epsilon m_{1}(x)}$</span>.</li>
<li>If <span class="math-container">$M_{\epsilon}^{A_{2}}$</span> queries <span class="math-container">$A_{2}$</span> on input <span class="math-container">$x'$</span>, then <span class="math-container">$m_{2}(x') \in O( m_{1}(x) )$</span> and <span class="math-container">$|x'| = |x|^{O(1)}$</span>.</li>
</ol>
<p>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 <span class="math-container">$k$</span>-SAT the complexity parameter could be the number of variables, the number of clauses or the binary length of the SAT expression.</p>
<p>Now, suppose we have <span class="math-container">$2$</span> SERF reductions <span class="math-container">$R_{1}$</span> from <span class="math-container">$A_{1}$</span> with complexity parameter <span class="math-container">$m_{1}$</span> to <span class="math-container">$A_{2}$</span> with complexity parameter <span class="math-container">$m_{2}$</span> and <span class="math-container">$R_{2}$</span> from <span class="math-container">$A_{2}$</span> to <span class="math-container">$A_{3}$</span> with complexity parameter <span class="math-container">$m_{3}$</span>. We will define the composition in a meaningful way and show that it is also a SERF reduction from <span class="math-container">$A_{1}$</span> to <span class="math-container">$A_{3}$</span>.</p>
<p>The composition of two SERF reductions must also be a collection, where we compose the two Turing reductions for each fixed <span class="math-container">$\epsilon &gt; 0$</span>.We need to check that the restriction of the definition still hold for each <span class="math-container">$\epsilon&gt;0$</span>.</p>
<p>To begin with, we can simply compose the two Turing reductions <span class="math-container">$M_{\epsilon}^{A_{2}}$</span> and <span class="math-container">$M_{\epsilon}^{A_{3}}$</span> to obtain <span class="math-container">$M_{\epsilon}^{'A_{3}}$</span>. This is possible since Turing reductions are composable. In short, whenever <span class="math-container">$M_{\epsilon}^{A_{2}}$</span> queries <span class="math-container">$A_{2}$</span> on input <span class="math-container">$x'$</span>, instead of using the oracle for <span class="math-container">$A_{2}$</span> we call <span class="math-container">$M_{\epsilon}^{A_{3}}$</span> on input <span class="math-container">$x'$</span>. It remains only to see if the restrictions are respected:</p>
<p>Restriction 2: Since <span class="math-container">$R_{2}$</span> is a SERF reduction we have that each query <span class="math-container">$x''$</span> to <span class="math-container">$A_{3}$</span> in <span class="math-container">$M_{\epsilon}^{'A_{3}}$</span> satisfies <span class="math-container">$m_{3}(x'') \in O(m_{2}(x'))$</span> and <span class="math-container">$|x''| = |x'|^{O(1)}$</span> where <span class="math-container">$x'$</span> is the input to <span class="math-container">$M_{\epsilon}^{A_{3}}$</span>. Now in turn since <span class="math-container">$R_{1}$</span> is a SERF reduction we know that <span class="math-container">$m_{2}(x') \in O(m_{1}(x))$</span> and <span class="math-container">$|x'| = |x|^{O(1)}$</span>. Combining the two we have that <span class="math-container">$m_{3}(x'') \in O(m_{2}(x')) \in O(m_{1}(x))$</span> and <span class="math-container">$|x''| = |x'|^{O(1)} = |x|^{O(1)}$</span> so the restriction is satisfied.</p>
<p>Restriction 1: <span class="math-container">$M_{\epsilon}^{'A_{3}}$</span> may call <span class="math-container">$M_{\epsilon}^{A_{3}}$</span> at most once for each running step of <span class="math-container">$M_{\epsilon}^{A_{2}}$</span>. <span class="math-container">$M_{\epsilon}^{A_{2}}$</span> runs in time <span class="math-container">$poly(|x|)2^{\epsilon m_{1}(x)}$</span>. Each call to <span class="math-container">$M_{\epsilon}^{A_{3}}$</span> takes time at most <span class="math-container">$poly(|x'|)2^{\epsilon m_{2}(x')} = poly(|x|)2^{\epsilon c m_{1}(x)}$</span> where the equality follows from Restriction 2. Thus the running time in total is at most the product of the two, <span class="math-container">$poly(|x|)2^{\epsilon m_{1}(x)} * poly(|x|)2^{\epsilon c m_{1}(x)} $</span> = <span class="math-container">$poly(|x|)2^{\epsilon (1+c) m_{1}(x)}$</span>  thus the restriction is satisfied.</p>
<p>Since this holds for all <span class="math-container">$\epsilon &gt; 0$</span>, it follows that the composition of two SERF reductions is also a SERF reduction and thus SERF reductions are transitive.</p>

CC BY-SA 4.0
2024-02-04T16:19:51.343Z
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.
chazisop
CC BY-SA 4.0
2024-01-29T12:36:00.243Z
2024-02-04T16:17:52.427Z
2024-02-04T16:17:52.427Z
chazisop
<p>I have a question concerning the SERF-reducibility of <a href="https://drive.google.com/file/d/1Y951Y9IehqDU16fhmIdLKg9OsClyMrtX/view?usp=drivesdk" rel="nofollow noreferrer">Impagliazzo, Paturi and Zane</a> and subexponential algorithms.</p>
<p><em><strong>My question is:</strong></em> is a composition of two SERF reductions  a SERF reduction? Are there a write-up of the proof somewhere?</p>
<p>Little work is <a href="https://cstheory.stackexchange.com/questions/9233/serf-reducibility-and-subexponential-algorithms">here.</a></p>

CC BY-SA 4.0
2024-01-26T17:13:50.870Z
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,
chazisop
<cc.complexity-theory><reference-request>
Operation on Sub-exponential Reduction
S. M.
# Operation on Sub-exponential Reduction

(Asked by: username_0 on 2024-01-25)

I have a question concerning the SERF-reducibility of [Impagliazzo, Paturi and Zane](https://drive.google.com/file/d/1Y951Y9IehqDU16fhmIdLKg9OsClyMrtX/view?usp=drivesdk) 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.](https://cstheory.stackexchange.com/questions/9233/serf-reducibility-and-subexponential-algorithms)

**Tags:** cc.complexity-theory, reference-request
> **Comments:**
> **username_1**: 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,  

---

## 1 answers

### Answer by username_1 on 2024-01-29. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_1**: 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.  

---

