未解决问题，拓扑学, 应用与计算数学，1910年提出

解结问题（判定平凡纽结的计算复杂度）

部分解决

给定平面上具有 $n$ 个交叉点、表示纽结 $K \subset S^3$ 的纽结投影图 $D$ ，设计算法判定——并确定能否在多项式时间 $O(n^c)$ 内判定—— $K$ 是否与平凡纽结 $S^1 \subset S^3$ 环境同痕。

研究前沿截至2026年

截至2026年，解结问题已被无条件证明属于 $\mathsf{NP} \cap \mathsf{coNP}$ ，而马克·拉肯比2021年宣布的 $n^{O(\log n)}$ 步准多项式时间算法，使平凡纽结判定与图同构问题并列成为 $\mathsf{NP} \cap \mathsf{coNP}$ 中具有准多项式复杂度、但尚未确定是否属于 $\mathsf{P}$ 的标志性自然问题。在实际计算中，基于正规曲面线性规划（如Regina软件）和辫叶状结构化简的算法对数百个交叉点的纽结图均能快速判定，但严格证明最坏情形下的多项式时间复杂度 $O(n^c)$ 仍是未决难题。

已知最佳结果

平凡纽结判定无条件属于 $\mathsf{NP} \cap \mathsf{coNP}$ （ $\mathsf{NP}$ 由哈斯-拉加里亚斯-皮彭杰于1999年证明； $\mathsf{coNP}$ 由库珀伯格于2014年在GRH下证明，并由拉肯比于2016/2021年无条件证明）。
平凡纽结的任意 $n$ 交叉点图均可通过至多 $(236\,n)^{11}$ 步莱德迈斯特变换解开（拉肯比，2015年）。
目前已知最快的确定性算法运行于准多项式时间 $n^{O(\log n)}$ （拉肯比于2021年宣布）。

使用的方法及其局限

方法	取得的结果	局限所在
正规曲面理论与缝合流形层级（哈肯、哈斯-拉加里亚斯-皮彭杰、拉肯比）	将平凡纽结判定无条件归入 $\mathsf{NP} \cap \mathsf{coNP}$ ，并通过对缝合流形层级的高效搜索给出了 $n^{O(\log n)}$ 准多项式时间算法	沿缝合流形层级的 $O(\log n)$ 层深度进行分支时，每层的多项式选择相乘，导致总时间为 $n^{O(\log n)}$ 而非多项式时间 $n^{O(1)}$
到 $\operatorname{SL}(2,\mathbb{C})$ 与 $\operatorname{SL}(2,\mathbb{F}_p)$ 的群表示（克龙海默-姆罗夫卡、库珀伯格）	（在广义黎曼猜想下）通过给出到多项式比特长度素数 $p$ 的有限域线性群的非交换同态 $\pi_1(S^3 \setminus K) \to \operatorname{SL}(2,\mathbb{F}_p)$ 来认证纽结的非平凡性	虽能提供非平凡性的简短非确定性证书，但确定性地寻找该表示需要利用格罗布纳基求解多项式方程组，在最坏情形下仍需指数时间

尚未解决的问题

解结问题能否在确定性多项式时间 $\mathsf{P}$ 内解决？
将平凡纽结的任意 $n$ 交叉点图解开所需的莱德迈斯特变换次数，是否存在线性或二次上界 $O(n^2)$ ？

参考文献

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