Class Description

PPADS: Polynomial Parity Argument (Directed, Sink)

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.

Linked From

PPAD: Polynomial Parity Argument (Directed)

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.

Contained in PPA and PPADS.

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].

More about...


PPP: Polynomial Pigeonhole Principle

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.

More about...


PSK: Polynomial Sink

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.

More about...