must be continuous. There is a topological reason why you cannot map continuously the circle on itself without leaving a point unmoved, and that’s Brouwer’s theorem.¹⁶ It states that any continuous map from a compact (that is, closed and bounded) and convex (that is, without holes) subset of the Euclidean space into itself always has a fixed point.

directions, and we must be close to an approximate fixed point. We elaborate on this in the next few paragraphs, focusing on the two-dimensional case.

Brouwer’s theorem immediately suggests an interesting computational total search problem, called Brouwer: Given a continuous function from some compact and convex set to itself, find a fixed point. But of course, for a meaningful definition of Brouwer we need to first address two questions: How do we specify a continuous map from some compact and convex set to itself? And how do we deal with irrational fixed points?

First, we fix the compact and convex set to be the unit
cube [0, 1]^m—in the case of more general domains, for
example, the circular domain discussed above, we can
translate it to this setting by shrinking the circle, embed-
ding it into the unit square, and extending the function to
the whole square so that no new fixed points are introduced.
We then assume that the function F is given by an efficient
algorithm Π which, for each point x of the cube written in
F
binary, computes F(x). We assume that F obeys a Lipschitz
condition:

Triangulation: First, we subdivide the unit square into small squares of size determined by e and K, and then divide each little square into two right triangles (see Figure 7, ignoring for now the colors, shading, and arrows). (In the m-dimensional case, we subdivide the m-dimensional cube into m-dimensional cubelets, and we subdivide each cubelet into the m-dimensional analog of a triangle, called an m-simplex.) Coloring: We color each vertex x of the triangles by one of three colors depending on the direction in which F maps x. In two dimensions, this can be taken to be the angle between vector F(x) – x and the horizontal. Specifically, we color it red if the direction lies between 0 and −135°, blue if it ranges between 90 and 225°, and yellow otherwise, as shown in Figure 6. (If the direction is 0°, we allow either yellow or red; similarly for the other two borderline cases.) Using the above coloring convention the vertices get colored in such a way that the following property is satisfied:

(P1): None of the vertices on the lower side of the square uses red, no vertex on the left side uses blue, and no vertex on the other two sides uses yellow. Figure 7 shows a coloring of the vertices that could result from the function F; ignore the arrows and the shading of triangles.

(4) Sperner’s Lemma: It now follows from an elegant result in Combinatorics called Sperner’s Lemma²⁰ that, in any coloring satisfying Property (P1), there will be at least one small triangle whose vertices have all three colors (verify this in Figure 7; the trichromatic triangles are shaded). Because we have chosen the triangles to be small, any vertex of a trichromatic triangle will be an approximate fixed point. Intuitively, since F satisfies the Lipschitz condition given in (4), it cannot fluctuate too fast; hence, the only way that there can be three points close to each other in distance, which are mapped in three different directions, is if they are all approximately fixed.

where d(·,·) is the Euclidean distance and K is the Lipschitz constant of F. This benign well-behavedness condition ensures that approximate fixed points can be localized by examining the value F(x) when x ranges over a discretized grid over the domain. Hence, we can deal with irrational solutions in a similar maneuver as with Nash, by only seeking approximate fixed points. In fact, we have the following strong guarantee: for any e, there is an e-approximate fixed point—that is, a point x such that d(F(x), x) ≤ e—whose coordinates are integer multiples of 2^−d, where d depends on K, e, and the dimension m; in the absence of a Lipschitz constant K, there would be no such guarantee and the problem of computing fixed points would become intractable. Formally, the problem Brouwer is defined as follows.

Brouwer

Input: An efficient algorithm Π for the evaluation of a F

The Connection with PPAD: ...is the proof of Sperner’s Lemma. Think of all the triangles containing at least one red and yellow vertex as the nodes of a directed graph G. There is a directed edge from a triangle T to another triangle T ′ if T and T ′ share a red–yellow edge which goes from red to yellow clockwise in T (see Figure 7). The graph G thus created consists of paths and cycles, since for every T there is at most one T ′ and vice versa (verify this in Figure 7). Now, we may

function F: [0, 1]^m → [0, 1]^m; a constant K such that F satisfies (4); and the desired accuracy e.

Output: A point x such that d(F(x), x) ≤ e.

It turns out that Brouwer is in PPAD. (Papadimitriou²⁰ gives a similar result for a more restrictive class of Brouwer functions.) To prove this, we will need to construct an end of the line graph associated with a Brouwer instance. We do this by constructing a mesh of tiny triangles over the domain, where each triangle will be a vertex of the graph. Edges, between pairs of adjacent triangles, will be defined with respect to a coloring of the vertices of the mesh. Vertices get colored according to the direction in which F displaces them. We argue that if a triangle’s vertices get all possible colors, then F is trying to shift these points in conflicting

Figure 6: The colors assigned to the different directions of F(x) – x. There is a transition from red to yellow at 0∞, from yellow to blue at 90∞, and from blue to red at 225∞.

FEBRUARY 2009 | VOL. 52 | NO. 2 | COMMUNICATIONS OF THE ACM
93