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."

: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 is a subclass of TFNP. TFNP also contains subclasses PLS, PPA, and PPAD.

TFNP = FP would imply P = NP $cap$ coNP, and therefore that factoring and simplex pivoting are in P.

TFNP ≠ FP would imply NP = coNP.

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.

References

* Megiddo and Papadimitriou. [http://citeseer.ist.psu.edu/megiddo89note.html A Note on Total Functions, Existence Theorems and Computational Complexity (1989)] .