*** Welcome to piglix ***

TFNP


In computational complexity theory, the complexity class TFNP is a subclass of FNP where a solution is guaranteed to exist. It stands for "Total Function Nondeterministic Polynomial."

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

FP is a subclass of TFNP. TFNP also contains subclasses PLS, PPA, PPAD, and PPP.

TFNP coincides with F(NP coNP). TFNP = FP would imply P = NP 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.


...
Wikipedia

...