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.
-
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$Emil Jeřábek– Emil Jeřábek2025年11月02日 09:26:21 +00:00Commented 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$alsips-cl– alsips-cl2025年11月02日 11:16:25 +00:00Commented 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$Joshua Grochow– Joshua Grochow2025年11月02日 18:02:10 +00:00Commented Nov 2 at 18:02