On the complexity of torus knot recognition

Baldwin, John; Sivek, Steven

doi:10.1090/tran/7394

On the complexity of torus knot recognition
HTML articles powered by AMS MathViewer

by John A. Baldwin and Steven Sivek PDF

Trans. Amer. Math. Soc. 371 (2019), 3831-3855 Request permission

Abstract:

We show that the problem of recognizing that a knot diagram represents a specific torus knot, or any torus knot at all, is in the complexity class NP${}\cap {}$co-NP, assuming the generalized Riemann hypothesis. We also show that satellite knot detection is in NP under the same assumption and that cabled knot detection and composite knot detection are unconditionally in NP. Our algorithms are based on recent work of Kuperberg and of Lackenby on detecting knottedness.

References

Ian Agol, Joel Hass, and William Thurston, The computational complexity of knot genus and spanning area, Trans. Amer. Math. Soc. 358 (2006), no. 9, 3821–3850. MR 2219001, DOI 10.1090/S0002-9947-05-03919-X
John Berge, The knots in $D^2\times S^1$ which have nontrivial Dehn surgeries that yield $D^2\times S^1$, Topology Appl. 38 (1991), no. 1, 1–19. MR 1093862, DOI 10.1016/0166-8641(91)90037-M
Gerhard Burde and Heiner Zieschang, Eine Kennzeichnung der Torusknoten, Math. Ann. 167 (1966), 169–176 (German). MR 210113, DOI 10.1007/BF01362170
Gerhard Burde and Heiner Zieschang, Knots, 2nd ed., De Gruyter Studies in Mathematics, vol. 5, Walter de Gruyter & Co., Berlin, 2003. MR 1959408
Richard H. Crowell and Ralph H. Fox, Introduction to knot theory, Ginn and Company, Boston, Mass., 1963. Based upon lectures given at Haverford College under the Philips Lecture Program. MR 0146828
Alexander Coward and Marc Lackenby, An upper bound on Reidemeister moves, Amer. J. Math. 136 (2014), no. 4, 1023–1066. MR 3245186, DOI 10.1353/ajm.2014.0027
Marc Culler and Peter B. Shalen, Varieties of group representations and splittings of $3$-manifolds, Ann. of Math. (2) 117 (1983), no. 1, 109–146. MR 683804, DOI 10.2307/2006973
David Gabai, Surgery on knots in solid tori, Topology 28 (1989), no. 1, 1–6. MR 991095, DOI 10.1016/0040-9383(89)90028-1
David Gabai, $1$-bridge braids in solid tori, Topology Appl. 37 (1990), no. 3, 221–235. MR 1082933, DOI 10.1016/0166-8641(90)90021-S
C. McA. Gordon and R. A. Litherland, On the signature of a link, Invent. Math. 47 (1978), no. 1, 53–69. MR 500905, DOI 10.1007/BF01609479
C. McA. Gordon and J. Luecke, Knots are determined by their complements, J. Amer. Math. Soc. 2 (1989), no. 2, 371–415. MR 965210, DOI 10.1090/S0894-0347-1989-0965210-7
Wolfgang Haken, Theorie der Normalflächen, Acta Math. 105 (1961), 245–375 (German). MR 141106, DOI 10.1007/BF02559591
Wolfgang Haken, Über das Homöomorphieproblem der 3-Mannigfaltigkeiten. I, Math. Z. 80 (1962), 89–120 (German). MR 160196, DOI 10.1007/BF01162369
Wolfgang Haken, Some results on surfaces in $3$-manifolds, Studies in Modern Topology, Math. Assoc. America, Buffalo, N.Y.; distributed by Prentice-Hall, Englewood Cliffs, N.J., 1968, pp. 39–98. MR 0224071
Geoffrey Hemion, On the classification of homeomorphisms of $2$-manifolds and the classification of $3$-manifolds, Acta Math. 142 (1979), no. 1-2, 123–155. MR 512214, DOI 10.1007/BF02395059
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
S. V. Ivanov, The computational complexity of basic decision problems in 3-dimensional topology, Geom. Dedicata 131 (2008), 1–26. MR 2369189, DOI 10.1007/s10711-007-9210-4
Klaus Johannson, Homotopy equivalences of $3$-manifolds with boundaries, Lecture Notes in Mathematics, vol. 761, Springer, Berlin, 1979. MR 551744
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
William H. Jaco and Peter B. Shalen, Seifert fibered spaces in $3$-manifolds, Mem. Amer. Math. Soc. 21 (1979), no. 220, viii+192. MR 539411, DOI 10.1090/memo/0220
William Jaco and Eric Sedgwick, Decision problems in the space of Dehn fillings, Topology 42 (2003), no. 4, 845–906. MR 1958532, DOI 10.1016/S0040-9383(02)00083-6
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
P. B. Kronheimer and T. S. Mrowka, Dehn surgery, the fundamental group and SU$(2)$, Math. Res. Lett. 11 (2004), no. 5-6, 741–754. MR 2106239, DOI 10.4310/MRL.2004.v11.n6.a3
Pascal Koiran, Hilbert’s Nullstellensatz is in the polynomial hierarchy, J. Complexity 12 (1996), no. 4, 273–286. Special issue for the Foundations of Computational Mathematics Conference (Rio de Janeiro, 1997). MR 1422712, DOI 10.1006/jcom.1996.0019
Greg Kuperberg, Knottedness is in $\mathsf {NP}$, modulo GRH, Adv. Math. 256 (2014), 493–506. MR 3177300, DOI 10.1016/j.aim.2014.01.007
Marc Lackenby, A polynomial upper bound on Reidemeister moves, Ann. of Math. (2) 182 (2015), no. 2, 491–564. MR 3418524, DOI 10.4007/annals.2015.182.2.3
Marc Lackenby, The efficient certification of knottedness and Thurston norm, arXiv:1604.00290, 2016.
W. B. Raymond Lickorish, An introduction to knot theory, Graduate Texts in Mathematics, vol. 175, Springer-Verlag, New York, 1997. MR 1472978, DOI 10.1007/978-1-4612-0691-0
R. A. Litherland, Signatures of iterated torus knots, Topology of low-dimensional manifolds (Proc. Second Sussex Conf., Chelwood Gate, 1977) Lecture Notes in Math., vol. 722, Springer, Berlin, 1979, pp. 71–84. MR 547456
J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic number fields: $L$-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409–464. MR 0447191
Sergei Matveev, Algorithmic topology and classification of 3-manifolds, Algorithms and Computation in Mathematics, vol. 9, Springer-Verlag, Berlin, 2003. MR 1997069, DOI 10.1007/978-3-662-05102-3
Aleksandar Mijatović, Triangulations of fibre-free Haken 3-manifolds, Pacific J. Math. 219 (2005), no. 1, 139–186. MR 2174223, DOI 10.2140/pjm.2005.219.139
Lee Rudolph, Nontrivial positive braids have positive signature, Topology 21 (1982), no. 3, 325–327. MR 649763, DOI 10.1016/0040-9383(82)90014-3
Saul Schleimer, Sphere recognition lies in NP, Low-dimensional and symplectic topology, Proc. Sympos. Pure Math., vol. 82, Amer. Math. Soc., Providence, RI, 2011, pp. 183–213. MR 2768660, DOI 10.1090/pspum/082/2768660
Tetsuo Shibuya, Genus of torus links and cable links, Kobe J. Math. 6 (1989), no. 1, 37–42. MR 1023523
Carl L. Siegel, Über einige Anwendungen diophantischer Approximationen [reprint of Abhandlungen der Preußischen Akademie der Wissenschaften. Physikalisch-mathematische Klasse 1929, Nr. 1], On some applications of Diophantine approximations, Quad./Monogr., vol. 2, Ed. Norm., Pisa, 2014, pp. 81–138 (German). MR 3330350
Jonathan Simon, An algebraic classification of knots in $S^{3}$, Ann. of Math. (2) 97 (1973), 1–13. MR 310861, DOI 10.2307/1970874
William P. Thurston, Three-dimensional manifolds, Kleinian groups and hyperbolic geometry, Bull. Amer. Math. Soc. (N.S.) 6 (1982), no. 3, 357–381. MR 648524, DOI 10.1090/S0273-0979-1982-15003-0
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. MR 1689167
P. J. Weinberger, Finding the number of factors of a polynomial, J. Algorithms 5 (1984), no. 2, 180–186. MR 744488, DOI 10.1016/0196-6774(84)90025-7
Raphael Zentner, Integer homology 3-spheres admit irreducible representations in $\textrm {SL}(2,\Bbb {C})$, Duke Math. J. 167 (2018), no. 9, 1643–1712. MR 3813594, DOI 10.1215/00127094-2018-0004