Remote Access Transactions of the American Mathematical Society
Green Open Access

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
DOI: https://doi.org/10.1090/S0002-9947-05-03919-X
Published electronically: December 20, 2005
MathSciNet review: 2219001
Full-text PDF

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?)

  • 1. M. Dehn, ``Uber die Topologie des dreidimensional Raumes'', Math. Annalen, 69 (1910) 137-168. MR 1511580
  • 2. M.R. Garey and D.S. Johnson, ``Computers and intractability. A guide to the theory of NP-completeness'', W. H. Freeman and Co., San Francisco, 1979. MR 0519066 (80g:68056)
  • 3. W. Haken, ``Theorie der Normalflächen: Ein Isotopiekriterium für den Kreisknoten'', Acta Math., 105 (1961) 245-375. MR 0141106 (25:4519a)
  • 4. J. Hass, ``Algorithms for recognizing knots and 3-manifolds'', Chaos, Solitons and Fractals, 9 (1998) 569-581. MR 1628743 (2000a:57038)
  • 5. J. Hass, J. C. Lagarias and N. Pippenger, ``The computational complexity of Knot and Link problems'', Journal of the ACM, 46 (1999) 185-211. MR 1693203 (2000g:68056)
  • 6. J. Hass and J. C. Lagarias, ``The number of Reidemeister moves needed for unknotting'', J. Amer. Math. Soc. 14 (2001), no. 2, 399-428 MR 1815217 (2001m:57012)
  • 7. G. Hemion, The Classification of Knots and $ 3$-Dimensional Spaces, Oxford University Press, 1992. MR 1211184 (94g:57015)
  • 8. J. Hempel, 3-Manifolds, Princeton University Press, Princeton, NJ, 1976. MR 0415619 (54:3702)
  • 9. W. Jaco, Lectures on three-manifold topology, CBMS Regional Conference Series in Mathematics, 43 AMS, Providence, RI, 1980. MR 0565450 (81k:57009)
  • 10. W. Jaco and U. Oertel, ``An Algorithm to Decide If a $ 3$-Manifold Is a Haken Manifold'', Topology, 23 (1984) 195-209. MR 0744850 (85j:57014)
  • 11. W. Jaco and J. L. Tollefson, ``Algorithms for the Complete Decomposition of a Closed $ 3$-Manifold'', Illinois J. Math., 39 (1995) 358-406. MR 1339832 (97a:57014)
  • 12. W. Jaco and J. H. Rubinstein, ``PL Equivariant Surgery and Invariant Decompositions of $ 3$-Manifolds'', Advances in Math., 73 (1989) 149-191. MR 0987273 (90g:57016)
  • 13. F. Jaeger, D. L. Vertigan and D. J. A. Welsh, ``On the Computational Complexity of the Jones and Tutte Polynomials'', Math. Proc. Cambridge Phil. Soc., 108 (1990) 35-53. MR 1049758 (91h:05038)
  • 14. H. Kneser, ``Geschlossene Flächen in dreidimensionalen Mannigfaltigkeiten'', Jahresbericht Math. Verein., 28 (1929) 248-260.
  • 15. E. E. Moise, ``Affine Structures in $ 3$-Manifolds, V: The Triangulation Theorem and Hauptvermutung'', Ann. Math., 56 (1952) 96-114. MR 0048805 (14:72d)
  • 16. C.H. Papadimitriou, Computational complexity. Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285 (95f:68082)
  • 17. M. O. Rabin, ``Recursive Unsolvability of Group-Theoretic Problems'', Ann. Math., 67 (1958) 172-194. MR 0110743 (22:1611)
  • 18. J.H. Rubinstein, ``An algorithm to recognize the $ 3$-sphere'', Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Zurich, 1994), Birkhauser, Basel, 601-611. MR 1403961 (97e:57011)
  • 19. Schaefer, T.J. ``The complexity of satisfiability problems'', Proc 10th Ann. ACM. Symp. on Theory of Computing, ACM, NY (1978) 216-226. MR 0521057 (80d:68058)
  • 20. A. Schrijver, Theory of Linear and Integer Programming, John Wiley and Sons, 1986. MR 0874114 (88m:90090)
  • 21. H. Schubert, ``Bestimmung der Primfaktorzerlegung von Verkettungen'', Math. Zeitschr., 76 (1961) 116-148. MR 0141107 (25:4519b)
  • 22. A. Sebö, ``Hilbert Bases, Caratheodory's Theorem and Combinatorial Optimization'', in: R. Kannan and W. R. Pulleyblank (Eds.), Integer Programming and Combinatorial Optimization, University of Waterloo Press, 1990, 431-455.
  • 23. H. Seifert, ``Über das Geschlecht von Knoten'', Math. Annalen, 110 (1935) 571-592. MR 1512955
  • 24. A. Thompson, Thin position and the recognition problem for $ S^3$. Math. Res. Lett. 1 (1994), 613-630. MR 1295555 (95k:57015)
  • 25. D. J. A. Welsh, Complexity: Knots, Colourings and Counting, Cambridge University Press, 1993. MR 1245272 (94m:57027)
  • 26. D. J. A. Welsh, ``The Complexity of Knots'', Ann. Discr. Math., 55 (1993) 159-173. MR 1217989 (94c:57021)
  • 27. D. J. A. Welsh, ``Knots and Braids'', Contemp. Math., 147 (1993) 109-123. MR 1224698 (94g:57014)

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: https://doi.org/10.1090/S0002-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

American Mathematical Society