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

DOI10.1007/S10711-007-9210-4zbMATH Open1146.57025OpenAlexW1992600635MaRDI QIDQ2481645FDOQ2481645

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

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

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)

Cites Work

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

Cited In (22)

• Sphere recognition lies in NP
• Computing a link diagram from its exterior
• Hardness of embedding simplicial complexes in \(\mathbb 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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

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)