What exactly are the classes FP, FNP and TFNP?

Question

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?

Answer 1

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

Answer 2

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.