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

DOI10.1007/S10711-007-9210-4MaRDI QIDQ2481645zbMATH OpenOpenAlexFDO

Authors S. V. Ivanov

Publication date 14 April 2008

Published in Geometriae Dedicata (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10711-007-9210-4

zbMATH Keywords

3-manifoldsComputational complexityNormal surfacesTriangulationsDecision problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Fundamental group, presentations, free differential calculus (57M05) General geometric structures on low-dimensional manifolds (57M50)

Recommendations

• Sphere recognition lies in NP
• Some conditionally hard problems on links and 3-manifolds
• The computational complexity of knot genus and spanning area
• scientific article; zbMATH DE number 7647903
• Decision problems for 3-manifolds and their fundamental groups

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1134565 (Why is no real title available?)
• scientific article; zbMATH DE number 849995 (Why is no real title available?)
• scientific article; zbMATH DE number 256200 (Why is no real title available?)
• 0-efficient triangulations of 3-manifolds
• Affine structures in 3-manifolds. V: The triangulation theorem and Hauptvermutung
• Algorithms for the complete decomposition of a closed 3-manifold
• Almost normal surfaces in 3-manifolds
• An algorithm for the recognition of 3-spheres (according to Thompson)
• An algorithm to decide if a 3-manifold is a Haken manifold
• An alternative proof that 3-manifolds can be triangulated
• Foliations and the topology of 3-manifolds. III
• Knots are Determined by Their Complements
• PL equivariant surgery and invariant decompositions of 3-manifolds
• Recognizing the 3-sphere
• Sphere recognition lies in NP
• The computational complexity of knot and link problems
• The computational complexity of knot genus and spanning area
• Theorie der Normalflächen. Ein Isotopiekriterium für den Kreisknoten
• Thin position and the recognition problem for \(S^ 3\)

Cited in

(22)

• scientific article; zbMATH DE number 7647903 (Why is no real title available?)
• Sphere recognition lies in NP
• Computing a link diagram from its exterior
• Hardness of embedding simplicial complexes in R^d
• Identifying lens spaces in polynomial time
• Deciding contractibility of a non-simple curve on the boundary of a 3-manifold
• Computational topology and normal surfaces: theoretical and experimental complexity bounds
• scientific article; zbMATH DE number 7236450 (Why is no real title available?)
• On the complexity of torus knot recognition
• Algorithms for contractibility of compressed curves on 3-manifold boundaries
• A solution of the decision problem for the Lewis systems S2 and S4, with an application to topology
• About the Complexity of Timetables and 3-Dimensional Discrete Tomography: A Short Proof of NP-Hardness
• Decision problems for 3-manifolds and their fundamental groups
• On Conjectures of Andrews and Curtis
• Finding non-orientable surfaces in 3-manifolds
• The intersection of subgroups in free groups and linear programming
• On the hardness of finding normal surfaces
• Finding non-orientable surfaces in 3-manifolds
• The complexity of detecting taut angle structures on triangulations
• Recognition of Seifert fibered spaces with boundary is in NP
• The efficient certification of knottedness and Thurston norm
• Some conditionally hard problems on links and 3-manifolds

This page was built for publication: The computational complexity of basic decision problems in 3-dimensional topology

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2481645)