In computational complexity theory, the complexity classTFNP 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.
Formal Definition
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.
The complexity class F 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 NP coNP. It is known that with this definition, F coincides with TFNP. To see this, first notice that the inclusion TFNP ⊆ F 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 F. Decompose R into R1R2 such that ∈ R1 precisely when ∈ R and y is a "yes" answer, and let R2 be such ∈ R and y is a "no" answer. Then the binary relation R1 ∪ R2 is in TFNP. The other definition uses that NP coNP is known to be a well-behaved class of decision problems, and applies F to that class. With this definition, if NP coNP = P then F = FP.
Connection to 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.
Notable Subclasses
The structure of TFNP is often studied through the study of its subclasses. These subclasses are defined by the mathematical theorem by which solutions to the problems are guaranteed. One appeal of studying subclasses of TFNP is that although TFNP is believed not to have any complete problems, these subclasses are defined by a certain complete problem, making them easier to reason about.
PLS
is a class of problems designed to model the process of searching for a local optimum for a function. In particular, it is the class of total function problems that are polynomial-time reducible to the following problem It contains the class CLS.
PPA
is the class of problems whose solution is guaranteed by the handshaking lemma: any undirected graph with an odd degree vertex must have another odd degree vertex. It contains the subclasses PWPP and PPAD.
PPP
is the class of problems whose solution is guaranteed by the Pigeonhole principle. More precisely, it is the class of problems that can be reduced in polynomial time to the Pigeon problem, defined as follows PPP contains the classes PPAD and PWPP. Notable problems in this class include the short integer solution problem.
PPAD
is a restriction of PPA to problems whose solutions are guaranteed by a directed version of the handshake lemma. It is often defined as the set of problems that are polynomial-time reducible to End-of-a-Line: PPAD is in the intersection of PPA and PPP, and it contains CLS.
CLS
CLS is a class of search problems designed to model the process of finding a local optima of a continuous function over a continuous domain. It is defined as the class of problems that are polynomial-time reducible to the Continuous Localpoint problem: This class was first defined by Daskalakis and Papadimitriou in 2011. It is contained in the intersection of PPAD and PLS, and was designed to be a class of relatively simple optimization problems that still contains many interesting problems that are believed to be hard.
FP
is the class of function problems that can be solved in deterministic polynomial time. FP CLS, and it is conjectured that this inclusion is strict. This class represents the class of function problems that are believed to be computationally tractable. If TFNP = FP, then P = NP ∩ coNP, which should be intuitive given the fact that TFNP = F. However, it is generally conjectured that P ≠ NP ∩ coNP, and so TFNP ≠ FP.
