Abstract
We study the computational complexity of basic decision problems of 3-dimensional topology, such as to determine whether a triangulated 3-manifold is irreducible, prime, ∂-irreducible, or homeomorphic to a given 3-manifold M. For example, we prove that the problem to recognize whether a triangulated 3-manifold is homeomorphic to a 3-sphere, or to a 2-sphere bundle over a circle, or to a real projective 3-space, or to a handlebody of genus g, is decidable in nondeterministic polynomial time (NP) of size of the triangulation. We also show that the problem to determine whether a triangulated orientable 3-manifold is irreducible (or prime) is in PSPACE and whether it is ∂-irreducible is in coNP. The proofs improve and extend arguments of prior author's article on the recognition problem for the 3-sphere.
Original language | English (US) |
---|---|
Pages (from-to) | 1-26 |
Number of pages | 26 |
Journal | Geometriae Dedicata |
Volume | 131 |
Issue number | 1 |
DOIs | |
State | Published - Feb 2008 |
Keywords
- 3-manifolds
- Computational complexity
- Decision problems
- Normal surfaces
- Triangulations
ASJC Scopus subject areas
- Geometry and Topology