6
$\begingroup$

The following definitions are from Elaine Rich's Automata, Computability and Complexity.

The Class FP: A binary relation $Q$ is in $\mathsf{FP}$ iff there is a deterministic polynomial time algorithm that, given an arbitrary input $x$, can find some $y$ such that $(x,y) \in Q$.

The Class FNP: A binary relation $Q$ is in $\mathsf{FNP}$ iff there is a deterministic polynomial time verifier, given an arbitrary input pair $(x,y)$, determines whether $(x,y) \in Q$. Equivalentely, $Q$ is in $\mathsf{FNP}$ iff there is a nondeterministic polynomial time algorithm that, given an arbitrary input $x$, can find some $y$ such that $(x,y) \in Q$

From the second definition of $\mathsf{FNP}$ it is clear that $\mathsf{FP} \subseteq \mathsf{FNP}$.

However, I don't see why the two definitions of $\mathsf{FNP}$ are equivalent.

In fact, It seems that according to the first definition of $\mathsf{FNP}$, we would have neither $\mathsf{FP} \subseteq \mathsf{FNP}$ nor $\mathsf{FNP} \subseteq \mathsf{FP}$. In fact I think we can prove that $\mathsf{FP} \subseteq \mathsf{FNP}$ doesn't hold:

Proof. Let $R$ be some relation that is not in either $\mathsf{FP}$ or $\mathsf{FNP}$. Define $Q$ as $(x,y) \in Q$ iff either $y=1$ or $y=0z$ and $(x,z) \in R$.

Then clearly $Q$ is in $\mathsf{FP}$: for any $x$, output 1ドル$. But it's not in $\mathsf{FNP}$, since if it were, then for any $(x,z)$ we could decide if it's in $R$ by checking if $(x,0z)$ is in $Q$. QED.

So am I just misinterpreting the definition? Did I make a mistake?

ps. this is discussed somewhat here, but the comment by Joshua doesn't seem to solve it.

Yixin Cao
2,6191 gold badge17 silver badges29 bronze badges
asked Nov 2 at 4:45
$\endgroup$
3
  • 5
    $\begingroup$ The normal definition is that FP is the class of polynomial-time computable functions, i.e., there is a unique output for each input. Anyway, if you quoted thd definitions from the book faithfully, they are indeed confused. It seems the author cannot make her mind whether to force all classes to be closed under enlarging the set of solutions or not. $\endgroup$ Commented Nov 2 at 9:26
  • $\begingroup$ Relevantly, this confusion also appears in Complexity Zoo as it gives two incompatible definitions for FP: one for functions, and a second for predicates. $\endgroup$ Commented Nov 2 at 11:16
  • 3
    $\begingroup$ "FP" is used for two related but distinct concepts, as I explained in my answer to the other Q. However, the definition quoted here seems to agree with neither of them, which makes me think this is simply an error in the book. Using "definition 2" from my other answer, one has (essentially by definition) that "FP is contained in FNP". $\endgroup$ Commented Nov 2 at 18:02

0

Know someone who can answer? Share a link to this question via email, Twitter, or Facebook.

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.