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.
The class of function problems of the following form:
FNP generalizes NP, which is defined in terms of decision problems only.
Actually the word "function" is misleading, since there could be many valid outputs y. That's unavoidable, since given a predicate F there's no "syntactic" criterion ensuring that y is unique.
FP = FNP if and only if P = NP.
Contains TFNP.
A basic question about FNP problems is whether they're self-reducible; that is, whether they reduce to the corresponding NP decision problems. Although this is true for all NPC problems, [BG94] shows that if EE does not equal NEE, then there is a problem in NP such that no corresponding FNP problem can be reduced to it. [BG94] cites Impagliazzo and Sudan as giving the same conclusion under the assumption that NE does not equal coNE.
The class of TFNP function problems that are guaranteed to have a solution because of the Lovász Local Lemma. Defined in [Pap94b].
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.
The subclass of TFNP function problems that are guaranteed to have a solution because of the lemma that "every finite graph has an even number of odd-degree nodes."
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.