<p>In addition to Joshua's extensive answer, I want to add the following definitions from Elaine Ruch her <em>Automata, Computability and Complexity</em>.</p>
<blockquote>
<p><strong>The Class FP</strong>: A binary relation <span class="math-container">$Q$</span> is in <span class="math-container">$\mathsf{FP}$</span> iff there is a deterministic polynomial time algorithm that, given an arbitrary input <span class="math-container">$x$</span>, can find some <span class="math-container">$y$</span> such that <span class="math-container">$(x,y) \in Q$</span>.</p>
<p><strong>The Class FNP</strong>: A binary relation <span class="math-container">$Q$</span> is in <span class="math-container">$\mathsf{FNP}$</span> iff there is a deterministic polynomial time verifier, given an arbitrary input pair <span class="math-container">$(x,y)$</span>, determines whether <span class="math-container">$(x,y) \in Q$</span>. Equivalentely, <span class="math-container">$Q$</span> is in <span class="math-container">$\mathsf{FNP}$</span> iff there is a nondeterministic polynomial time algorithm that, given an arbitrary input <span class="math-container">$x$</span>, can find some <span class="math-container">$y$</span> such that <span class="math-container">$(x,y) \in Q$</span></p>
</blockquote>
<p>From these definitions it is clear that <span class="math-container">$\mathsf{FP} \subseteq \mathsf{TFNP} \subseteq \mathsf{FNP}$</span>. She also briefly talks about problems outside of <span class="math-container">$\mathsf{FNP}$</span>.</p>
<p>For me, this has been the most satisfying resource that consists out of one single page I've found since a long time.</p>

CC BY-SA 3.0
2017-03-28T17:02:23.780Z
After I have given these definition some thought, I suspect that the two 'equivalent' definitions of $\mathsf{FNP}$ aren't equivalent at all...
Auberon
CC BY-SA 4.0
2018-07-03T22:35:12.687Z
I think to get equivalence one needs to assume the relation is p-bounded (that is, there is a polynomial $p$ such that if $\exists y$ such that $(x,y) \in Q$, then there is such a $y$ with $|y| \leq p(|x|)$). Also, one has to specify what it means for a "nondeterministic algorithm to find a $y$" - that is, what does it mean for a nondeterministic algorithm to "make an output"? This is part of why I like the NPMV family of definitions...
Joshua Grochow
CC BY-SA 3.0
2017-03-27T22:42:35.077Z
2017-03-27T22:42:35.077Z
2020-06-17T09:38:08.363Z
Auberon
<p>Emil Jerabek's comment is a nice summary, but I wanted to point out that there are other classes with clearer definitions that capture more-or-less the same concept, and to clarify the relation between all these things.</p>

<p>[Warning: while I believe I've gotten the definitions right, some of the things below reflect my personal preferences - I've tried to be clear about where that was.]</p>

<p>In the deterministic world, a function class is just a collection of functions (in the usual, mathematical sense of the word "function", that is, a map $\Sigma^* \to \Sigma^*$). Occasionally we want to allow "partial functions," whose output is "undefined" for certain inputs. (Equivalently, functions that are defined on a subset of $\Sigma^*$ rather than all of it.)</p>

<p>Unfortunately, there are two different definitions for $\mathsf{FP}$ floating around, and as far as I can tell they are not equivalent (though they are "morally" equivalent). </p>

<ul>
<li>$\mathsf{FP}$ (definition 1) is the class of functions that can be computed in polynomial-time. Whenever you see $\mathsf{FP}$ and its not in a context where people are talking about $\mathsf{FNP}, \mathsf{TFNP}$, this is the definition I assume.</li>
</ul>

<p>In the nondeterministic world things get a little funny. There, it is convenient to allow "partial, multi-valued functions." It would be natural to also call such a thing a <em>binary relation</em>, that is, a subset of $\Sigma^* \times \Sigma^*$. But from the complexity point of view it is often philosophically and mentally useful to think of these things as "nondeterministic functions." I think many of these definitions are clarified by the following classes (whose definitions are completely standardized, if not very well-known):</p>

<ul>
<li><p>$\mathsf{NPMV}$: The class of "partial, multi-valued functions" computable by a nondeterministic machine in polynomial time. What this means is there is a poly-time nondeterministic machine, and on input $x$, on each nondeterministic branch it may choose to accept and make some output, or reject and make no output. The "multi-valued" output on input $x$ is then the set of all outputs on all nondeterministic branches when given $x$ as input. Note that this set can be empty, so as a "multi-valued function" this may only be partial. If we think of it in terms of binary relations, this corresponds to the relation $\{(x,y) : y \text{ is output by some branch of the computation on input } x\}$.</p></li>
<li><p>$\mathsf{NPMV}_t$: Total "functions" in $\mathsf{NPMV}$, that is, on every input $x$, at least one branch accepts (and therefore makes an output, by definition)</p></li>
<li><p>$\mathsf{NPSV}$: Single-valued (potentially partial) functions in $\mathsf{NPMV}$. There is some flexibility here, however, in that multiple branches may accept, but if any branch accepts, then all accepting branches must be guaranteed to make the <em>same</em> output (so that it really is single-valued). However, it is still possible that no branch accepts, so the function is only a "partial function" (i.e. not defined on all of $\Sigma^*$).</p></li>
<li><p>$\mathsf{NPSV}_t$: Single-valued total functions in $\mathsf{NPSV}$. These really are functions, in the usual sense of the word, $\Sigma^* \to \Sigma^*$. It is a not-too-hard exercise to see that $\mathsf{NPSV}_t = \mathsf{FP}^{\mathsf{NP} \cap \mathsf{coNP}}$ (using Def 1 for FP above).</p></li>
</ul>

<p>When we talk about potentially multi-valued functions, talking about containment of complexity classes isn't really useful any more: $\mathsf{NPMV} \not\subseteq \mathsf{NPSV}$ unconditionally simply because $\mathsf{NPSV}$ doesn't contain any multi-valued "functions", but $\mathsf{NPMV}$ does. Instead, we talk about "c-containment", denoted $\subseteq_c$. A (potentially partial, multi-valued) function $f$ refines a (potentially partial multi-valued) function $g$ if: (1) for every input $x$ for which $g$ makes some output, so does $f$, and (2) the outputs of $f$ are always a subset of the outputs of $g$. The proper question is then whether every $\mathsf{NPMV}$ "function" has an $\mathsf{NPSV}$ refinement. If so, we write $\mathsf{NPMV} \subseteq_c \mathsf{NPSV}$. </p>

<ul>
<li>$\mathsf{PF}$ (a little less standard) is the class of (potentially partial) functions computable in poly-time. That is, a function $f\colon D \to \Sigma^*$ ($D \subseteq \Sigma^*$) is in $\mathsf{PF}$ if there is a poly-time deterministic machine such that, on inputs $x \in D$ the machine outputs $f(x)$, and on inputs $x \notin D$ the machine makes no output (/rejects/says "no"/however you want to phrase it).</li>
</ul>

<hr>

<ul>
<li><p>$\mathsf{FNP}$ is a class of "function problems" (rather than a class of functions). I would also call $\mathsf{FNP}$ a "relational class", but really whatever words you use to describe it you need to clarify yourself afterwards, which is why I'm not particularly partial to this definition. To any binary relation $R \subseteq \Sigma^* \times \Sigma^*$ there is an associated "function problem." What is a function problem? I don't have a clean mathematical definition the way I do for language/function/relation; rather, it's defined by what a valid solution is: a valid solution to the function problem associated to $R$ is any (potentially partial) function $f$ such that if $(\exists y)[R(x,y)]$ then $f$ outputs any such $y$, and otherwise $f$ makes no output. $\mathsf{FNP}$ is the class of function problems associated to relations $R$ such that $R \in \mathsf{P}$ (when considered as a language of pairs) and is p-balanced. So $\mathsf{FNP}$ is not a class of functions, nor a class of languages, but a class of "function problems," where "problem" here is defined roughly in terms of what it means to solve it.</p></li>
<li><p>$\mathsf{TFNP}$ is then the class of function problems in $\mathsf{FNP}$ - defined by a relation $R$ as above - such $R$ is total, in the sense that for every $x$ there exists a $y$ such that $R(x,y)$.</p></li>
</ul>

<p>In order to not have to write things like "If every $\mathsf{FNP}$ (resp., $\mathsf{TFNP}$) function problem has a solution in $\mathsf{PF}$ (resp., $\mathsf{FP}$ according to above definition), then..." in this context one uses Definition 2 of $\mathsf{FP}$, which is:</p>

<ul>
<li>$\mathsf{FP}$ (definition 2) is the class of function problems in $\mathsf{FNP}$ which have a poly-time solution. One can assume that the solution (=function) here is total by picking a special string $y_0$ that is not a valid $y$ for any $x$, and having the function output $y_0$ when there would otherwise be no valid $y$. (If needed, we can modify the relation $R$ by prepending every $y$ with a 1, and then take $y_0$ to be the string 0; this doesn't change the complexity of anything involved).</li>
</ul>

<hr>

<p>Here's how these various definitions relate to one another, $\mathsf{FNP} \subseteq \mathsf{FP}$ (definition 2, which is what you should assume because it's in a context where it's being compared with $\mathsf{FNP}$) is equivalent to $\mathsf{NPMV} \subseteq_c \mathsf{PF}$. $\mathsf{TFNP} \subseteq \mathsf{FP}$ (def 2) is equivalent to $\mathsf{NPMV}_t \subseteq_c \mathsf{FP}$ (def 1).</p>

CC BY-SA 3.0
2017-03-23T11:36:46.603Z
Thank you for your extensive answer. I'm trying to digest it and it has been very helpful so far. I assume, however, you meant **FP** $\subseteq$ **FNP** and **FP** $\subseteq$ **TFNP** in the last paragraph?
Auberon
CC BY-SA 3.0
2017-03-23T16:28:25.287Z
@Auberon: No, the last paragraph is translating between various conjectures. It says that $\mathsf{FNP} \subseteq \mathsf{FP} \Leftrightarrow \mathsf{NPMV} \subseteq_c \mathsf{PF}$, etc.
Joshua Grochow
CC BY-SA 4.0
2020-09-06T16:48:53.223Z
Those definitions are really useful to tackle function complexity questions. Do you have pointers to their definitions in the literature ?
wazdra
CC BY-SA 4.0
2020-09-07T03:33:31.703Z
@wazdra Selman 1994 A taxonomy of complexity classes of functions https://doi.org/10.1016/S0022-0000(05)80009-1 and references therein.
Joshua Grochow
CC BY-SA 4.0
2020-09-07T03:50:35.973Z
@1.. NP = UP (or P^UP) is not known to collapse PH (nor do we know an oracle rel to whcih this is false - one of my favorite oracle questions). I don't think we know containment either way between P^UP and P^TFNP. Morally TFNP is like NP intersect coNP, so I'd expect NP in P^TFNP to collapse PH, but I'd need to think about it a bit more because of how awkward it is to use TFNP as an oracle (another reason I prefer NPMV, NPSV, etc)...
Joshua Grochow
CC BY-SA 4.0
2019-05-26T15:07:24.403Z
@JoshuaGrochow $NP\in P^{TFNP}$ or $NP\in P^{UP}$ possible or the hierarchy collapses? Also does $P^{UP}$ in $P^{TFNP}$ or vice versa hold (it seems plausible as there seem no implication either way)?
Turbo
CC BY-SA 4.0
2021-02-04T04:39:45.740Z
For FNP what kind of access is the verifier allowed to have to the binary relation R? How does the verifier “read” the problem instance?
gen
CC BY-SA 4.0
2021-02-04T05:38:12.070Z
@gen There isn't really a "verifier" per se in the definition of FNP. It's just that the relation R must itself be in P. If you want to think of it as a verifier, then depending on how you're thinking about it, the verifier gets access to the pair (x,y), just as in the definition of NP.
Joshua Grochow
CC BY-SA 3.0
2017-03-21T16:12:15.530Z
2017-03-21T16:12:15.530Z
Joshua Grochow
<p>In his book <em>Computational Complexity</em>, Papadimitriou defines <strong>FNP</strong> as follows:</p>
<blockquote>
<p>Suppose that <span class="math-container">$L$</span> is a language in <strong>NP</strong>. By Proposition 9.1, there is a polynomial-time decidable, polynomially balanced relation <span class="math-container">$R_L$</span> such that for all strings <span class="math-container">$x$</span>: There is a string <span class="math-container">$y$</span> with <span class="math-container">$R_L(x,y)$</span> if and only if <span class="math-container">$x\in L$</span>. The function problem associated with <span class="math-container">$L$</span>, denoted <span class="math-container">$FL$</span>, is the following computational problem:</p>
<p>Given <span class="math-container">$x$</span>, find a string <span class="math-container">$y$</span> such that <span class="math-container">$R_L(x,y)$</span> if such a string exists; if no such string exists, return &quot;no&quot;.</p>
<p>The class of all function problems associated as above with language in <strong>NP</strong> is called <strong>FNP</strong>. <strong>FP</strong> is the subclass resulting if we only consider function problems in <strong>FNP</strong> that can be solved in polynomial time.</p>
<p>(...)</p>
<p>(...), we call a problem <span class="math-container">$R$</span> in <strong>FNP</strong> <em>total</em> if for every string <span class="math-container">$x$</span> there is at least one <span class="math-container">$y$</span> such that <span class="math-container">$R(x,y)$</span>. The subclass of <strong>FNP</strong> containing all total function problems is denoted <strong>TFNP</strong>.</p>
</blockquote>
<p>In a venn diagram in the chapter overview, Papadimitriou implies that <strong>FP</strong> <span class="math-container">$\subseteq$</span> <strong>TFNP</strong> <span class="math-container">$\subseteq$</span> <strong>FNP</strong>.</p>
<p>I have a hard time understanding why exactly it holds that <strong>FP</strong> <span class="math-container">$\subseteq$</span> <strong>TFNP</strong> since problems in <strong>FP</strong> do not have to be total per se.</p>
<p>To gain a better understanding, I've been plowing through literature to find a waterproof definition of <strong>FP</strong>,<strong>FNP</strong> and sorts, without success.</p>
<p>In my very (humble) opinion, I think there is little (correct!) didactic material of these topics.</p>
<p>For decision problems, the classes are sets of languages (i.e. sets of strings).</p>
<p>What exactly are the classes for function problems? Are they sets of relations, languages, ... ? What is a solid definition?</p>

CC BY-SA 3.0
2017-03-21T15:56:21.960Z
The common notation is somewhat sloppy. First, FP was and is used to denote the class of poly-time *functions* (hence total) outside the context of NP search problems, where it has been redefined. Second, every search problem solvable in polynomial time has a total extension solvable in polynomial time, so in that sense, there is not much real difference between a total and non-total definition of FP, so the two are conflated by abuse of language.
Emil Jeřábek
<complexity>
What exactly are the classes FP, FNP and TFNP?
Auberon
# What exactly are the classes FP, FNP and TFNP?

(Asked by: username_0 on 2017-03-21)

In his book *Computational Complexity*, Papadimitriou defines **FNP** as follows:

> Suppose that $L$ is a language in **NP**. By Proposition 9.1, there is a polynomial-time decidable, polynomially balanced relation $R\_L$ such that for all strings $x$: There is a string $y$ with $R\_L(x,y)$ if and only if $x\in L$. The function problem associated with $L$, denoted $FL$, is the following computational problem:
>
> Given $x$, find a string $y$ such that $R\_L(x,y)$ if such a string exists; if no such string exists, return "no".
>
> The class of all function problems associated as above with language in **NP** is called **FNP**. **FP** is the subclass resulting if we only consider function problems in **FNP** that can be solved in polynomial time.
>
> (...)
>
> (...), we call a problem $R$ in **FNP** *total* if for every string $x$ there is at least one $y$ such that $R(x,y)$. The subclass of **FNP** containing all total function problems is denoted **TFNP**.

In a venn diagram in the chapter overview, Papadimitriou implies that **FP** $\subseteq$ **TFNP** $\subseteq$ **FNP**.

I have a hard time understanding why exactly it holds that **FP** $\subseteq$ **TFNP** since problems in **FP** do not have to be total per se.

To gain a better understanding, I've been plowing through literature to find a waterproof definition of **FP**,**FNP** and sorts, without success.

In my very (humble) opinion, I think there is little (correct!) didactic material of these topics.

For decision problems, the classes are sets of languages (i.e. sets of strings).

What exactly are the classes for function problems? Are they sets of relations, languages, ... ? What is a solid definition?

**Tags:** complexity
> **Comments:**
> **username_1**: The common notation is somewhat sloppy. First, FP was and is used to denote the class of poly-time *functions* (hence total) outside the context of NP search problems, where it has been redefined. Second, every search problem solvable in polynomial time has a total extension solvable in polynomial time, so in that sense, there is not much real difference between a total and non-total definition of FP, so the two are conflated by abuse of language.  

---

## 2 answers

### Answer by username_2 on 2017-03-21. Score: 16 | Accepted answer

Emil Jerabek's comment is a nice summary, but I wanted to point out that there are other classes with clearer definitions that capture more-or-less the same concept, and to clarify the relation between all these things.

[Warning: while I believe I've gotten the definitions right, some of the things below reflect my personal preferences - I've tried to be clear about where that was.]

In the deterministic world, a function class is just a collection of functions (in the usual, mathematical sense of the word "function", that is, a map $\Sigma^\* \to \Sigma^\*$). Occasionally we want to allow "partial functions," whose output is "undefined" for certain inputs. (Equivalently, functions that are defined on a subset of $\Sigma^\*$ rather than all of it.)

Unfortunately, there are two different definitions for $\mathsf{FP}$ floating around, and as far as I can tell they are not equivalent (though they are "morally" equivalent).

* $\mathsf{FP}$ (definition 1) is the class of functions that can be computed in polynomial-time. Whenever you see $\mathsf{FP}$ and its not in a context where people are talking about $\mathsf{FNP}, \mathsf{TFNP}$, this is the definition I assume.

In the nondeterministic world things get a little funny. There, it is convenient to allow "partial, multi-valued functions." It would be natural to also call such a thing a *binary relation*, that is, a subset of $\Sigma^\* \times \Sigma^\*$. But from the complexity point of view it is often philosophically and mentally useful to think of these things as "nondeterministic functions." I think many of these definitions are clarified by the following classes (whose definitions are completely standardized, if not very well-known):

* $\mathsf{NPMV}$: The class of "partial, multi-valued functions" computable by a nondeterministic machine in polynomial time. What this means is there is a poly-time nondeterministic machine, and on input $x$, on each nondeterministic branch it may choose to accept and make some output, or reject and make no output. The "multi-valued" output on input $x$ is then the set of all outputs on all nondeterministic branches when given $x$ as input. Note that this set can be empty, so as a "multi-valued function" this may only be partial. If we think of it in terms of binary relations, this corresponds to the relation $\{(x,y) : y \text{ is output by some branch of the computation on input } x\}$.
* $\mathsf{NPMV}\_t$: Total "functions" in $\mathsf{NPMV}$, that is, on every input $x$, at least one branch accepts (and therefore makes an output, by definition)
* $\mathsf{NPSV}$: Single-valued (potentially partial) functions in $\mathsf{NPMV}$. There is some flexibility here, however, in that multiple branches may accept, but if any branch accepts, then all accepting branches must be guaranteed to make the *same* output (so that it really is single-valued). However, it is still possible that no branch accepts, so the function is only a "partial function" (i.e. not defined on all of $\Sigma^\*$).
* $\mathsf{NPSV}\_t$: Single-valued total functions in $\mathsf{NPSV}$. These really are functions, in the usual sense of the word, $\Sigma^\* \to \Sigma^\*$. It is a not-too-hard exercise to see that $\mathsf{NPSV}\_t = \mathsf{FP}^{\mathsf{NP} \cap \mathsf{coNP}}$ (using Def 1 for FP above).

When we talk about potentially multi-valued functions, talking about containment of complexity classes isn't really useful any more: $\mathsf{NPMV} \not\subseteq \mathsf{NPSV}$ unconditionally simply because $\mathsf{NPSV}$ doesn't contain any multi-valued "functions", but $\mathsf{NPMV}$ does. Instead, we talk about "c-containment", denoted $\subseteq\_c$. A (potentially partial, multi-valued) function $f$ refines a (potentially partial multi-valued) function $g$ if: (1) for every input $x$ for which $g$ makes some output, so does $f$, and (2) the outputs of $f$ are always a subset of the outputs of $g$. The proper question is then whether every $\mathsf{NPMV}$ "function" has an $\mathsf{NPSV}$ refinement. If so, we write $\mathsf{NPMV} \subseteq\_c \mathsf{NPSV}$.

* $\mathsf{PF}$ (a little less standard) is the class of (potentially partial) functions computable in poly-time. That is, a function $f\colon D \to \Sigma^\*$ ($D \subseteq \Sigma^\*$) is in $\mathsf{PF}$ if there is a poly-time deterministic machine such that, on inputs $x \in D$ the machine outputs $f(x)$, and on inputs $x \notin D$ the machine makes no output (/rejects/says "no"/however you want to phrase it).

---

* $\mathsf{FNP}$ is a class of "function problems" (rather than a class of functions). I would also call $\mathsf{FNP}$ a "relational class", but really whatever words you use to describe it you need to clarify yourself afterwards, which is why I'm not particularly partial to this definition. To any binary relation $R \subseteq \Sigma^\* \times \Sigma^\*$ there is an associated "function problem." What is a function problem? I don't have a clean mathematical definition the way I do for language/function/relation; rather, it's defined by what a valid solution is: a valid solution to the function problem associated to $R$ is any (potentially partial) function $f$ such that if $(\exists y)[R(x,y)]$ then $f$ outputs any such $y$, and otherwise $f$ makes no output. $\mathsf{FNP}$ is the class of function problems associated to relations $R$ such that $R \in \mathsf{P}$ (when considered as a language of pairs) and is p-balanced. So $\mathsf{FNP}$ is not a class of functions, nor a class of languages, but a class of "function problems," where "problem" here is defined roughly in terms of what it means to solve it.
* $\mathsf{TFNP}$ is then the class of function problems in $\mathsf{FNP}$ - defined by a relation $R$ as above - such $R$ is total, in the sense that for every $x$ there exists a $y$ such that $R(x,y)$.

In order to not have to write things like "If every $\mathsf{FNP}$ (resp., $\mathsf{TFNP}$) function problem has a solution in $\mathsf{PF}$ (resp., $\mathsf{FP}$ according to above definition), then..." in this context one uses Definition 2 of $\mathsf{FP}$, which is:

* $\mathsf{FP}$ (definition 2) is the class of function problems in $\mathsf{FNP}$ which have a poly-time solution. One can assume that the solution (=function) here is total by picking a special string $y\_0$ that is not a valid $y$ for any $x$, and having the function output $y\_0$ when there would otherwise be no valid $y$. (If needed, we can modify the relation $R$ by prepending every $y$ with a 1, and then take $y\_0$ to be the string 0; this doesn't change the complexity of anything involved).

---

Here's how these various definitions relate to one another, $\mathsf{FNP} \subseteq \mathsf{FP}$ (definition 2, which is what you should assume because it's in a context where it's being compared with $\mathsf{FNP}$) is equivalent to $\mathsf{NPMV} \subseteq\_c \mathsf{PF}$. $\mathsf{TFNP} \subseteq \mathsf{FP}$ (def 2) is equivalent to $\mathsf{NPMV}\_t \subseteq\_c \mathsf{FP}$ (def 1).

> **Comments:**
> **username_0**: Thank you for your extensive answer. I'm trying to digest it and it has been very helpful so far. I assume, however, you meant **FP** $\subseteq$ **FNP** and **FP** $\subseteq$ **TFNP** in the last paragraph?  
> **username_2**: @Auberon: No, the last paragraph is translating between various conjectures. It says that $\mathsf{FNP} \subseteq \mathsf{FP} \Leftrightarrow \mathsf{NPMV} \subseteq_c \mathsf{PF}$, etc.  
> **username_4**: @JoshuaGrochow $NP\in P^{TFNP}$ or $NP\in P^{UP}$ possible or the hierarchy collapses? Also does $P^{UP}$ in $P^{TFNP}$ or vice versa hold (it seems plausible as there seem no implication either way)?  
> **username_3**: Those definitions are really useful to tackle function complexity questions. Do you have pointers to their definitions in the literature ?  
> **username_2**: @wazdra Selman 1994 A taxonomy of complexity classes of functions https://doi.org/10.1016/S0022-0000(05)80009-1 and references therein.  
> **username_2**: @1.. NP = UP (or P^UP) is not known to collapse PH (nor do we know an oracle rel to whcih this is false - one of my favorite oracle questions). I don't think we know containment either way between P^UP and P^TFNP. Morally TFNP is like NP intersect coNP, so I'd expect NP in P^TFNP to collapse PH, but I'd need to think about it a bit more because of how awkward it is to use TFNP as an oracle (another reason I prefer NPMV, NPSV, etc)...  
> **username_5**: For FNP what kind of access is the verifier allowed to have to the binary relation R? How does the verifier “read” the problem instance?  
> **username_2**: @gen There isn't really a "verifier" per se in the definition of FNP. It's just that the relation R must itself be in P. If you want to think of it as a verifier, then depending on how you're thinking about it, the verifier gets access to the pair (x,y), just as in the definition of NP.  

---

### Answer by username_0 on 2017-03-27. Score: 5

In addition to Joshua's extensive answer, I want to add the following definitions from Elaine Ruch her *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 these definitions it is clear that $\mathsf{FP} \subseteq \mathsf{TFNP} \subseteq \mathsf{FNP}$. She also briefly talks about problems outside of $\mathsf{FNP}$.

For me, this has been the most satisfying resource that consists out of one single page I've found since a long time.

> **Comments:**
> **username_0**: After I have given these definition some thought, I suspect that the two 'equivalent' definitions of $\mathsf{FNP}$ aren't equivalent at all...  
> **username_2**: I think to get equivalence one needs to assume the relation is p-bounded (that is, there is a polynomial $p$ such that if $\exists y$ such that $(x,y) \in Q$, then there is such a $y$ with $|y| \leq p(|x|)$). Also, one has to specify what it means for a "nondeterministic algorithm to find a $y$" - that is, what does it mean for a nondeterministic algorithm to "make an output"? This is part of why I like the NPMV family of definitions...  

---

