The Computational Complexity of Knot Genus and Spanning Area
| dc.creator | Agol, Ian | |
| dc.creator | Hass, Joel | |
| dc.creator | Thurston, William P. | |
| dc.date | 2002-05-06 | |
| dc.date | 2004-07-10 | |
| dc.date.accessioned | 2026-07-07T04:48:18Z | |
| dc.date.available | 2026-07-07T04:48:18Z | |
| dc.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. | |
| dc.description | 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 | |
| dc.identifier | https://arxiv.org/abs/math/0205057 | |
| dc.identifier | http://arxiv.org/abs/math/0205057 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/63991 | |
| dc.subject | Geometric Topology | |
| dc.subject | Differential Geometry | |
| dc.subject | 11Y16, 57M50, 57M25 | |
| dc.title | The Computational Complexity of Knot Genus and Spanning Area | |
| dc.type | text |