The subclass of TFNP function problems that are guaranteed to have a solution because of the lemma that "every finite directed acyclic graph has a sink."
More precisely, for each input, there's a finite set of solutions (i.e. strings), and a polynomial-time algorithm that computes a cost for each solution, and a neighboring solution of lower cost provided that one exists. Then the problem is to return any solution that has cost less than or equal to all of its neighbors. (In other words, a local optimum.)
(Note: In the Zookeeper's humble opinion, PLS should have been defined as follows: there exist polynomial-time algorithms that compute the cost of a solution, and the set of all neighbors of a given solution, not just a single solution of lower cost. Of course we'd require that every solution has only polynomially many neighbors. The two definitions are not obviously equivalent, and it's conceivable that knowing all the neighbors would be helpful -- for example, in simulated annealing one sometimes makes uphill moves.)
(Note to Note: The equivalance of these classes was shown (though not stated explicitly) in Theorem 1 of [JPY88].)
There exists an oracle relative to which PLS is not contained in FBQP [Aar03].
Also, there exist oracles relative to which PLS is not contained in PPA [BM04] or PPP [GHJ+22], and PPA and PPP are not contained in PLS [Mor01].
[CT07] conjecture that if PPAD is in P, then PLS is in P.
Has the same relation to BQP as FNP does to NP.
There exists an oracle relative to which PLS is not contained in FBQP [Aar03].
Defined in [Pap94b]; see also [BCE+95].
The subclass of TFNP function problems that are guaranteed to have a solution because of the lemma that "all graphs of maximum degree 2 have an even number of leaves."
More precisely, there's a polynomial-time algorithm that, given any string, computes its 'neighbor' strings (of which there are at most two). Then given a leaf string (i.e. one with only one neighbor), the problem is to output another leaf string.
As an example, suppose you're given a cubic graph (one where every vertex has degree 3), and a Hamiltonian cycle H on that graph. Then by making a sequence of modifications to H (albeit possibly exponentially many), it is always possible to find a second Hamilton cycle (see [Pap94]). So this problem is in PPA.
Another problem in PPA is finding an Arrow-Debreu equilibrium, given the goods and utility functions of traders in a marketplace.
Jeřábek [Jeř12] showed that computing the square root mod n and finding quadratic nonresidues mod n are both in PPA. Further, integer factorization is in PPA under the assumption of a generalized Riemann hypothesis.
A complete problem for PPA is Sperner's lemma for non-orientable 3-manifolds. [Gri01]
Contained in TFNP.
Contains PPAD.
There exist oracles relative to which PPA does not contain PLS [BM04] and PPP [BCE+95]. There also exists an oracle relative to which PPA is not contained in PPP [BCE+95].
Defined in [Pap94b]; see also [BCE+95].
The subclass of TFNP function problems that are guaranteed to have a solution because of the Pigeonhole Principle.
More precisely, we're given a Boolean circuit, that maps n-bit strings to n-bit strings. The problem is to return either an input that maps to 0n, or two inputs that map to the same output.
Contained in TFNP.
Contains PPADS.
[BCE+95] give oracles relative to which PPP is not contained in PPA and PPAD, and PPA is not contained in PPP.
[Mor01] gives an oracle relative to which PPP is not contained in PLS.
[GHJ+22] proves there exists an oracle relative to which PLS is not contained in PPP.
The class of function problems of the following form:
Can be considered as the functional analogue of NP ∩ coNP. Defined in [MP91].
Contained in FNP.
Subclasses include PPA, PPP, and PLS.