The efficient certification of knottedness and Thurston norm

2016/04/01 by Lackenby, Marc · 3 citations
#57K10 #57K30 #68Q17 #FOS: Mathematics #Geometric Topology (math.GT)

paper · doi:10.48550/arxiv.1604.00290

Abstract

We show that the problem of determining whether a knot in the 3-sphere is non-trivial lies in NP. This is a consequence of the following more general result. The problem of determining whether the Thurston norm of a second homology class in a compact orientable 3-manifold is equal to a given integer is in NP. As a corollary, the problem of determining the genus of a knot in the 3-sphere is in NP. We also show that the problem of determining whether a compact orientable 3-manifold has incompressible boundary is in NP.

Cited by

• A fast algorithm for the Hecke representation of the braid group, and applications to the computation of the HOMFLY-PT polynomial and the search for interesting braids
• On knot detection via picture recognition
• An elementary proof that linking problems are hard

Related

• The computational complexity of knot genus in a fixed 3-manifold
• The profinite completion of 3-manifold groups, fiberedness and the Thurston norm
• Thurston norm, fibered manifolds and twisted Alexander polynomials
• A survey of the Thurston norm
• Some conditionally hard problems on links and 3-manifolds