fbpx
Wikipedia

Unknotting problem

February 07, 2023

Unsolved problem in mathematics:

Can unknots be recognized in polynomial time?

(more unsolved problems in mathematics)

In mathematics, the unknotting problem is the problem of algorithmically recognizing the unknot, given some representation of a knot, e.g., a knot diagram. There are several types of unknotting algorithms. A major unresolved challenge is to determine if the problem admits a polynomial time algorithm; that is, whether the problem lies in the complexity class P.

Two simple diagrams of the unknot
A tricky unknot diagram by Morwen Thistlethwaite

Computational complexity

First steps toward determining the computational complexity were undertaken in proving that the problem is in larger complexity classes, which contain the class P. By using normal surfaces to describe the Seifert surfaces of a given knot, Hass, Lagarias & Pippenger (1999) showed that the unknotting problem is in the complexity class NP. Hara, Tani & Yamamoto (2005) claimed the weaker result that unknotting is in AM ∩ co-AM; however, later they retracted this claim.[1] In 2011, Greg Kuperberg proved that (assuming the generalized Riemann hypothesis) the unknotting problem is in co-NP,[2] and in 2016, Marc Lackenby provided an unconditional proof of co-NP membership.[3]

The unknotting problem has the same computational complexity as testing whether an embedding of an undirected graph in Euclidean space is linkless.[4]

Unknotting algorithms

Several algorithms solving the unknotting problem are based on Haken's theory of normal surfaces:

  • Haken's algorithm uses the theory of normal surfaces to find a disk whose boundary is the knot. Haken originally used this algorithm to show that unknotting is decidable, but did not analyze its complexity in more detail.
  • Hass, Lagarias, and Pippenger showed that the set of all normal surfaces may be represented by the integer points in a polyhedral cone and that a surface witnessing the unknottedness of a curve (if it exists) can always be found on one of the extreme rays of this cone. Therefore, vertex enumeration methods can be used to list all of the extreme rays and test whether any of them corresponds to a bounding disk of the knot. Hass, Lagarias, and Pippenger used this method to show that the unknottedness is in NP; later researchers such as Burton (2011a) refined their analysis, showing that this algorithm can be useful (though not polynomial time), with its complexity being a low-order singly-exponential function of the number of crossings.
  • The algorithm of Birman & Hirsch (1998) uses braid foliations, a somewhat different type of structure than a normal surface. However to analyze its behavior they return to normal surface theory.

Other approaches include:

  • The number of Reidemeister moves needed to change an unknot diagram to the standard unknot diagram is at most polynomial in the number of crossings.[5] Therefore, a brute force search for all sequences of Reidemeister moves can detect unknottedness in exponential time.
  • Similarly, any two triangulations of the same knot complement may be connected by a sequence of Pachner moves of length at most doubly exponential in the number of crossings.[6] Therefore, it is possible to determine whether a knot is the unknot by testing all sequences of Pachner moves of this length, starting from the complement of the given knot, and determining whether any of them transforms the complement into a standard triangulation of a solid torus. The time for this method would be triply exponential; however, experimental evidence suggests that this bound is very pessimistic and that many fewer Pachner moves are needed.[7]
  • Any arc-presentation of an unknot can be monotonically simplified to a minimal one using elementary moves.[8] So a brute force search among all arc-presentations of not greater complexity gives a single-exponential algorithm for the unknotting problem.
  • Residual finiteness of the knot group (which follows from geometrization of Haken manifolds) gives an algorithm: check if the group has non-cyclic finite group quotient. This idea is used in Kuperberg's result that the unknotting problem is in co-NP.
  • Knot Floer homology of the knot detects the genus of the knot, which is 0 if and only if the knot is an unknot. A combinatorial version of knot Floer homology allows it to be computed (Manolescu, Ozsváth & Sarkar 2009).
  • Khovanov homology detects the unknot according to a result of Kronheimer and Mrowka.[9] The complexity of Khovanov homology at least as high as the #P-hard problem of computing the Jones polynomial, but it may be calculated in practice using an algorithm and program of Bar-Natan (2007). Bar-Natan provides no rigorous analysis of his algorithm, but heuristically estimates it to be exponential in the pathwidth of a crossing diagram, which in turn is at most proportional to the square root of the number of crossings.

Understanding the complexity of these algorithms is an active field of study.

See also

Notes

  1. ^ Mentioned as a "personal communication" in reference [15] of Kuperberg (2014).
  2. ^ Kuperberg (2014)
  3. ^ Lackenby (2021)
  4. ^ Kawarabayashi, Kreutzer & Mohar (2010).
  5. ^ Lackenby (2015).
  6. ^ Mijatović (2005).
  7. ^ Burton (2011b).
  8. ^ Dynnikov (2006).
  9. ^ Kronheimer & Mrowka (2011)

References

  • Bar-Natan, Dror (2007), "Fast Khovanov homology computations", Journal of Knot Theory and Its Ramifications, 16 (3): 243–255, arXiv:math.GT/0606318, doi:10.1142/S0218216507005294, MR 2320156, S2CID 17036344.
  • Birman, Joan S.; Hirsch, Michael (1998), "A new algorithm for recognizing the unknot", Geometry and Topology, 2: 178–220, arXiv:math/9801126, doi:10.2140/gt.1998.2.175, S2CID 17776505.
  • Burton, Benjamin A. (2011a), "Maximal admissible faces and asymptotic bounds for the normal surface solution space" (PDF), Journal of Combinatorial Theory, Series A, 118 (4): 1410–1435, arXiv:1004.2605, doi:10.1016/j.jcta.2010.12.011, MR 2763065, S2CID 11461722.
  • Burton, Benjamin (2011b), "The Pachner graph and the simplification of 3-sphere triangulations", Proc. 27th ACM Symposium on Computational Geometry, pp. 153–162, arXiv:1011.4169, doi:10.1145/1998196.1998220, S2CID 382685.
  • Dynnikov, Ivan (2006), "Arc-presentations of links: monotonic simplification", Fundamenta Mathematicae, 190: 29–76, arXiv:math/0208153, doi:10.4064/fm190-0-3, S2CID 14137437.
  • Haken, Wolfgang (1961), "Theorie der Normalflächen", Acta Mathematica, 105: 245–375, doi:10.1007/BF02559591.
  • Hara, Masao; Tani, Seiichi; Yamamoto, Makoto (2005), "Unknotting is in AM ∩ co-AM", Proc. 16th ACM-SIAM Symposium on Discrete algorithms (SODA '05), pp. 359–364.
  • Hass, Joel; Lagarias, Jeffrey C.; Pippenger, Nicholas (1999), "The computational complexity of knot and link problems", Journal of the ACM, 46 (2): 185–211, arXiv:math/9807016, doi:10.1145/301970.301971, MR 1693203, S2CID 125854.
  • Hass, Joel; Lagarias, Jeffrey C. (2001), "The number of Reidemeister moves needed for unknotting", Journal of the American Mathematical Society, 14 (2): 399–428, arXiv:math/9807012, doi:10.1090/S0894-0347-01-00358-7, MR 1815217, S2CID 15654705.
  • Kawarabayashi, Ken-ichi; Kreutzer, Stephan; Mohar, Bojan (2010), "Linkless and flat embeddings in 3-space and the unknot problem" (PDF), Proc. ACM Symposium on Computational Geometry (SoCG '10), pp. 97–106, doi:10.1145/1810959.1810975, S2CID 12290801.
  • Kronheimer, Peter; Mrowka, Tomasz (2011), "Khovanov homology is an unknot-detector", Publications Mathématiques de l'IHÉS, 113 (1): 97–208, arXiv:1005.4346, doi:10.1007/s10240-010-0030-y, S2CID 119586228
  • Kuperberg, Greg (2014), "Knottedness is in NP, modulo GRH", Advances in Mathematics, 256: 493–506, arXiv:1112.0845, doi:10.1016/j.aim.2014.01.007, MR 3177300, S2CID 12634367.
  • Lackenby, Marc (2015), "A polynomial upper bound on Reidemeister moves", Annals of Mathematics, Second Series, 182 (2): 491–564, arXiv:1302.0180, doi:10.4007/annals.2015.182.2.3, MR 3418524, S2CID 119662237.
  • Lackenby, Marc (2021), "The efficient certification of Knottedness and Thurston norm", Advances in Mathematics, 387: 107796, arXiv:1604.00290, doi:10.1016/j.aim.2021.107796, S2CID 119307517.
  • Manolescu, Ciprian; Ozsváth, Peter S.; Sarkar, Sucharit (2009), "A combinatorial description of knot Floer homology", Annals of Mathematics, Second Series, 169 (2): 633–660, arXiv:math/0607691, Bibcode:2006math......7691M, doi:10.4007/annals.2009.169.633, MR 2480614, S2CID 15427272.
  • Mijatović, Aleksandar (2005), "Simplical structures of knot complements", Mathematical Research Letters, 12 (6): 843–856, arXiv:math/0306117, doi:10.4310/mrl.2005.v12.n6.a6, MR 2189244, S2CID 7726354

February 07, 2023
unknotting, problem, unsolved, problem, mathematics, unknots, recognized, polynomial, time, more, unsolved, problems, mathematics, mathematics, unknotting, problem, problem, algorithmically, recognizing, unknot, given, some, representation, knot, knot, diagram. Unsolved problem in mathematics Can unknots be recognized in polynomial time more unsolved problems in mathematics In mathematics the unknotting problem is the problem of algorithmically recognizing the unknot given some representation of a knot e g a knot diagram There are several types of unknotting algorithms A major unresolved challenge is to determine if the problem admits a polynomial time algorithm that is whether the problem lies in the complexity class P Two simple diagrams of the unknot A tricky unknot diagram by Morwen Thistlethwaite Contents 1 Computational complexity 2 Unknotting algorithms 3 See also 4 Notes 5 ReferencesComputational complexity EditFirst steps toward determining the computational complexity were undertaken in proving that the problem is in larger complexity classes which contain the class P By using normal surfaces to describe the Seifert surfaces of a given knot Hass Lagarias amp Pippenger 1999 showed that the unknotting problem is in the complexity class NP Hara Tani amp Yamamoto 2005 claimed the weaker result that unknotting is in AM co AM however later they retracted this claim 1 In 2011 Greg Kuperberg proved that assuming the generalized Riemann hypothesis the unknotting problem is in co NP 2 and in 2016 Marc Lackenby provided an unconditional proof of co NP membership 3 The unknotting problem has the same computational complexity as testing whether an embedding of an undirected graph in Euclidean space is linkless 4 Unknotting algorithms EditSeveral algorithms solving the unknotting problem are based on Haken s theory of normal surfaces Haken s algorithm uses the theory of normal surfaces to find a disk whose boundary is the knot Haken originally used this algorithm to show that unknotting is decidable but did not analyze its complexity in more detail Hass Lagarias and Pippenger showed that the set of all normal surfaces may be represented by the integer points in a polyhedral cone and that a surface witnessing the unknottedness of a curve if it exists can always be found on one of the extreme rays of this cone Therefore vertex enumeration methods can be used to list all of the extreme rays and test whether any of them corresponds to a bounding disk of the knot Hass Lagarias and Pippenger used this method to show that the unknottedness is in NP later researchers such as Burton 2011a refined their analysis showing that this algorithm can be useful though not polynomial time with its complexity being a low order singly exponential function of the number of crossings The algorithm of Birman amp Hirsch 1998 uses braid foliations a somewhat different type of structure than a normal surface However to analyze its behavior they return to normal surface theory Other approaches include The number of Reidemeister moves needed to change an unknot diagram to the standard unknot diagram is at most polynomial in the number of crossings 5 Therefore a brute force search for all sequences of Reidemeister moves can detect unknottedness in exponential time Similarly any two triangulations of the same knot complement may be connected by a sequence of Pachner moves of length at most doubly exponential in the number of crossings 6 Therefore it is possible to determine whether a knot is the unknot by testing all sequences of Pachner moves of this length starting from the complement of the given knot and determining whether any of them transforms the complement into a standard triangulation of a solid torus The time for this method would be triply exponential however experimental evidence suggests that this bound is very pessimistic and that many fewer Pachner moves are needed 7 Any arc presentation of an unknot can be monotonically simplified to a minimal one using elementary moves 8 So a brute force search among all arc presentations of not greater complexity gives a single exponential algorithm for the unknotting problem Residual finiteness of the knot group which follows from geometrization of Haken manifolds gives an algorithm check if the group has non cyclic finite group quotient This idea is used in Kuperberg s result that the unknotting problem is in co NP Knot Floer homology of the knot detects the genus of the knot which is 0 if and only if the knot is an unknot A combinatorial version of knot Floer homology allows it to be computed Manolescu Ozsvath amp Sarkar 2009 Khovanov homology detects the unknot according to a result of Kronheimer and Mrowka 9 The complexity of Khovanov homology at least as high as the P hard problem of computing the Jones polynomial but it may be calculated in practice using an algorithm and program of Bar Natan 2007 Bar Natan provides no rigorous analysis of his algorithm but heuristically estimates it to be exponential in the pathwidth of a crossing diagram which in turn is at most proportional to the square root of the number of crossings Understanding the complexity of these algorithms is an active field of study See also EditAlgorithmic topology Unknotting numberNotes Edit Mentioned as a personal communication in reference 15 of Kuperberg 2014 Kuperberg 2014 Lackenby 2021 Kawarabayashi Kreutzer amp Mohar 2010 Lackenby 2015 Mijatovic 2005 Burton 2011b Dynnikov 2006 Kronheimer amp Mrowka 2011 References EditBar Natan Dror 2007 Fast Khovanov homology computations Journal of Knot Theory and Its Ramifications 16 3 243 255 arXiv math GT 0606318 doi 10 1142 S0218216507005294 MR 2320156 S2CID 17036344 Birman Joan S Hirsch Michael 1998 A new algorithm for recognizing the unknot Geometry and Topology 2 178 220 arXiv math 9801126 doi 10 2140 gt 1998 2 175 S2CID 17776505 Burton Benjamin A 2011a Maximal admissible faces and asymptotic bounds for the normal surface solution space PDF Journal of Combinatorial Theory Series A 118 4 1410 1435 arXiv 1004 2605 doi 10 1016 j jcta 2010 12 011 MR 2763065 S2CID 11461722 Burton Benjamin 2011b The Pachner graph and the simplification of 3 sphere triangulations Proc 27th ACM Symposium on Computational Geometry pp 153 162 arXiv 1011 4169 doi 10 1145 1998196 1998220 S2CID 382685 Dynnikov Ivan 2006 Arc presentations of links monotonic simplification Fundamenta Mathematicae 190 29 76 arXiv math 0208153 doi 10 4064 fm190 0 3 S2CID 14137437 Haken Wolfgang 1961 Theorie der Normalflachen Acta Mathematica 105 245 375 doi 10 1007 BF02559591 Hara Masao Tani Seiichi Yamamoto Makoto 2005 Unknotting is in AM co AM Proc 16th ACM SIAM Symposium on Discrete algorithms SODA 05 pp 359 364 Hass Joel Lagarias Jeffrey C Pippenger Nicholas 1999 The computational complexity of knot and link problems Journal of the ACM 46 2 185 211 arXiv math 9807016 doi 10 1145 301970 301971 MR 1693203 S2CID 125854 Hass Joel Lagarias Jeffrey C 2001 The number of Reidemeister moves needed for unknotting Journal of the American Mathematical Society 14 2 399 428 arXiv math 9807012 doi 10 1090 S0894 0347 01 00358 7 MR 1815217 S2CID 15654705 Kawarabayashi Ken ichi Kreutzer Stephan Mohar Bojan 2010 Linkless and flat embeddings in 3 space and the unknot problem PDF Proc ACM Symposium on Computational Geometry SoCG 10 pp 97 106 doi 10 1145 1810959 1810975 S2CID 12290801 Kronheimer Peter Mrowka Tomasz 2011 Khovanov homology is an unknot detector Publications Mathematiques de l IHES 113 1 97 208 arXiv 1005 4346 doi 10 1007 s10240 010 0030 y S2CID 119586228 Kuperberg Greg 2014 Knottedness is in NP modulo GRH Advances in Mathematics 256 493 506 arXiv 1112 0845 doi 10 1016 j aim 2014 01 007 MR 3177300 S2CID 12634367 Lackenby Marc 2015 A polynomial upper bound on Reidemeister moves Annals of Mathematics Second Series 182 2 491 564 arXiv 1302 0180 doi 10 4007 annals 2015 182 2 3 MR 3418524 S2CID 119662237 Lackenby Marc 2021 The efficient certification of Knottedness and Thurston norm Advances in Mathematics 387 107796 arXiv 1604 00290 doi 10 1016 j aim 2021 107796 S2CID 119307517 Manolescu Ciprian Ozsvath Peter S Sarkar Sucharit 2009 A combinatorial description of knot Floer homology Annals of Mathematics Second Series 169 2 633 660 arXiv math 0607691 Bibcode 2006math 7691M doi 10 4007 annals 2009 169 633 MR 2480614 S2CID 15427272 Mijatovic Aleksandar 2005 Simplical structures of knot complements Mathematical Research Letters 12 6 843 856 arXiv math 0306117 doi 10 4310 mrl 2005 v12 n6 a6 MR 2189244 S2CID 7726354 Retrieved from https en wikipedia org w index php title Unknotting problem amp oldid 1131215310, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.