3-manifold knot genus is NP-complete

DOI10.1145/509907.510016zbMath1192.68305OpenAlexW2169534903WikidataQ130947768 ScholiaQ130947768MaRDI QIDQ3579217

Joel Hass, William P. Thurston, Ian Agol

Publication date: 5 August 2010

Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/509907.510016

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

Quadrilateral–Octagon Coordinates for Almost Normal Surfaces ⋮ Some conditionally hard problems on links and 3-manifolds ⋮ Maximal admissible faces and asymptotic bounds for the normal surface solution space ⋮ Computing Heegaard Genus is NP-Hard ⋮ Cuts for 3-D magnetic scalar potentials: visualizing unintuitive surfaces arising from trivial knots ⋮ A polynomial upper bound on Reidemeister moves ⋮ The computational complexity of the solid torus core recognition problem ⋮ On the hardness of finding normal surfaces

This page was built for publication: 3-manifold knot genus is NP-complete