Papex

Open problem · Mathematics · Open

Unknotting problem

Can a computer decide in polynomial time whether a knot diagram shows a loop that can be untangled into a circle?

Summary

Algorithms that recognise the unknot go back to Haken’s work, and the problem is known to lie in both NP and co-NP. Whether it can be solved in polynomial time is unknown.

Why it is open

A knot is a closed loop in space that does not cross itself; it is unknotted, or trivial, if it can be deformed without self-intersection until it lies in a plane [1]. Knots are usually given as diagrams that record which strand passes over which at each crossing, and the number of crossings measures the size of the input [1].

Wolfgang Haken announced an algorithm that decides the question in 1954 and published it in 1961 [1]; what is open is how fast it can be decided. Unknot recognition lies in NP, meaning that a yes-answer has a certificate that an algorithm can check in time polynomial in the size of the input, and in co-NP, meaning that a no-answer has one [6]. "But whether this problem is solvable using a deterministic polynomial-time algorithm remains unknown", Marc Lackenby wrote in a 2020 survey [6], and Alexander He, Eric Sedgwick and Jonathan Spreer repeated in 2025 that it "remains unknown" [10].

Lackenby explains that a problem in both classes is very likely not NP-complete, since an NP-complete problem in co-NP would make NP equal to co-NP, which is widely believed to be false [6]; see the Papex page NP versus co-NP. Such problems are "good candidates for being NP-intermediate", neither solvable in polynomial time nor NP-complete, but evidence for that status is "extremely challenging" to provide [6].

No prize sets the bar; a proof that some algorithm runs in polynomial time, or that none does, would settle the question as listed. Two obstacles recur. The surfaces that certify an unknot, such as a spanning disc, "may be exponentially complicated" in the number of tetrahedra of a triangulation of the knot's complement, and a blind search through polynomially many diagram moves "could not do any better than exponential time" [6].

What is known

Decision procedures (1961–1999). A knot is trivial exactly when it bounds a disc [1]. Haken's method uses normal surfaces, surfaces that meet each tetrahedron of a triangulation of the knot's complement in triangles and squares: if the knot is trivial, a disc showing this can be found among finitely many "fundamental" normal surfaces, which an algorithm can list [6, 14]. Joel Hass, Jeffrey Lagarias and Nicholas Pippenger proved in 1999 that the problem is in NP and gave a deterministic algorithm running in time O(2^cn) for a diagram with n crossings and some constant c; they knew of no earlier explicit complexity bound for Haken's procedure [1].

Certificates of knottedness (2011–2021). Greg Kuperberg showed that knottedness, the complementary question, is in NP if the generalised Riemann hypothesis holds; the hypothesis is needed "only to find a short certificate", not to believe one [4]. Lackenby removed the assumption, using a method outlined by Ian Agol, in a paper posted in 2016 and published in 2021 that also puts the problem of determining the genus of a knot in NP [6, 8].

Reidemeister moves (2015–2026). Reidemeister moves are simple changes to a diagram that leave the knot unchanged [1]. Lackenby proved in 2015 that any diagram of the unknot with c crossings can be reduced to the diagram with no crossings using at most (236c)^11 such moves, through diagrams with at most (7c)^2 crossings [5]. This gives a second proof that the problem is in NP [6]. In a February 2026 preprint, not peer reviewed, he shows that a polynomial bound of this kind holds for each fixed type of knot or link, so that recognising any fixed type is also in NP [13].

Hardness nearby (2006–2021). Deciding whether a knot in a general 3-manifold bounds a surface of given genus is NP-complete, a result of Agol, Hass and William Thurston [6]. Arnaud de Mesmay, Yo'av Rieck, Eric Sedgwick and Martin Tancer proved that deciding whether a diagram of the unknot can be untangled with at most k Reidemeister moves, with k part of the input, is NP-hard, as are detecting a trivial sublink with a given number of components and computing the unlinking number [7].

Recent claims. In slides dated March 2021, Lackenby announced an algorithm that decides whether a diagram with n crossings is the unknot in time 2^O((log n)^3), "quasi-polynomial time", based on hierarchies: sequences of cuts of the knot's complement along surfaces [9]. He, Sedgwick and Spreer's 2025 paper cites the result as announced [10]. In July 2026 Lackenby posted a preprint, not peer reviewed, with "a new algorithm to detect the unknot" built on hierarchies, for which "no challenging invariants need to be computed and no lengthy search procedures are required" [14]. It gives a crude count of the algorithm's steps but no quasi-polynomial bound, and says the algorithm "seems amenable to possible speed-up, which we will explore in future work" [14]. On 16 October 2026 neither the arXiv nor Crossref listed a paper by Lackenby stating the quasi-polynomial bound [9].

Main approaches

Surfaces and hierarchies. Certify the answer with surfaces in the knot's complement: a spanning disc for the unknot, or a hierarchy that ends in balls for a knotted loop [6, 9]. Strongest evidence: this route gave membership in NP and in co-NP [1, 8] and the announced quasi-polynomial algorithm [9]. Main difficulty: the surfaces can be exponentially complicated [6], and earlier algorithms of this kind require "a search through a possibly very extensive search space" [14].

Diagram moves. Simplify the diagram directly [5]. Strongest evidence: the polynomial bound on Reidemeister moves [5]. Main difficulty: a blind search through those moves takes exponential time [6], and finding the fewest moves is NP-hard [7].

Invariants. Compute a quantity that tells the unknot from every other knot. Peter Kronheimer and Tomasz Mrowka proved in 2011 that a knot is the unknot if and only if its reduced Khovanov cohomology has rank 1 [2]. Strongest evidence: this result, and Heegaard Floer homology, which also detects the unknot [2, 14]. Main difficulty: for Khovanov homology there is an exponential lower bound on the worst-case running time, "subject to some standard conjectures in complexity theory" [14].

Practical and learned methods. Benjamin Burton and Melih Ozlen's algorithm, which combines normal surfaces with integer and linear programming, is exponential in theory but "exhibits a clear polynomial time behaviour" on all 2977 non-trivial prime knots with at most 12 crossings [3]. A reinforcement-learning agent of Taylor Applebaum, Lackenby, András Juhász and colleagues, built to bound unknotting numbers (the fewest crossing changes that turn a knot into the unknot), produced 2.6 million distinct hard unknot diagrams as a by-product [11]. In a 2026 preprint, Jason Cantarella, Henrik Schumacher and Clayton Shonkwiler report that most such diagrams are easy for the triangulation-based methods in the programs Regina and SnapPy, and that their simplifier, ReAPR, simplifies every published hard-unknot example they know of, together with new collections, about 2.6 million examples in all, in under 30 seconds of total CPU time [15]. Sergei Gukov, James Halverson, Ciprian Manolescu and Fabian Ruehle applied reinforcement learning, used before to unknot diagrams, to "a much more difficult problem of the same type", deciding when a knot bounds a ribbon disc, which bears on an approach to disproving the four-dimensional smooth Poincaré conjecture [12]. Strongest evidence: the experiments above [3, 15]. Main difficulty: experiments do not bound the worst case, and Burton and Ozlen's algorithm remains exponential in theory [3].

Open sub-questions

  1. Hierarchy length. Lackenby's 2026 algorithm runs at most L(g + 1)^L iterations, where L is the maximal length of a hierarchy and g the maximal pattern-complexity of a decomposing surface [14]. For n-crossing diagrams, can L and g be bounded tightly enough to give the 2^O((log n)^3) running time announced in 2021 [9]?
  2. Hard diagrams and branching. Does Burton and Ozlen's algorithm keep its polynomial-looking running time on the 2.6 million hard unknot diagrams of Applebaum and colleagues [3, 11]?
  3. Worst cases for ReAPR. Is there a family of n-crossing unknot diagrams on which ReAPR needs more than polynomially many re-embedding and pass-move steps [15]?
  4. Smaller exponents. Can every c-crossing diagram of the unknot be reduced with O(c^k) Reidemeister moves for some k well below the 11 in Lackenby's bound [5]?
  5. Shorter certificates. Do the essential hierarchies of the 2026 algorithm give knottedness certificates of lower polynomial degree than those of Lackenby's 2021 proof [8, 14]?

Work on this in Papex

If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.

Key references

  1. Hass, J., Lagarias, J. C. & Pippenger, N. (1999). The computational complexity of knot and link problems. Journal of the ACM 46(2), 185–211. 10.1145/301970.301971 · Checked 16 Oct 2026
  2. Kronheimer, P. B. & Mrowka, T. S. (2011). Khovanov homology is an unknot-detector. Publications Mathématiques de l'IHÉS 113, 97–208. 10.1007/s10240-010-0030-y · Checked 16 Oct 2026
  3. Burton, B. A. & Ozlen, M. (2012). A fast branching algorithm for unknot recognition with experimental polynomial-time behaviour. Preprint, arXiv:1211.1079 (version 3, 9 October 2014), not peer reviewed in this version; the author comment says "To appear in Mathematical Programming", and no published version was found in Crossref on 2026-10-16. Source · Checked 16 Oct 2026
  4. Kuperberg, G. (2014). Knottedness is in NP, modulo GRH. Advances in Mathematics 256, 493–506. 10.1016/j.aim.2014.01.007 · Checked 16 Oct 2026
  5. Lackenby, M. (2015). A polynomial upper bound on Reidemeister moves. Annals of Mathematics 182(2), 491–564. 10.4007/annals.2015.182.2.3 · Checked 16 Oct 2026
  6. Lackenby, M. (2020). Algorithms in 3-manifold theory. Surveys in Differential Geometry 25, 163–213. 10.4310/SDG.2020.v25.n1.a5 · Checked 16 Oct 2026
  7. de Mesmay, A., Rieck, Y., Sedgwick, E. & Tancer, M. (2021). The unbearable hardness of unknotting. Advances in Mathematics 381, 107648. 10.1016/j.aim.2021.107648 · Checked 16 Oct 2026
  8. Lackenby, M. (2021). The efficient certification of knottedness and Thurston norm. Advances in Mathematics 387, 107796. 10.1016/j.aim.2021.107796 · Checked 16 Oct 2026
  9. Lackenby, M. (2021). Unknot recognition in quasi-polynomial time. Talk slides, dated March 2021. Source · Checked 16 Oct 2026
  10. He, A., Sedgwick, E. & Spreer, J. (2025). A practical algorithm for knot factorisation. In 41st International Symposium on Computational Geometry (SoCG 2025), Leibniz International Proceedings in Informatics 332, 55:1–55:15. 10.4230/LIPIcs.SoCG.2025.55 · Checked 16 Oct 2026
  11. Applebaum, T., Blackwell, S., Davies, A., Edlich, T., Juhász, A., Lackenby, M., Tomašev, N. & Zheng, D. (2025). The unknotting number, hard unknot diagrams, and reinforcement learning. Experimental Mathematics, published online 18 August 2025, 1–19. 10.1080/10586458.2025.2542174 · Checked 16 Oct 2026
  12. Gukov, S., Halverson, J., Manolescu, C. & Ruehle, F. (2025). Searching for ribbons with machine learning. Machine Learning: Science and Technology 6(2), 025065. 10.1088/2632-2153/ade362 · Checked 16 Oct 2026
  13. Lackenby, M. (2026). A polynomial upper bound on Reidemeister moves for each link type. Preprint, arXiv:2602.09923 (version 1, 10 February 2026), not peer reviewed. Source · Checked 16 Oct 2026
  14. Lackenby, M. (2026). Incompressible surfaces, hierarchies and unknot recognition. Preprint, arXiv:2607.23350 (version 1, 25 July 2026), not peer reviewed. Source · Checked 16 Oct 2026
  15. Cantarella, J., Schumacher, H. & Shonkwiler, C. (2026). Hard unknots are often easy from a different perspective. Preprint, arXiv:2607.28772 (version 3, 6 October 2026), not peer reviewed. Source · Checked 16 Oct 2026

Page reviewed 16 Oct 2026

Source

Open, as listed by Wikipedia · Unsolved problems in mathematics. Checked 08 Oct 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Mathematics