- 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 which is at most polynomially longer than x such that P(x,y) holds.
The job of a TFNP algorithm is to establish, given an x, one possible value for a y such that P(x,y) holds.
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.
- Megiddo and Papadimitriou (1989)
- Megiddo and Papadimitriou. A Note on Total Functions, Existence Theorems and Computational Complexity (1989).