2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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^*)$. $\endgroup$
    – chi
    May 22, 2023 at 12:25
  • $\begingroup$ @chi Yes, that is correct. Sorry. $\endgroup$ May 22, 2023 at 19:58

1 Answer 1

4
$\begingroup$

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").

$\endgroup$
3
  • $\begingroup$ Can this be extended to arbitrary binary relations (as function problems are)? Right now, this only works for functions ($g$ is a function). $\endgroup$ May 22, 2023 at 4:20
  • 1
    $\begingroup$ 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. $\endgroup$
    – Arno
    May 22, 2023 at 10:58
  • $\begingroup$ @Arno, oops, thank you for correcting my erroneous answer. $\endgroup$
    – D.W.
    May 22, 2023 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.