|
The computational complexity of knot genus and spanning area
Author(s):
Ian
Agol;
Joel
Hass;
William
Thurston
Journal:
Trans. Amer. Math. Soc.
358
(2006),
3821-3850.
MSC (2000):
Primary 11Y16, 57M50;
Secondary 57M25
Posted:
December 20, 2005
Retrieve article in:
PDF
Abstract |
References |
Similar articles |
Additional information
Abstract:
We show that the problem of deciding whether a polygonal knot in a closed three-dimensional manifold bounds a surface of genus at most  is NP-complete. We also show that the problem of deciding whether a curve in a PL manifold bounds a surface of area less than a given constant  is NP-hard.
References:
-
- 1.
- M. Dehn, ``Uber die Topologie des dreidimensional Raumes'', Math. Annalen, 69 (1910) 137-168. MR 1511580
- 2.
- M.R. Garey and D.S. Johnson, ``Computers and intractability. A guide to the theory of NP-completeness'', W. H. Freeman and Co., San Francisco, 1979. MR 0519066 (80g:68056)
- 3.
- W. Haken, ``Theorie der Normalflächen: Ein Isotopiekriterium für den Kreisknoten'', Acta Math., 105 (1961) 245-375. MR 0141106 (25:4519a)
- 4.
- J. Hass, ``Algorithms for recognizing knots and 3-manifolds'', Chaos, Solitons and Fractals, 9 (1998) 569-581. MR 1628743 (2000a:57038)
- 5.
- J. Hass, J. C. Lagarias and N. Pippenger, ``The computational complexity of Knot and Link problems'', Journal of the ACM, 46 (1999) 185-211. MR 1693203 (2000g:68056)
- 6.
- J. Hass and J. C. Lagarias, ``The number of Reidemeister moves needed for unknotting'', J. Amer. Math. Soc. 14 (2001), no. 2, 399-428 MR 1815217 (2001m:57012)
- 7.
- G. Hemion, The Classification of Knots and
 -Dimensional Spaces, Oxford University Press, 1992. MR 1211184 (94g:57015) - 8.
- J. Hempel, 3-Manifolds, Princeton University Press, Princeton, NJ, 1976. MR 0415619 (54:3702)
- 9.
- W. Jaco, Lectures on three-manifold topology, CBMS Regional Conference Series in Mathematics, 43 AMS, Providence, RI, 1980. MR 0565450 (81k:57009)
- 10.
- W. Jaco and U. Oertel, ``An Algorithm to Decide If a
 -Manifold Is a Haken Manifold'', Topology, 23 (1984) 195-209. MR 0744850 (85j:57014) - 11.
- W. Jaco and J. L. Tollefson, ``Algorithms for the Complete Decomposition of a Closed
 -Manifold'', Illinois J. Math., 39 (1995) 358-406. MR 1339832 (97a:57014) - 12.
- W. Jaco and J. H. Rubinstein, ``PL Equivariant Surgery and Invariant Decompositions of
 -Manifolds'', Advances in Math., 73 (1989) 149-191. MR 0987273 (90g:57016) - 13.
- F. Jaeger, D. L. Vertigan and D. J. A. Welsh, ``On the Computational Complexity of the Jones and Tutte Polynomials'', Math. Proc. Cambridge Phil. Soc., 108 (1990) 35-53. MR 1049758 (91h:05038)
- 14.
- H. Kneser, ``Geschlossene Flächen in dreidimensionalen Mannigfaltigkeiten'', Jahresbericht Math. Verein., 28 (1929) 248-260.
- 15.
- E. E. Moise, ``Affine Structures in
 -Manifolds, V: The Triangulation Theorem and Hauptvermutung'', Ann. Math., 56 (1952) 96-114. MR 0048805 (14:72d) - 16.
- C.H. Papadimitriou, Computational complexity. Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285 (95f:68082)
- 17.
- M. O. Rabin, ``Recursive Unsolvability of Group-Theoretic Problems'', Ann. Math., 67 (1958) 172-194. MR 0110743 (22:1611)
- 18.
- J.H. Rubinstein, ``An algorithm to recognize the
 -sphere'', Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Zurich, 1994), Birkhauser, Basel, 601-611. MR 1403961 (97e:57011) - 19.
- Schaefer, T.J. ``The complexity of satisfiability problems'', Proc 10th Ann. ACM. Symp. on Theory of Computing, ACM, NY (1978) 216-226. MR 0521057 (80d:68058)
- 20.
- A. Schrijver, Theory of Linear and Integer Programming, John Wiley and Sons, 1986. MR 0874114 (88m:90090)
- 21.
- H. Schubert, ``Bestimmung der Primfaktorzerlegung von Verkettungen'', Math. Zeitschr., 76 (1961) 116-148. MR 0141107 (25:4519b)
- 22.
- A. Sebö, ``Hilbert Bases, Caratheodory's Theorem and Combinatorial Optimization'', in: R. Kannan and W. R. Pulleyblank (Eds.), Integer Programming and Combinatorial Optimization, University of Waterloo Press, 1990, 431-455.
- 23.
- H. Seifert, ``Über das Geschlecht von Knoten'', Math. Annalen, 110 (1935) 571-592. MR 1512955
- 24.
- A. Thompson, Thin position and the recognition problem for
 . Math. Res. Lett. 1 (1994), 613-630. MR 1295555 (95k:57015) - 25.
- D. J. A. Welsh, Complexity: Knots, Colourings and Counting, Cambridge University Press, 1993. MR 1245272 (94m:57027)
- 26.
- D. J. A. Welsh, ``The Complexity of Knots'', Ann. Discr. Math., 55 (1993) 159-173. MR 1217989 (94c:57021)
- 27.
- D. J. A. Welsh, ``Knots and Braids'', Contemp. Math., 147 (1993) 109-123. MR 1224698 (94g:57014)
Similar Articles:
Retrieve articles in Transactions of the American Mathematical Society
with MSC
(2000):
11Y16, 57M50,
57M25
Retrieve articles in all Journals with MSC
(2000):
11Y16, 57M50,
57M25
Additional Information:
Ian
Agol
Affiliation:
Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, Chicago, Illinois 60607
Email:
agol@math.uic.edu
Joel
Hass
Affiliation:
School of Mathematics, Institute for Advanced Study and Department of Mathematics, University of California, Davis, California 95616
Email:
hass@math.ucdavis.edu
William
Thurston
Affiliation:
Department of Mathematics, University of California, Davis, California 95616
Address at time of publication:
Department of Mathematics, Cornell University, Ithaca, New York 14853
Email:
wpt@math.ucdavis.edu, wpt@math.cornell.edu
DOI:
10.1090/S0002-9947-05-03919-X
PII:
S 0002-9947(05)03919-X
Keywords:
Computational topology,
complexity,
knot,
3-manifold,
NP-complete,
normal surface,
genus
Received by editor(s):
July 17, 2002
Received by editor(s) in revised form:
May 28, 2004
Posted:
December 20, 2005
Additional Notes:
The first author was partially supported by ARC grant 420998. This work was carried out while the second author was visiting the Institute for Advanced Study, and was partially supported by NSF grant DMS-0072348, and by a grant to the Institute for Advanced Study by AMIAS. The third author was partially supported by NSF grant DMS-9704286.
Copyright of article:
Copyright
2005,
Ian Agol, Joel Hass, and William Thurston
|
Comments: webmaster@ams.org