## 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 1 2008 |

## Keywords

- 3-manifolds
- Computational complexity
- Decision problems
- Normal surfaces
- Triangulations

## ASJC Scopus subject areas

- Geometry and Topology