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.16 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 Lemma20 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. (Papadimitriou20
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