The Computational Complexity of Knot Genus and Spanning Area

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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

Keywords

Geometric Topology, Differential Geometry, 11Y16, 57M50, 57M25

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/63991

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0205057
 http://arxiv.org/abs/math/0205057

Collections

arXiv