{
  "id": "math/0205057",
  "version": "v2",
  "published": "2002-05-06T18:47:53.000Z",
  "updated": "2004-07-10T00:25:44.000Z",
  "title": "The Computational Complexity of Knot Genus and Spanning Area",
  "authors": [
    "Ian Agol",
    "Joel Hass",
    "William P. Thurston"
  ],
  "comment": "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"
  ],
  "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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2004-07-10T00:25:44.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "11Y16",
      "57M50",
      "57M25"
    ],
    "keywords": [
      "computational complexity",
      "knot genus",
      "spanning area",
      "three-dimensional topology",
      "similar ideas"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 29,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2002math......5057A"
    }
  }
}