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
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

Steven Sivek
Affiliation: Department of Mathematics, Imperial College London, Huxley Building, 180 Queen’s Gate, London SW7 2AZ, United Kingdom

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