The Computational Complexity of Classical Knot Recognition

Kazuhiro Ichihara, Yuya Nishimura, Seiichi Tani

The classical knot recognition problem is the problem of determining whether the virtual knot represented by a given diagram is classical. We prove that this problem is in NP, and…