Isotopy in surface complexes from the computational viewpoint
John Stillwell · Bulletin of the Australian Mathematical Society · 1979
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.