The computational complexity of knot genus and spanning area

Agol, Ian; Hass, Joel; Thurston, William

doi:10.1090/S0002-9947-05-03919-X

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