The computational complexity of knot genus and spanning area
HTML articles powered by AMS MathViewer
- by Ian Agol, Joel Hass and William Thurston PDF
- Trans. Amer. Math. Soc. 358 (2006), 3821-3850
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
- M. Dehn, Über die Topologie des dreidimensionalen Raumes, Math. Ann. 69 (1910), no. 1, 137–168 (German). MR 1511580, DOI 10.1007/BF01455155
- Michael R. Garey and David S. Johnson, Computers and intractability, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness. MR 519066
- Wolfgang Haken, Theorie der Normalflächen, Acta Math. 105 (1961), 245–375 (German). MR 141106, DOI 10.1007/BF02559591
- Joel Hass, Algorithms for recognizing knots and $3$-manifolds, Chaos Solitons Fractals 9 (1998), no. 4-5, 569–581. Knot theory and its applications. MR 1628743, DOI 10.1016/S0960-0779(97)00109-4
- Joel Hass, Jeffrey C. Lagarias, and Nicholas Pippenger, The computational complexity of knot and link problems, J. ACM 46 (1999), no. 2, 185–211. MR 1693203, DOI 10.1145/301970.301971
- Joel Hass and Jeffrey C. Lagarias, The number of Reidemeister moves needed for unknotting, J. Amer. Math. Soc. 14 (2001), no. 2, 399–428. MR 1815217, DOI 10.1090/S0894-0347-01-00358-7
- Geoffrey Hemion, The classification of knots and $3$-dimensional spaces, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1992. MR 1211184
- John Hempel, $3$-Manifolds, Princeton University Press, Princeton, N. J.; University of Tokyo Press, Tokyo, 1976. Ann. of Math. Studies, No. 86. MR 0415619
- William Jaco, Lectures on three-manifold topology, CBMS Regional Conference Series in Mathematics, vol. 43, American Mathematical Society, Providence, R.I., 1980. MR 565450
- William Jaco and Ulrich Oertel, An algorithm to decide if a $3$-manifold is a Haken manifold, Topology 23 (1984), no. 2, 195–209. MR 744850, DOI 10.1016/0040-9383(84)90039-9
- William Jaco and Jeffrey L. Tollefson, Algorithms for the complete decomposition of a closed $3$-manifold, Illinois J. Math. 39 (1995), no. 3, 358–406. MR 1339832
- William Jaco and J. Hyam Rubinstein, PL equivariant surgery and invariant decompositions of $3$-manifolds, Adv. in Math. 73 (1989), no. 2, 149–191. MR 987273, DOI 10.1016/0001-8708(89)90067-4
- F. Jaeger, D. L. Vertigan, and D. J. A. Welsh, On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Cambridge Philos. Soc. 108 (1990), no. 1, 35–53. MR 1049758, DOI 10.1017/S0305004100068936
- H. Kneser, “Geschlossene Flächen in dreidimensionalen Mannigfaltigkeiten”, Jahresbericht Math. Verein., 28 (1929) 248–260.
- Edwin E. Moise, Affine structures in $3$-manifolds. V. The triangulation theorem and Hauptvermutung, Ann. of Math. (2) 56 (1952), 96–114. MR 48805, DOI 10.2307/1969769
- Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285
- Michael O. Rabin, Recursive unsolvability of group theoretic problems, Ann. of Math. (2) 67 (1958), 172–194. MR 110743, DOI 10.2307/1969933
- Joachim H. Rubinstein, An algorithm to recognize the $3$-sphere, Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Zürich, 1994) Birkhäuser, Basel, 1995, pp. 601–611. MR 1403961
- Thomas J. Schaefer, The complexity of satisfiability problems, Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, Calif., 1978) ACM, New York, 1978, pp. 216–226. MR 521057
- Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. MR 874114
- Wolfgang Haken, Theorie der Normalflächen, Acta Math. 105 (1961), 245–375 (German). MR 141106, DOI 10.1007/BF02559591
- 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.
- H. Seifert, Über das Geschlecht von Knoten, Math. Ann. 110 (1935), no. 1, 571–592 (German). MR 1512955, DOI 10.1007/BF01448044
- Abigail Thompson, Thin position and the recognition problem for $S^3$, Math. Res. Lett. 1 (1994), no. 5, 613–630. MR 1295555, DOI 10.4310/MRL.1994.v1.n5.a9
- D. J. A. Welsh, Complexity: knots, colourings and counting, London Mathematical Society Lecture Note Series, vol. 186, Cambridge University Press, Cambridge, 1993. MR 1245272, DOI 10.1017/CBO9780511752506
- Dominic J. A. Welsh, The complexity of knots, Quo vadis, graph theory?, Ann. Discrete Math., vol. 55, North-Holland, Amsterdam, 1993, pp. 159–171. MR 1217989, DOI 10.1016/S0167-5060(08)70385-6
- D. J. A. Welsh, Knots and braids: some algorithmic questions, Graph structure theory (Seattle, WA, 1991) Contemp. Math., vol. 147, Amer. Math. Soc., Providence, RI, 1993, pp. 109–123. MR 1224698, DOI 10.1090/conm/147/01166
Additional Information
- Ian Agol
- Affiliation: Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, Chicago, Illinois 60607
- MR Author ID: 671767
- ORCID: 0000-0002-4254-8483
- 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
- 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.
- © Copyright 2005 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
- MathSciNet review: 2219001