NP–hard problems naturally arising in knot theory

Koenig, Dale; Tsvietkova, Anastasiia

doi:10.1090/btran/71

NP–hard problems naturally arising in knot theory
HTML articles powered by AMS MathViewer

by Dale Koenig and Anastasiia Tsvietkova HTML | PDF

Trans. Amer. Math. Soc. Ser. B 8 (2021), 420-441

Abstract:

We prove that certain problems naturally arising in knot theory are NP–hard or NP–complete. These are the problems of obtaining one diagram from another one of a link in a bounded number of Reidemeister moves, determining whether a link has an unlinking or splitting number $k$, finding a $k$-component unlink as a sublink, and finding a $k$-component alternating sublink.

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
Alexander Coward and Marc Lackenby, Unknotting genus one knots, Comment. Math. Helv. 86 (2011), no. 2, 383–399. MR 2775133, DOI 10.4171/CMH/227
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
Arnaud de Mesmay, Yo’av Rieck, Eric Sedgwick, and Martin Tancer, The unbearable hardness of unknotting, Adv. Math. 381 (2021), Paper No. 107648, 36. MR 4215750, DOI 10.1016/j.aim.2021.107648
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
M. R. Garey, D. S. Johnson, and R. Endre Tarjan, The planar Hamiltonian circuit problem is NP-complete, SIAM J. Comput. 5 (1976), no. 4, 704–714. MR 444516, DOI 10.1137/0205049
Oded Goldreich, P, NP, and NP-completeness, Cambridge University Press, Cambridge, 2010. The basics of computational complexity. MR 2779481, DOI 10.1017/CBO9780511761355
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
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
Chuichiro Hayashi, The number of Reidemeister moves for splitting a link, Math. Ann. 332 (2005), no. 2, 239–252. MR 2178061, DOI 10.1007/s00208-004-0599-x
Marc Lackenby, Elementary knot theory, Lectures on geometry, Clay Lect. Notes, Oxford Univ. Press, Oxford, 2017, pp. 29–64. MR 3676592
Marc Lackenby, A polynomial upper bound on Reidemeister moves for each link type, In preparation.
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, Some conditionally hard problems on links and 3-manifolds, Discrete Comput. Geom. 58 (2017), no. 3, 580–595. MR 3690662, DOI 10.1007/s00454-017-9905-8
Marc Lackenby, Links with splitting number one, Geom. Dedicata, to appear. arXiv:1808.05495, 2018.
W. Menasco, Closed incompressible surfaces in alternating knot and link complements, Topology 23 (1984), no. 1, 37–44. MR 721450, DOI 10.1016/0040-9383(84)90023-5
Kurt Reidemeister, Knoten und Gruppen, Abh. Math. Sem. Univ. Hamburg 5 (1927), no. 1, 7–23 (German). MR 3069461, DOI 10.1007/BF02952506
Dale Rolfsen, Knots and links, Mathematics Lecture Series, No. 7, Publish or Perish, Inc., Berkeley, Calif., 1976. MR 0515288