The efficient certification of knottedness and Thurston norm

Author: 

Lackenby, M

Publication Date: 

1 April 2016

Journal: 

arXiv

Last Updated: 

2020-02-14T15:07:38.193+00:00

abstract: 

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 [10]. 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.

Symplectic id: 

614586

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article