TFNP
Sign in to saveAlso known as Total Function NP
In computational complexity theory, the complexity class TFNP is the class of total function problems that can be solved in nondeterministic polynomial time. That is, it is the class of function problems that are guaranteed to have an answer, and this answer can be checked in polynomial time, or equivalently it is the subset of FNP where a solution is guaranteed to exist. The abbreviation TFNP stands for "Total Function Nondeterministic Polynomial".
~13 min read
Article
15 sectionsContents
- Formal definition
- Examples
- Pigeonhole principle problem
- Connections to other complexity classes
- F(NP ∩ coNP)
- Connection to NP
- Notable subclasses
- PLS
- PPA
- PPP
- PPAD
- CLS
- EOPL and UEOPL
- FP
- References
In computational complexity theory, the complexity class TFNP is the class of total function problems that can be solved in nondeterministic polynomial time. That is, it is the class of function problems that are guaranteed to have an answer, and this answer can be checked in polynomial time, or equivalently it is the subset of FNP where a solution is guaranteed to exist. The abbreviation TFNP stands for "Total Function Nondeterministic Polynomial".
TFNP contains many natural problems that are of interest to computer scientists. These problems include integer factorization, finding a Nash equilibrium of a game, and searching for local optima. TFNP is widely conjectured to contain problems that are computationally intractable, and several such problems have been shown to be hard under cryptographic assumptions. However, there are no known unconditional intractability results or results showing TFNP-hardness of TFNP problems. In fact, TFNP is believed not to have any complete problems.