Article contents
Isotopy in surface complexes from the computational viewpoint
Published online by Cambridge University Press: 17 April 2009
Abstract
It is shown that the problem of deciding whether a curve in a finite surface complex is isotopic to a point is NP-complete. This contrasts with the recursively enumerable (RE)-completeness of the corresponding homotopy problem, and exhibits surface complexes as a common framework for NP-complete and RE-complete algorithmic problems.
- Type
- Research Article
- Information
- Copyright
- Copyright © Australian Mathematical Society 1979
References
- 2
- Cited by