The computational complexity of basic decision problems in 3-dimensional topology

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)1-26
Number of pages26
JournalGeometriae Dedicata
Volume131
Issue number1
DOIs
StatePublished - Feb 1 2008

Keywords

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

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint Dive into the research topics of 'The computational complexity of basic decision problems in 3-dimensional topology'. Together they form a unique fingerprint.

Cite this