Through the eyes of a topologist, manifolds have no local properties: every point has a small neighborhood that looks like euclidean space. Accordingly, as initiated by PoincarA(c), the classification of manifolds is one of the central problems in topology. The ``homeomorphism problem'' is somewhat easier: given a pair of manifolds, we are asked to decide if they are homeomorphic.
These problems are solved for zero-, one-, and two-manifolds. Even better, the solutions are ``effective'': there are complete topological invariants that we can compute in polynomial time. On the other hand, in dimensions four and higher the homeomorphism problem is logically undecidable.
This leaves the provocative third dimension. Work of Haken, Rubenstein, Casson, Manning, Perelman, and others shows that these problems are decidable. Sometimes we can do better: for example, if one of the manifolds is the three-sphere then I showed that the homeomorphism problem lies in the complexity class NP. In joint work with Marc Lackenby, we show that recognizing spherical space forms also lies in NP. If time permits, we'll discuss the standing of the other seven Thurston geometries.