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: :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. 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: :G is a (possibly exponentially large) directed graph with every
vertex having at most one predecessor and at most one successor. G is specified by giving a polynomial-time computable function f(
v) (polynomial in the size of
v) that returns the predecessor and successor (if they exist) of the vertex
v. Given a vertex
s in G with no predecessor, find a vertex
t≠s with no predecessor or no successor. (The input to the problem is the source vertex
s and the function f(
v)). 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.) == Proving membership in PPAD ==