  The Complex of Curves on a Surface is a simplicial complex whose vertices are
homotopy classes of simple closed curves, and whose simplices are sets of
homotopy classes which can be realized disjointly. It is not hard to see that
the complex is finite-dimensional, but locally infinite. It was introduced by
Harvey as an analogy, in the context of Teichmuller space, for Tits buildings
for symmetric spaces, and has been studied by Harer and Ivanov as a tool for
understanding mapping class groups of surfaces.
  In this paper we prove that, endowed with a natural metric, the complex is
hyperbolic in the sense of Gromov. In a certain sense this hyperbolicity is an
explanation of why the Teichmuller space has some negative-curvature properties
in spite of not being itself hyperbolic: Hyperbolicity in the Teichmuller space
fails most obviously in the regions corresponding to surfaces where some curve
is extremely short. The complex of curves exactly encodes the intersection
patterns of this family of regions (it is the "nerve" of the family), and we
show that its hyperbolicity means that the Teichmuller space is "relatively
hyperbolic" with respect to this family. A similar relative hyperbolicity
result is proved for the mapping class group of a surface.
  We also show that the action of pseudo-Anosov mapping classes on the complex
is hyperbolic, with a uniform bound on translation distance.
