3-manifold knot genus is NP-complete

DOI10.1145/509907.510016MaRDI QIDQ3579217zbMATH OpenOpenAlexWikidataFDO

Authors Ian Agol, Joel R. Hass, William P. Thurston

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)

Cited in

(8)

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

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

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