3-manifold knot genus is NP-complete

2002/05/19 by Ian Agol, Joel Hass, William P. Thurston · 5 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Geometric and Algebraic Topology #Ubiquitin and proteasome pathways

paper · doi:10.1145/509907.510016

openalex publication_date 2002/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

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 g is NP-complete.

Citations

• Algorithms for the complete decomposition of a closed 3-manifold
• �ber die Topologie des dreidimensionalen Raumes

Cited by

• Linkless and flat embeddings in 3-space and the unknot problem
• Detecting genus in vertex links for the fast enumeration of 3-manifold triangulations
• Maximal admissible faces and asymptotic bounds for the normal surface solution space
• List of NP-complete problems [wikipedia]
• Seifert surface [wikipedia]