Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

On the complexity of torus knot recognition


Authors: John A. Baldwin and Steven Sivek
Journal: Trans. Amer. Math. Soc. 371 (2019), 3831-3855
MSC (2010): Primary 57M25; Secondary 68Q17
DOI: https://doi.org/10.1090/tran/7394
Published electronically: November 16, 2018
MathSciNet review: 3917210
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We show that the problem of recognizing that a knot diagram represents a specific torus knot, or any torus knot at all, is in the complexity class NP${}\cap {}$co-NP, assuming the generalized Riemann hypothesis. We also show that satellite knot detection is in NP under the same assumption and that cabled knot detection and composite knot detection are unconditionally in NP. Our algorithms are based on recent work of Kuperberg and of Lackenby on detecting knottedness.


References [Enhancements On Off] (What's this?)

References

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 57M25, 68Q17

Retrieve articles in all journals with MSC (2010): 57M25, 68Q17


Additional Information

John A. Baldwin
Affiliation: Department of Mathematics, Boston College, Maloney Hall, Fifth Floor, Boston College, Chestnut Hill, Massachusetts 02467-3806
MR Author ID: 772542
Email: john.baldwin@bc.edu

Steven Sivek
Affiliation: Department of Mathematics, Imperial College London, Huxley Building, 180 Queen’s Gate, London SW7 2AZ, United Kingdom
MR Author ID: 781378
Email: s.sivek@imperial.ac.uk

Received by editor(s): June 16, 2017
Received by editor(s) in revised form: September 6, 2017, and September 9, 2017
Published electronically: November 16, 2018
Additional Notes: The first author was supported by NSF Grant DMS-1406383 and NSF CAREER Grant DMS-1454865.
The second author was supported by the Max Planck Institute for Mathematics during some of the period in which this paper was completed.
Article copyright: © Copyright 2018 American Mathematical Society