1 April 2016
How difficult is it to determine whether a given knot is the unknot? The answer is not known. There might be a polynomial-time algorithm, but so far, this has remained elusive. The complexity of the unknot recognition problem was shown to be in NP by Hass, Lagarias and Pippenger . The main aim of this article is to establish that it is in co-NP. This can be stated equivalently in terms of the KNOTTEDNESS decision problem, which asks whether a given knot diagram represents a non-trivial knot.
Submitted to ORA: