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 2ⁿ 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. ⁸ 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