Open problem, Topology, Applied and computational mathematics, posed 1910

Unknotting problem (complexity of recognising the unknot)

Partially solved

Given a knot diagram $D$ in the plane with $n$ crossings representing a knot $K \subset S^3$ , decide algorithmically — and determine whether it can be decided in polynomial time $O(n^c)$ — whether $K$ is ambient isotopic to the trivial unknot $S^1 \subset S^3$ .

Research frontier as of 2026

As of 2026, the unknotting problem is known unconditionally to lie in $\mathsf{NP} \cap \mathsf{coNP}$ , and Marc Lackenby's 2021 announcement gives a quasi-polynomial time algorithm running in $n^{O(\log n)}$ steps, placing unknot recognition alongside graph isomorphism as one of the premier natural problems in $\mathsf{NP} \cap \mathsf{coNP}$ with quasi-polynomial complexity whose membership in $\mathsf{P}$ remains unresolved. In practice, algorithms based on linear programming over normal surfaces (Regina) and dynnikov/braid-foliation simplification run rapidly on diagrams with hundreds of crossings, but certifying worst-case polynomial time $O(n^c)$ remains an open problem.

Best known results

Unknot recognition lies unconditionally in $\mathsf{NP} \cap \mathsf{coNP}$ (Hass–Lagarias–Pippenger 1999 for $\mathsf{NP}$ ; Kuperberg 2014 conditional on GRH and Lackenby 2016/2021 unconditionally for $\mathsf{coNP}$ ).
Every $n$ -crossing diagram of the unknot can be untangled using at most $(236\,n)^{11}$ Reidemeister moves (Lackenby, 2015).
The fastest known deterministic algorithm runs in quasi-polynomial time $n^{O(\log n)}$ (announced by Lackenby in 2021).

Tools and where they stop

Tool	Achieved	Where it stops
Normal surfaces and sutured manifold hierarchies (Haken, Hass–Lagarias–Pippenger, Lackenby)	Places unknot recognition unconditionally in $\mathsf{NP} \cap \mathsf{coNP}$ and yields a quasi-polynomial $n^{O(\log n)}$ algorithm via efficient navigation of sutured hierarchies	Branching along $O(\log n)$ levels of a sutured hierarchy multiplies polynomial choices at each depth, producing $n^{O(\log n)}$ rather than $n^{O(1)}$ time
Group representations into $\operatorname{SL}(2,\mathbb{C})$ and $\operatorname{SL}(2,\mathbb{F}_p)$ (Kronheimer–Mrowka, Kuperberg)	Certifies knottedness by exhibiting a non-abelian homomorphism $\pi_1(S^3 \setminus K) \to \operatorname{SL}(2,\mathbb{F}_p)$ for a prime $p$ of polynomial bit-length (under GRH)	Gives a short nondeterministic witness of knottedness, but finding the representation deterministically requires solving polynomial systems via Gröbner bases, which takes exponential time in the worst case

Open questions

Can the unknotting problem be solved in deterministic polynomial time $\mathsf{P}$ ?
Is there a linear or quadratic upper bound $O(n^2)$ on the number of Reidemeister moves needed to untangle any $n$ -crossing diagram of the unknot?

References

Wolfgang Haken (1961). Theorie der Normalflächen: Ein Isotopiekriterium für den Kreisknoten · DOI:10.1007/BF02559591
Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger (1999). The computational complexity of knot and link problems · DOI:10.1145/301970.301971 · arXiv:math/9807016v1
Marc Lackenby (2015). A polynomial upper bound on Reidemeister moves · DOI:10.4007/annals.2015.182.2.3 · arXiv:1302.0180v3
Marc Lackenby (2021). The efficient certification of knottedness and Thurston norm · DOI:10.1016/j.aim.2021.107796 · arXiv:1604.00290v1