Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

   

 

The computational complexity of knot genus and spanning area


Authors: Ian Agol, Joel Hass and William Thurston
Journal: Trans. Amer. Math. Soc. 358 (2006), 3821-3850
MSC (2000): Primary 11Y16, 57M50; Secondary 57M25
Published electronically: December 20, 2005
MathSciNet review: 2219001
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We show that the problem of deciding whether a polygonal knot in a closed three-dimensional manifold bounds a surface of genus at most $ g$ is NP-complete. We also show that the problem of deciding whether a curve in a PL manifold bounds a surface of area less than a given constant $ C$ is NP-hard.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 11Y16, 57M50, 57M25

Retrieve articles in all journals with MSC (2000): 11Y16, 57M50, 57M25


Additional Information

Ian Agol
Affiliation: Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, Chicago, Illinois 60607
Email: agol@math.uic.edu

Joel Hass
Affiliation: School of Mathematics, Institute for Advanced Study and Department of Mathematics, University of California, Davis, California 95616
Email: hass@math.ucdavis.edu

William Thurston
Affiliation: Department of Mathematics, University of California, Davis, California 95616
Address at time of publication: Department of Mathematics, Cornell University, Ithaca, New York 14853
Email: wpt@math.ucdavis.edu, wpt@math.cornell.edu

DOI: http://dx.doi.org/10.1090/S0002-9947-05-03919-X
PII: S 0002-9947(05)03919-X
Keywords: Computational topology, complexity, knot, 3-manifold, NP-complete, normal surface, genus
Received by editor(s): July 17, 2002
Received by editor(s) in revised form: May 28, 2004
Published electronically: December 20, 2005
Additional Notes: The first author was partially supported by ARC grant 420998. This work was carried out while the second author was visiting the Institute for Advanced Study, and was partially supported by NSF grant DMS-0072348, and by a grant to the Institute for Advanced Study by AMIAS. The third author was partially supported by NSF grant DMS-9704286.
Article copyright: © Copyright 2005 Ian Agol, Joel Hass, and William Thurston