# Constructing equivalent (to a polynomial-time degree) decision problems from function problems

Let's say we're some function problem, $$R \subseteq \Sigma^* \times \Sigma^*$$, where $$\Sigma = \{0, 1\}$$ and some oracle $$O_R$$ that solves $$R$$.

Now, we're given some language, $$L \subseteq \Sigma^*$$ and an associated oracle $$O_L$$ that solves $$L$$.

We say $$R =_{poly} L$$ if a machine equipped with $$O_L$$ can solve $$R$$ AND a machine equipped with $$O_R$$ can solve $$L$$.

Is there some function that maps $$f \colon \mathcal{P}(\Sigma^* \times \Sigma^*) \mapsto \mathcal{P}(\Sigma^*)$$ such that $$R =_{poly} f(R) \: \forall R$$?

My requirement for $$f$$ is that it must computable. As a bonus, and this isn't really quantifiable, but I would like for it to be "neat;" i.e. it should be able to be written as a "short" human-readable algorithm in the English language.

My question basically boils down to converting function problems to decision problems, such that they are polynomial-time equivalent problems.

• The line "Is there some function" is confusing to me. Above you defined $=_{poly}$ as a relation between relations (function problems) and languages. Instead, in this line $\omega =_{poly} f(\omega)$ uses it between a pair of words and a word, which makes no sense. I believe you want something like $R =_{poly} f(R)$ and $f : \mathcal{P}(\Sigma^*\times\Sigma^*) \to \mathcal{P}(\Sigma^*)$.
– chi
May 22, 2023 at 12:25
• @chi Yes, that is correct. Sorry. May 22, 2023 at 19:58

# Special case: computing a (single-valued) function

In the special case where the relation $$R$$ corresponds to a (single-valued) function, call it $$g$$, then yes, there is an equivalence. Suppose the function problem is to compute the function $$g$$. Define the language $$L$$ by

$$L=\{\langle x,i,b \rangle \mid x \in \{0,1\}^*, g(x)_i=b\},$$

i.e., $$L$$ consists of all triples $$\langle x,i,b \rangle$$ such that the $$i$$th bit of the output is $$b$$ when the input is $$x$$. Assume that we consider $$g(x)_i$$ to be $$\bot$$ if $$i$$ is past the end of $$g(x)$$.

Then given an algorithm or oracle to decide $$L$$, you can immediately compute $$g$$ (by computing it a bit at a time, trying all three possibilities for $$b$$ for each $$i$$), and given an algorithm or oracle to compute $$g$$, you can immediately decide $$L$$. Moreover this a polynomial-time reduction in both directions, assuming the length of $$g(x)$$ is polynomial in the length of $$x$$.

# General case

I don't know. I am not aware of any way to define such an equivalence, for a general relation $$R$$ (which might be "multi-valued").

• Can this be extended to arbitrary binary relations (as function problems are)? Right now, this only works for functions ($g$ is a function). May 22, 2023 at 4:20
• Your construction for the multivalued case doesn't work. While $R$ is going to be polytime reducible to $L$, there is no reason why $L$ would be polytime reducible to $R$. If we just get some output from $R$, we don't know whether there is a different output that would indeed extend $s$ or not.
– Arno
May 22, 2023 at 10:58
• @Arno, oops, thank you for correcting my erroneous answer.
– D.W.
May 22, 2023 at 15:54