In computational complexity theory, the complexity class TFNP is the class of total function problems which can be solved in nondeterministic polynomial time. That is, it is the class of function problems that are guaranteed to have an answer, and this answer can be checked in polynomial time, or equivalently it is the subset of FNP where a solution is guaranteed to exist. The abbreviation TFNP stands for "Total Function Nondeterministic Polynomial".

TFNP contains many natural problems that are of interest to computer scientists. These problems include integer factorization, finding a Nash Equilibrium of a game, and searching for local optima. TFNP is widely conjectured to contain problems that are computationally intractable, and several such problems have been shown to be hard under cryptographic assumptions. However, there are no known unconditional intractability results or results showing NP-hardness of TFNP problems. TFNP is not believed to have any complete problems.

The class TFNP is formally defined as follows.

It was first defined by Megiddo and Papadimitriou in 1989, although TFNP problems and subclasses of TFNP had been defined and studied earlier.

Let x be a mapping, and y a 2-tuple of items in its domain. The binary relation in question P(x,y) has the meaning "the images of both entries of y under x are equal", which, since the mapping is polynomially computable, is polynomially decidable. Moreover, such tuple y must exist for any mapping because of the pigeonhole principle.

The complexity class ${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$ can be defined in two different ways, and those ways are not known to be equivalent. One way applies F to the machine model for ${\displaystyle {\mathsf {NP}}\cap {\mathsf {coNP}}}$. It is known that with this definition, ${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$ coincides with TFNP. To see this, first notice that the inclusion ${\displaystyle {\mathsf {TFNP}}\subseteq {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$ follows easily from the definitions of the classes. All "yes" answers to problems in TFNP can be easily verified by definition, and since problems in TFNP are total, there are no "no" answers, so it is vacuously true that "no" answers can be easily verified. For the reverse inclusion, let R be a binary relation in ${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$. Decompose R into ${\displaystyle R_{1}\cup R_{2}}$ such that ${\displaystyle (x,0y)\in R_{1}}$ precisely when ${\displaystyle (x,y)\in R}$ and y is a "yes" answer, and let R₂ be ⁠${\displaystyle (x,1y)}$⁠ such ⁠${\displaystyle (x,y)\in R}$⁠ and y is a "no" answer. Then the binary relation ${\displaystyle R_{1}\cup R_{2}}$ is in TFNP.

The other definition uses that ${\displaystyle {\mathsf {NP}}\cap {\mathsf {coNP}}}$ is known to be a well-behaved class of decision problems, and applies F to that class. With this definition, if ${\displaystyle {\mathsf {NP}}\cap {\mathsf {coNP}}={\mathsf {P}}}$ then ${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})={\mathsf {\color {Blue}FP}}}$.

NP is one of the most widely studied complexity classes. The conjecture that there are intractable problems in NP is widely accepted and often used as the most basic hardness assumption. Therefore, it is only natural to ask how TFNP is related to NP. It is not difficult to see that solutions to problems in NP can imply solutions to problems in TFNP. However, there are no TFNP problems which are known to be NP-hard. Intuition for this fact comes from the fact that problems in TFNP are total. For a problem to be NP-hard, there must exist a reduction from some NP-complete problem to the problem of interest. A typical reduction from problem A to problem B is performed by creating and analyzing a map that sends "yes" instances of A to "yes" instances of B and "no" instances of A to "no" instances of B. However, TFNP problems are total, so there are no "no" instances for this type of reduction, causing common techniques to be difficult to apply. Beyond this rough intuition, there are several concrete results that suggest that it might be difficult or even impossible to prove NP-hardness for TFNP problems. For example, if any TFNP problem is NP-complete, then NP = coNP, which is generally conjectured to be false, but is still a major open problem in complexity theory. This lack of connections with NP is a major motivation behind the study of TFNP as its own independent class.