TFNP

From Wikipedia, the free encyclopedia

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 coNP, and therefore that factoring and simplex pivoting are in P.

TFNP != FP would imply NP = coNP.

Unlike FNP, there are no known recursive enumerations for problems in TFNP. Therefore, it seems that TFNP does not have complete problems.

[edit] References

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