Unknotting is in AM ∩ co-AM
Masao Hara, Seiichi Tani, Makoto Yamamoto · Symposium on Discrete Algorithms · 2005
Hass, Lagarias, and Pippenger analyzed the computational complexity of various decision problems in knot theory. They proved that the problem whether a given knot is unknotting is in NP, and conjectured that the problem is contained in NP∩co-NP. Agol, Hass, and Thurston proved that the problem called ManifoldGenus, which is a general problem of Unknotting, is NP-complete. We construct an interactive proof system for Knotting, and prove that the problem is contained in IP(2). Consequently, Unknotting is contained in AM ∩ co-AM. If Unknotting is NP-complete, then Σ2p = Π2p.