<p>In Chapter 10 of <em>Computational Complexity by Christos Papadimitriou</em>, it is noted that reduction between problems of functional complexity classes are defined as follows:</p>
<p><em>Function problem A reduces to function problem B if the following holds: There are string functions <span class="math-container">$R$</span> and <span class="math-container">$S$</span>, both computable in logarithmic space, such that for any strings <span class="math-container">$x$</span> and <span class="math-container">$z$</span> the following holds: if <span class="math-container">$x$</span> is an instance of A, then <span class="math-container">$R(x)$</span> is an instance of B. Furthermore, if <span class="math-container">$z$</span> is a correct output of <span class="math-container">$R(x)$</span>, then <span class="math-container">$S(z)$</span> is a correct output of x</em></p>
<p>Procedurally, this definition follows from the usual notion of reductions in the space of decision problems. However, my uncertainty lies in the 'power' given to the reduction functions <span class="math-container">$R$</span> and <span class="math-container">$S$</span> . Naturally, I would assume polynomial time computable constraints as an obvious analog to the space of decision problems, however, this is not the case. More specifically, it is true that</p>
<p><span class="math-container">$$
\text{SPACE}(f(n)) \subseteq \text{EXP}(f(n))
$$</span></p>
<p>which implies that</p>
<p><span class="math-container">$$
\text{SPACE}(\log n) \subseteq \text{TIME}(\text{poly}(n))
$$</span></p>
<p>However, the relation in the reverse direction is unknown. This seems to imply that the reduction in functional space is given potentially less power than in decision space. Such discrepancies arise in more obvious cases such as NL where reductions are allowed only logarithmic space to prevent universal equivalence between problems up to reduction. In this case, however, I am struggling to justify the difference in reductive power between functional problems and decisions problems. Would appreciate any and all insight.</p>

CC BY-SA 4.0
2022-11-16T09:27:37.423Z
Both polynomial-time reductions and logspace reductions are among the common choices for reductions among both decision problems and search ("functional") problems. Normally, you'd use the same choice for both. That is, if you prefer poly-time reductions for decision problems, use poly-time reductions for search problems. If you prefer (as Papadimitriou) logspace reductions for decision problems, you also use them for search problems.
Emil Jeřábek
CC BY-SA 4.0
2022-11-16T16:19:39.297Z
I see, thank you. As a follow up, does this mean that the set of complete problems derived from each choice is different? In the case that TIME(exp(n)) $\neq$ SPACE(n), I believe this would be the case. However, since there is no known problem $L \in$ TIME(exp(n)) such that $L \notin$ SPACE(n), the two definitions will produce the same results for all currently known problems. 

If it were the case that TIME(exp(n)) $\neq$ SPACE(n), which definition would then be chosen as the most natural?
Krish Singal
CC BY-SA 4.0
2022-11-17T06:48:57.300Z
What is “most natural” depends on the intended application, context, and personal preferences. There is no absolute answer.
Emil Jeřábek
<cc.complexity-theory><complexity-classes><reductions>
On the Reductions of Functional complexity Classes
Krish Singal
# On the Reductions of Functional complexity Classes

(Asked by: username_0 on 2022-11-16)

In Chapter 10 of *Computational Complexity by Christos Papadimitriou*, it is noted that reduction between problems of functional complexity classes are defined as follows:

*Function problem A reduces to function problem B if the following holds: There are string functions $R$ and $S$, both computable in logarithmic space, such that for any strings $x$ and $z$ the following holds: if $x$ is an instance of A, then $R(x)$ is an instance of B. Furthermore, if $z$ is a correct output of $R(x)$, then $S(z)$ is a correct output of x*

Procedurally, this definition follows from the usual notion of reductions in the space of decision problems. However, my uncertainty lies in the 'power' given to the reduction functions $R$ and $S$ . Naturally, I would assume polynomial time computable constraints as an obvious analog to the space of decision problems, however, this is not the case. More specifically, it is true that

$$
\text{SPACE}(f(n)) \subseteq \text{EXP}(f(n))
$$

which implies that

$$
\text{SPACE}(\log n) \subseteq \text{TIME}(\text{poly}(n))
$$

However, the relation in the reverse direction is unknown. This seems to imply that the reduction in functional space is given potentially less power than in decision space. Such discrepancies arise in more obvious cases such as NL where reductions are allowed only logarithmic space to prevent universal equivalence between problems up to reduction. In this case, however, I am struggling to justify the difference in reductive power between functional problems and decisions problems. Would appreciate any and all insight.

**Tags:** cc.complexity-theory, complexity-classes, reductions

> **Comments:**
> **username_1**: Both polynomial-time reductions and logspace reductions are among the common choices for reductions among both decision problems and search ("functional") problems. Normally, you'd use the same choice for both. That is, if you prefer poly-time reductions for decision problems, use poly-time reductions for search problems. If you prefer (as Papadimitriou) logspace reductions for decision problems, you also use them for search problems.  
> **username_0**: I see, thank you. As a follow up, does this mean that the set of complete problems derived from each choice is different? In the case that TIME(exp(n)) $\neq$ SPACE(n), I believe this would be the case. However, since there is no known problem $L \in$ TIME(exp(n)) such that $L \notin$ SPACE(n), the two definitions will produce the same results for all currently known problems.   If it were the case that TIME(exp(n)) $\neq$ SPACE(n), which definition would then be chosen as the most natural?  
> **username_1**: What is “most natural” depends on the intended application, context, and personal preferences. There is no absolute answer.  

---

## 0 answers

