PPAD (complexity)

In computer science, PPAD ("Polynomial Parity Arguments on Directed graphs") is a complexity class 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. The class attracted significant attention in the field of algorithmic game theory because it contains the problem of computing a Nash equilibrium, and this problem was shown by Chen and Deng in 2005 to be complete for the class.

PPAD is a class of problems that are believed to be hard, but obtaining PPAD-completeness is a weaker evidence of intractability than that of obtaining NP-completeness. PPAD problems cannot be NP-complete, for the technical reason that NP is a class of decision problems, but the answer of PPAD problems is always yes, as a solution is known to exist, even though it might be hard to find that solution. However, PPAD and NP are closely related. While the question whether a Nash equilibrium exists for a given game cannot be in NP because the answer is always yes, the question whether a second equilibrium exists is NP complete. It could still be the case that PPAD is the same class as FP, and still have that P ≠ NP, though it seems unlikely. Examples of PPAD-complete problems include finding Nash equilibria, computing fixed points in Brouwer functions, finding Arrow-Debreu equilibria in markets and more.

PPAD is a subset of the class TFNP, the class of function problems in FNP that are guaranteed to be total. The TFNP formal definition is given as follows:

Subclasses of TFNP are defined based on the type of mathematical proof used to prove that a solution always exists. 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, known as End-Of-The-Line:

...
Wikipedia