3-manifold knot genus is NP-complete
From MaRDI portal
Publication:3579217
DOI10.1145/509907.510016zbMath1192.68305OpenAlexW2169534903MaRDI 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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (7)
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 ⋮ On the hardness of finding normal surfaces
This page was built for publication: 3-manifold knot genus is NP-complete
