The computational complexity of knot genus and spanning area. (English) Zbl 1098.57003

Agol, Ian; Hass, Joel; Thurston, William

Trans. Am. Math. Soc. 358, No. 9, 3821-3850 (2006).

The paper studies the computational complexity of two problems: the determination of an upper bound on the genus of a knot in a (triangulated and orientable and with orientable embedded surfaces) 3-manifold and the problem of deciding whether a curve in a metrized PL 3-manifold bounds a surface of area less than a given constant.
The first problem can be considered as an extension of the problem of determining whether a given knot is non-trivial, a classical problem posed by M. Dehn [Math. Ann. 69, 137–168 (1910; JFM 41.0543.01)] that lies in the complexity class NP, see J. Hass, J. C. Lagarias and N. Pippenger [J. ACM 46, 185-211 (1999; Zbl 1065.68667)]. The genus \(g\) of a knot \(K\) is the minimum genus of a surface in the class \(S(K)\) of all orientable spanning surfaces for \(K\). Thus, a knot is trivial when its genus is zero.
The authors prove (Theorem 3) that the problem 3-Manifold Knot Genus is NP-complete. This theorem is a corollary of two previous results: Theorem 1 states that the problem is NP-hard; that theorem is proved in Section 3, showing that an instance of the problem One-In-Three SAT can be reduced in polynomial time to an instance of the problem 3-Manifold Knot Genus.
The second result, Theorem 2, shows that 3-Manifold Knot Genus is NP and is proved in Section 5 giving a certificate which demonstrates in polynomial time that the knot \(K\) bounds a surface of genus at most \(g\).
The authors point out that if one restricts to knots in \(\mathbb R^3\) or \(S^3\) it is an open problem whether the corresponding problem remains NP-hard.
In Section 7, using similar methods, the authors show that computing an upper bound on the area of a smallest area spanning surface in a metrized PL 3-dimensional manifold is NP-hard.

Reviewer: Juan Tena Ayuso (Valladolid)

MSC:

57M25	Knots and links in the \(3\)-sphere (MSC2010)
11Y16	Number-theoretic algorithms; complexity
57M50	General geometric structures on low-dimensional manifolds
68W30	Symbolic computation and algebraic computation
68Q25	Analysis of algorithms and problem complexity

Keywords:

computational topology; complexity; NP-complete; NP-hard; knot; genus; 3-manifold; normal surface.

Citations:

Zbl 1065.68667; JFM 41.0543.01

References:

[1]	M. Dehn, Über die Topologie des dreidimensionalen Raumes, Math. Ann. 69 (1910), no. 1, 137 – 168 (German). · JFM 41.0543.01 · doi:10.1007/BF01455155
[2]	Michael R. Garey and David S. Johnson, Computers and intractability, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness; A Series of Books in the Mathematical Sciences. · Zbl 0411.68039
[3]	Wolfgang Haken, Theorie der Normalflächen, Acta Math. 105 (1961), 245 – 375 (German). , https://doi.org/10.1007/BF02559591 Horst Schubert, Bestimmung der Primfaktorzerlegung von Verkettungen, Math. Z. 76 (1961), 116 – 148 (German). , https://doi.org/10.1007/BF01210965 Wolfgang Haken, Ein Verfahren zur Aufspaltung einer 3-Mannigfaltigkeit in irreduzible 3-Mannigfaltigkeiten, Math. Z. 76 (1961), 427 – 467 (German). · Zbl 0111.18803 · doi:10.1007/BF01210988
[4]	Joel Hass, Algorithms for recognizing knots and 3-manifolds, Chaos Solitons Fractals 9 (1998), no. 4-5, 569 – 581. Knot theory and its applications. · Zbl 0935.57014 · doi:10.1016/S0960-0779(97)00109-4
[5]	Joel Hass, Jeffrey C. Lagarias, and Nicholas Pippenger, The computational complexity of knot and link problems, J. ACM 46 (1999), no. 2, 185 – 211. · Zbl 1065.68667 · doi:10.1145/301970.301971
[6]	Joel Hass and Jeffrey C. Lagarias, The number of Reidemeister moves needed for unknotting, J. Amer. Math. Soc. 14 (2001), no. 2, 399 – 428. · Zbl 0964.57005
[7]	Geoffrey Hemion, The classification of knots and 3-dimensional spaces, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1992. · Zbl 0771.57001
[8]	John Hempel, 3-Manifolds, Princeton University Press, Princeton, N. J.; University of Tokyo Press, Tokyo, 1976. Ann. of Math. Studies, No. 86. · Zbl 0345.57001
[9]	William Jaco, Lectures on three-manifold topology, CBMS Regional Conference Series in Mathematics, vol. 43, American Mathematical Society, Providence, R.I., 1980. · Zbl 0433.57001
[10]	William Jaco and Ulrich Oertel, An algorithm to decide if a 3-manifold is a Haken manifold, Topology 23 (1984), no. 2, 195 – 209. · Zbl 0545.57003 · doi:10.1016/0040-9383(84)90039-9
[11]	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. · Zbl 0858.57018
[12]	William Jaco and J. Hyam Rubinstein, PL equivariant surgery and invariant decompositions of 3-manifolds, Adv. in Math. 73 (1989), no. 2, 149 – 191. · Zbl 0682.57005 · doi:10.1016/0001-8708(89)90067-4
[13]	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. · Zbl 0747.57006 · doi:10.1017/S0305004100068936
[14]	H. Kneser, “Geschlossene Flächen in dreidimensionalen Mannigfaltigkeiten”, Jahresbericht Math. Verein., 28 (1929) 248-260. · JFM 55.0311.03
[15]	Edwin E. Moise, Affine structures in 3-manifolds. V. The triangulation theorem and Hauptvermutung, Ann. of Math. (2) 56 (1952), 96 – 114. · Zbl 0048.17102 · doi:10.2307/1969769
[16]	Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. · Zbl 0833.68049
[17]	Michael O. Rabin, Recursive unsolvability of group theoretic problems, Ann. of Math. (2) 67 (1958), 172 – 194. · Zbl 0079.24802 · doi:10.2307/1969933
[18]	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. · Zbl 0864.57009
[19]	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. · Zbl 1282.68143
[20]	Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. · Zbl 0665.90063
[21]	Wolfgang Haken, Theorie der Normalflächen, Acta Math. 105 (1961), 245 – 375 (German). , https://doi.org/10.1007/BF02559591 Horst Schubert, Bestimmung der Primfaktorzerlegung von Verkettungen, Math. Z. 76 (1961), 116 – 148 (German). , https://doi.org/10.1007/BF01210965 Wolfgang Haken, Ein Verfahren zur Aufspaltung einer 3-Mannigfaltigkeit in irreduzible 3-Mannigfaltigkeiten, Math. Z. 76 (1961), 427 – 467 (German). · Zbl 0111.18803 · doi:10.1007/BF01210988
[22]	A. Sebö, “Hilbert Bases, Caratheodory’s Theorem and Combinatorial Optimization”, in: R. Kannan and W. R. Pulleyblank , Integer Programming and Combinatorial Optimization, University of Waterloo Press, 1990, 431-455.
[23]	H. Seifert, Über das Geschlecht von Knoten, Math. Ann. 110 (1935), no. 1, 571 – 592 (German). · Zbl 0010.13303 · doi:10.1007/BF01448044
[24]	Abigail Thompson, Thin position and the recognition problem for \?³, Math. Res. Lett. 1 (1994), no. 5, 613 – 630. · Zbl 0849.57009 · doi:10.4310/MRL.1994.v1.n5.a9
[25]	D. J. A. Welsh, Complexity: knots, colourings and counting, London Mathematical Society Lecture Note Series, vol. 186, Cambridge University Press, Cambridge, 1993. · Zbl 0799.68008
[26]	Dominic J. A. Welsh, The complexity of knots, Quo vadis, graph theory?, Ann. Discrete Math., vol. 55, North-Holland, Amsterdam, 1993, pp. 159 – 171. · Zbl 0801.68086 · doi:10.1016/S0167-5060(08)70385-6
[27]	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. · Zbl 0792.05058 · doi:10.1090/conm/147/01166