In computational complexity theory

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

, the complexity class

Complexity class

In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...

 TFNP is a subclass of FNP

FNP (complexity)

In computational complexity theory, the complexity class FNP is the function problem extension of the decision problem class NP. The name is somewhat of a misnomer, since technically it is a class of binary relations, not functions, as the following formal definition explains:This definition does...

 where a solution is guaranteed to exist. It stands for "Total Function Nondeterministic Polynomial."

A binary relation P(x,y) is in TFNP if and only if there is a deterministic polynomial time algorithm that can determine whether P(x,y) holds given both x and y, and for every x, there exists a y such that P(x,y) holds.

The job of an TFNP algorithm is to establish, given an x give one possible value for a y such that P(x,y) holds.

FP

FP (complexity)

In computational complexity theory, the complexity class FP is the set of function problems which can be solved by a deterministic Turing machine in polynomial time; it is the function problem version of the decision problem class P...

 is a subclass of TFNP. TFNP also contains subclasses PLS

PLS (complexity)

In computational complexity theory, PLS, which stands for Polynomial Local Search, is a complexity class that models the difficulty of finding a locally optimal solution to an optimization problem....

, PPA

PPA (complexity)

PPA is a complexity class, standing for "Polynomial Parity Argument" . Introduced by Christos Papadimitriou in 1994 , PPA is a subclass of TFNP...

, PPAD

PPAD (complexity)

PPAD is a complexity class introduced by Christos Papadimitriou in 1994. PPAD is a subclass of TFNP based on functions that can be shown to be total by a parity argument...

, and PPP

PPP (complexity)

PPP is a complexity class, standing for "Polynomial Pigeonhole Principle". Introduced by Christos Papadimitriou in 1994 , PPP is a subclass of TFNP. It is a class of search problems that can be shown to be total by an application of the pigeonhole principle.PPP is defined as follows...

.

TFNP = FP would imply P

P (complexity)

In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...

 = NP

NP (complexity)

In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...

  coNP, and therefore that factoring and simplex pivoting are in P.

In contrast to FNP, there is no known recursive enumeration of machines for problems in TFNP. It seems that such classes, and therefore TFNP, do not have complete problems.