# Operation on Sub-exponential Reduction

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.

• 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, Jan 26 at 17:13

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.

• Please help this question I found this paper but this paper it's very difficult to understand, would write simpler answer like this. Feb 1 at 18:24
• I do not see what is the relation of $\epsilon$ in the subscript of the machine to its running time (where I see some unrelated constant(?) $c$. This applies both to the definition on the first and the running time computation at the end of the write-up. Would edit your answer by writing $\epsilon$ instead of $c$? Feb 2 at 22:20
• 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. Feb 4 at 16:19