step.” It turns out that, for all known total search problems
in the fringes of P, these nonconstructive steps are one of
very few simple arguments:
• “If a graph has a node of odd degree, then it must have
another.” This is the parity argument, giving rise to the
class PPa.
• “If a directed graph has an unbalanced node (a vertex with
different in-degree and out-degree), then it must have
another.” This is the parity argument for directed graphs,
giving rise to the class PPaD considered in this article.
Figure 5 describes the corresponding search problems.
• “Every directed acyclic graph must have a sink.” The
corresponding class is called PLS for polynomial local
search.
• “If a function maps n elements to n – 1 elements, then
there is a collision.” This is the pigeonhole principle, and
the corresponding class is PPP.
We proceed with defining more precisely the second class in
the list above.
2. 1. the class PPaD
There are two equivalent ways to define nP: First, it is the
class of all search problems whose answers are verifiable
in polynomial time. For example, the search problem sat
(“Given a Boolean formula in CNF, find a satisfying truth
assignment, or report that none exists”) is in nP because it
is easy to check whether a truth assignment satisfies a CNF.
Since we know that sat is nP-complete, we can also define nP
as the class of all problems that can be reduced into instances
of sat. By “reduce” we refer to the usual form of polynomial-time reduction from search problem A to search problem B:
An efficient algorithm for transforming any instance of A to
an equivalent instance of B, together with an efficient algorithm for translating any solution of the instance of B back to
a solution of the original instance of A.
We define the class PPaD using the second strategy. In
particular, PPaD is the class of all search problems that can be
reduced to the problem end of the line, defined in Figure 5.
Note that, since end of the line is a total problem, so are
all problems in PPaD. Proceeding now in analogy with nP,
we call a problem PPaD-complete if end of the line (and
therefore all problems in PPaD) can be reduced to it.
2. 2. Why should we believe that PPaD contains
hard problems?
In the absence of a proof that P ≠ nP we cannot hope to be
sure that PPaD contains hard problems. The reason is that
PPaD lies “between P and nP” in the sense that, if P = nP, then
PPaD itself, as a subset of nP, will be equal to P. But even if
P ≠ nP, it may still be the case that PPaD-complete problems
are easy to solve. We believe that PPaD-complete problems
are hard for the same reasons of computational and mathematical experience that convince us that nP-complete
problems are hard (but as we mentioned, our confidence is
necessarily a little weaker): PPaD contains many problems
for which researchers have tried for decades to develop efficient algorithms; in the next section we introduce one such
92 CommunICatIons of the aCm | febrUary 2009 | vol. 52 | no. 2
figure 5: enD of the LIne: an apparently hard total search problem.
let us say that a vertex in a directed graph is “unbalanced” if the number of
its incoming edges differs from the number of its outgoing edges. observe
that, given a directed graph and an unbalanced vertex, there must exist at
least one other unbalanced vertex. This is the parity argument on directed
graphs. (PPAD stands for “polynomial parity argument for directed graphs.”)
Hence, the following is a total search problem:
Input: a directed graph G and a specified unbalanced vertex of G.
Output: Some other unbalanced vertex.
Note that, before we even begin to search G, the parity argument assures
us that we are searching for something that really exists. Now, if G were
presented in the form of a list of its vertices and edges, the problem could
of course be solved efficiently. Suppose however that we are given a graph
that is too large to be written out in full, but must be represented by a
program that tells us whether an edge exists or not.
To be specific, suppose G has 2n vertices, one for every bit string of length n
(the parameter denoting the size of the problem). for simplicity, we will suppose that every vertex has at most one incoming edge and at most one outgoing
edge. The edges of G will be represented by two Boolean circuits, of size polynomial in n, each with n input bits. Denote the circuits P and S (for predecessor
and successor). our convention is that there is a directed edge from vertex v to
vertex w, if, given input v, S outputs w and, vice versa, given input w, P outputs
v. Suppose now that some specific, identified vertex (say, the string 00 . . . 0) has
an outgoing edge but no incoming edge, and is thus unbalanced. Since there
is at most one incoming and one outgoing edge per node, the directed graph
must be a set of paths and cycles; hence, following the path that starts at the
all-zeroes node would eventually lead us to a solution. The catch is, of course,
that this may take exponential time. Is there an efficient algorithm for finding
another unbalanced node without actually following the path?
problem called Brouwer. However, end of the line itself
is a pretty convincingly hard problem: How can one hope to
devise an algorithm that telescopes exponentially long paths
in every implicitly given graph?
3. fRom nash to PPaD
Our main result is the following:
Theorem 3. 1. Nash is PPaD-complete.
In the remainder of this article we outline the main ideas
of the proof; for full details see Daskalakis et al.
8 We need to
prove two things: First, that Nash is in PPaD, that is, it can
be reduced to end of the line. Second (see Section 4), that
it is complete—the reverse reduction. As it turns out, both
directions are established through a computational problem inspired by a fundamental result in topology, called
Brouwer’s fixed point theorem, described next.
3. 1. Brouwer’s fixed point theorem
Imagine a continuous function mapping a circle (together
with its interior) to itself—for example, a rotation around the
center. Notice that the center is fixed, it has not moved under
this function. You could flip the circle—but then all points
on a diagonal would stay put. Or you could do something
more elaborate: Shrink the circle, translate it (so it still lies
within the original larger circle), and then rotate it. A little
thought reveals that there is still at least one fixed point. Or
stretch and compress the circle like a sheet of rubber any way
you want and stick it on the original circle; still points will
be fixed, unless of course you tear the circle—the function