TFNP

The complexity class F(NP ${\displaystyle \cap }$ 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 NP ${\displaystyle \cap }$ coNP. It is known that with this definition, F(NP ${\displaystyle \cap }$ coNP) coincides with TFNP.[6] To see this, first notice that the inclusion TFNP ⊆ F(NP ${\displaystyle \cap }$ 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 F(NP ${\displaystyle \cap }$ coNP). Decompose R into R₁${\displaystyle \cup }$ R₂ such that (x, 0y) ∈ R₁ precisely when (x, y) ∈ R and y is a "yes" answer, and let R₂ be (x, 1y) such (x, y) ∈ R and y is a "no" answer. Then the binary relation R₁ ∪ R₂ is in TFNP.

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

Intuition behind the lack of NP-hardness results for TFNP problems. The top image shows the typical form of a reduction that shows a problem is NP-hard. Yes instances map to yes instances and no instances map to no instances. The bottom image depicts the intuition for why it is difficult to show TFNP problems are NP-hard. TFNP problems always have a solution and so there is no simple place to map no instances of the original problem.

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,[7] 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.

PLS (standing for "Polynomial Local Search") 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

Given input circuits A and B each with n input and output bits, find x such that A(B(x)) ≤ A(X).

It contains the class CLS.

PPA (standing for "Polynomial time Parity Argument") 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 (standing for "Polynomial time Pigeonhole Principle") 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

Given circuit C with n input and output bits, find x such that C(x) = 0 or x ≠ y such that C(x) = C(y).

PPP contains the classes PPAD and PWPP. Notable problems in this class include the short integer solution problem.[8]

PPAD (standing for "Polynomial time Parity Argument, Directed") 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:

Given circuits S and P with n input and output bits S(0) ≠ 0 and P(0) = 0, find x such that P(S(x)) ≠ x or x ≠ 0 such that S(P(x)) ≠ x.

PPAD is in the intersection of PPA and PPP, and it contains CLS.

CLS (standing for "Continuous Local Search") 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:

Given two Lipschitz continuous functions f and p and parameters ε and λ, find an ε-approximate fixed point of f with respect to p or two points that violate the λ-continuity of p or f.

This class was first defined by Daskalakis and Papadimitriou in 2011.[9] 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 (complexity) (standing for "Function Polynomial") is the class of function problems that can be solved in deterministic polynomial time. FP ${\displaystyle \subseteq }$ 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 (without randomization). If TFNP = FP, then P = NP ∩ coNP, which should be intuitive given the fact that TFNP = F(NP ${\displaystyle \cap }$ coNP). However, it is generally conjectured that P ≠ NP ∩ coNP, and so TFNP ≠ FP.