未解決問題、位相幾何学(トポロジー), 応用数学と計算数学、1910年に提起

結び目解消問題（自明な結び目の認識計算量）

部分的に解決

空間内の結び目 $K \subset S^3$ を表す $n$ 個の交点を持つ平面上の結び目図式 $D$ が与えられたとき、 $K$ が自明な結び目 $S^1 \subset S^3$ と全空間同位（アンビエント・イソトピック）であるかどうかをアルゴリズム的に判定せよ。また、その判定が多項式時間 $O(n^c)$ で可能か決定せよ。

研究の最前線 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年、無条件でラッケンビー 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(1)}$ ではなく $n^{O(\log n)}$ となる
$\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$ 交点図式をほどくのに必要なライデマイスター移動の回数に対して、線形または2次のオーダー $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