PPAD (complexity)

PPAD is a complexity class, standing for "Polynomial Parity Arguments on Directed graphs". Introduced by Christos Papadimitriou in 1994, PPAD is a subclass of TFNP based on functions that can be shown to be total by a parity argument. [cite journal | author = Christos Papadimitriou | year = 1994 | title = On the complexity of the parity argument and other inefficient proofs of existence | journal = Journal of Computer and System Sciences | volume = 48 | issue = 3 | pages = 498–532 | url = http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf | doi = 10.1016/S0022-0000(05)80063-7] [cite web | author = Lance Fortnow | year = 2005 | title = What is PPAD? | url = http://weblog.fortnow.com/2005/12/what-is-ppad.html | accessdate = 2007-01-29]

Definition

TFNP is the class of function problems in FNP that are guaranteed to be total. Formally speaking:

:A binary relation P("x","y") is in TFNP if and only if there is a deterministic polynomial time algorithm that can determine whether P("x","y") holds given both "x" and "y", and for every "x", there exists a "y" such that P("x","y") holds.

Informally, PPAD is the subclass of TFNP where the guarantee that there exists a "y" such that P("x","y") holds is based on a parity argument on a directed graph. The class is formally defined by specifying one of its complete problems:

:G is a (possibly exponentially large) directed graph with no isolated vertices, and with every vertex having at most one predecessor and one successor. G is specified by giving a polynomial-time computable function f("v") that returns the predecessor and successor (if they exist) of the vertex "v". Given a vertex "s" in G with no precedessor, find a vertex "t≠s" with no predecessor or no successor. In other words, we want any source or sink of the directed graph other than "s".

Such a "t" must exist if an "s" does, because the structure of G means that vertices with only one neighbour come in pairs. In particular, given "s", we can find such a "t" at the other end of the string starting at "s". (Note that this may take exponential time if we just evaluate f repeatedly.)

Relationship to other complexity classes

PPAD is contained in (but not known to be equal) to PPA (the corresponding class of parity arguments for "undirected" graphs) which is contained in TFNP.

Other notable complete problems

Finding the Nash equilibrium on a 2-player game. [cite conference | author = Xi Cheni and Xiaotie Deng | title = Setting the Complexity of 2-Player Nash Equilibrium | booktitle = Electronic Colloquium on Computational Complexity, Report No. 140 | year = 2005 | url = http://eccc.hpi-web.de/eccc-reports/2005/TR05-140/Paper.pdf]

References