The computational complexity of basic decision problems in 3-dimensional topology |
| |
Authors: | S. V. Ivanov |
| |
Affiliation: | (1) Department of Mathematics, University of Illinois, Urbana Champaign, IL 61801, USA |
| |
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. |
| |
Keywords: | 3-manifolds Triangulations Normal surfaces Decision problems Computational complexity |
本文献已被 SpringerLink 等数据库收录! |
|