0
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Nov 16, 2022 at 9:27
  • $\begingroup$ 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? $\endgroup$
    – Krish Singal
    Nov 16, 2022 at 16:19
  • $\begingroup$ What is “most natural” depends on the intended application, context, and personal preferences. There is no absolute answer. $\endgroup$
    – Emil Jeřábek
    Nov 17, 2022 at 6:48

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy