On the hardness of finding normal surfaces

DOI10.1007/s41468-021-00076-0OpenAlexW3198811666MaRDI QIDQ2063199

Benjamin A. Burton, Alexander K. Khe

Publication date: 10 January 2022

Published in: Journal of Applied and Computational Topology (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1912.09051

zbMATH Keywords

computational complexitynormal surfaces3-manifoldscomputational topology

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) General topology of 3-manifolds (57K30)

Uses Software

• Regina

Cites Work

• Unnamed Item
• Unnamed Item
• A new approach to crushing 3-manifold triangulations
• Theorie der Normalflächen. Ein Isotopiekriterium für den Kreisknoten
• An algorithm to decide if a 3-manifold is a Haken manifold
• One-sided Heegaard splittings of 3-manifolds
• Integer homology 3-spheres admit irreducible representations in \(\mathrm{SL}(2,{\mathbb C})\)
• 0-efficient triangulations of 3-manifolds
• Algorithms for the complete decomposition of a closed \(3\)-manifold
• The computational complexity of basic decision problems in 3-dimensional topology
• Computational topology with Regina: Algorithms, heuristics and implementations
• The computational complexity of knot and link problems
• 3-manifold knot genus is NP-complete
• The complexity of satisfiability problems