"TFNP is the class of total function problems which can be solved in nondeterministic polynomial time", i.e. we don't consider decision problems (as for NP), but total functions.
This class contains quite some interesting subclasses, such as PLS (solution can be found via Local Search), PPA (solution exists because of a Parity Argument), PPP (solution exists because of a Pigeonhole Principle), PPAD (solution exists because of a Directed Parity Argument), CLS, ...
aleph_minus_one|7 months ago
> https://en.wikipedia.org/wiki/TFNP
"TFNP is the class of total function problems which can be solved in nondeterministic polynomial time", i.e. we don't consider decision problems (as for NP), but total functions.
This class contains quite some interesting subclasses, such as PLS (solution can be found via Local Search), PPA (solution exists because of a Parity Argument), PPP (solution exists because of a Pigeonhole Principle), PPAD (solution exists because of a Directed Parity Argument), CLS, ...
In interesting article which explains this topic quite well is https://inference-review.com/article/when-existence-is-ineff...