arXiv Analytics

Sign in

arXiv:math/0205057 [math.GT]AbstractReferencesReviewsResources

The Computational Complexity of Knot Genus and Spanning Area

Ian Agol, Joel Hass, William P. Thurston

Published 2002-05-06, updated 2004-07-10Version 2

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.

Comments: This is a revised version of the previous posting, with many minor clarifications and improvements. 29 pages, 5 figures. To appear in Transactions of the AMS
Categories: math.GT, math.DG
Subjects: 11Y16, 57M50, 57M25
Related articles: Most relevant | Search more
arXiv:0805.2042 [math.GT] (Published 2008-05-14, updated 2009-12-10)
Braid ordering and knot genus
arXiv:math/9807016 [math.GT] (Published 1998-07-03)
The Computational Complexity of Knot and Link Problems
arXiv:1707.03811 [math.GT] (Published 2017-07-12)
Computational complexity and 3-manifolds and zombies

Links

Toolbox