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
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 $ \textsf {NP} \cap \textsf {co\text {-}NP}$, assuming the generalized Riemann hypothesis. We also show that satellite knot detection is in $ \textsf {NP}$ under the same assumption and that cabled knot detection and composite knot detection are unconditionally in $ \textsf {NP}$. Our algorithms are based on recent work of Kuperberg and of Lackenby on detecting knottedness.


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


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
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
Email: s.sivek@imperial.ac.uk

DOI: https://doi.org/10.1090/tran/7394
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