Skip to main content
The Computational Complexity of Knot Genus and Spanning Area
Published Web Location
https://arxiv.org/pdf/math/0205057.pdfNo data is associated with this publication.
Abstract
We investigate the computational complexity of some problems in three-dimensional topology and geometry. We show that the problem of determining a bound on the genus of a knot in a 3-manifold, is NP-complete. Using similar ideas, we show that deciding whether a curve in a metrized PL 3-manifold bounds a surface of area less than a given constant C is NP-hard.