Defined in [Pap94b]; see also [BCE+95].
Same as PPA, except now the graph is directed, and we're asked to find a sink.
Contained in PPP.
Contains PPAD.
Defined in [Pap94b]; see also [BCE+95].
Same as PPA, except now the graph is directed, and we're asked to find either a source or a sink.
NASH, the problem of finding a Nash equilibrium in a normal form game of two or more players with specified utilities, is in PPAD [Pap94b], and proved to be complete for PPAD with four players in [DGP05], and shortly after extended to the case of three players [DP05] and independently [CD05].
There exists an oracle relative to which PPP is not contained in PPAD [BCE+95].There exists an oracle relative to which PPAD is not contained in BQP [Li11].
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.
Yeah, I'm told that's what the S and K stand for. Go figure.
The class of total function problems definable as follows: given a directed graph of indegree and outdegree at most 1, and given a source, find a sink.
Defined in [Pap90].
Equals PPADS.