# TFNP

Jump to navigation
Jump to search

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, PPAD, and PPP.

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.

## References

- Megiddo and Papadimitriou. A Note on Total Functions, Existence Theorems and Computational Complexity (1989).