This survey focuses on the computational complexity of some of the
fundamental decision problems in 3-manifold theory. The article discusses the
wide variety of tools that are used to tackle these problems, including normal
and almost surfaces, hierarchies, homomorphisms to finite groups, and
hyperbolic structures.