The Computational Complexity of Knot Genus and Spanning Area

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.

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