On the complexity of torus knot recognition

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

23 pages; v2: reorganized section 2, other minor changes

References in corpus (2)

• Integer homology 3-spheres admit irreducible representations in SL(2,C)
• Dehn surgery, the fundamental group and SU(2)

Cited by in corpus (2)

• Recognition of Seifert fibered spaces with boundary is in NP
• On the complexity of cusped non-hyperbolicity