The computational complexity of knot genus in a fixed 3-manifold

Marc Lackenby, Mehdi YazdiProceedings of the London Mathematical Society 2020

Abstract

In low-dimensional topology, determining the genus of a knot—the minimum genus of an orientable surface it can bound—is a fundamental measure of complexity. While the general problem of determining knot genus in an arbitrary 3-manifold is known to be NP-complete, this paper demonstrates a significant shift in the computational landscape when the surrounding manifold is fixed. We show that for a fixed compact, orientable three-dimensional manifold, the problem of determining knot genus lies in NP and co-NP. This result answers a long-standing question posed by Agol, Hass, and Thurston in 2002 and extends previous knowledge regarding rational homology three-spheres to all fixed 3-manifolds.

Introduction

The "genus" of a knot $K$ is defined as the minimum genus of a Seifert surface (an orientable surface) that the knot can bound. In 2002, Agol, Hass, and Thurston established that if both the knot and the manifold $M$ are provided as input, the problem is NP-complete. This suggests that no efficient algorithm exists for the general case. However, a natural question remained: does the problem become more tractable if the manifold is held constant? For instance, is finding the knot genus in the 3-sphere ($S^3$) or a specific lens space inherently easier?

This research addresses the "Fixed 3-Manifold" version of the problem. By constraining the manifold, the authors demonstrate that the problem's complexity drops into co-NP, meaning there exists an efficient way to verify a "certificate" proving that a knot does not bound a surface of a certain genus. Combined with the membership in NP, this suggests the problem is significantly more structured than the general case.

Theoretical Framework and Methodology

The proof integrates classical 3-manifold topology with modern discrete geometry and algorithmic theory through four primary pillars:

1. Normal Surface Theory

The authors utilize Haken’s framework of normal surfaces. This technique represents surfaces as vectors of non-negative integers within the triangulation of a manifold. By converting topological surfaces into algebraic vectors, the problem of finding a minimal genus surface is transformed into a search within a high-dimensional space.

2. The Thurston Norm

A critical component of the proof is the Thurston norm, which measures the complexity of homology classes in a 3-manifold. The unit ball of this norm is a convex polyhedron. The authors demonstrate that for a fixed manifold, the number of faces and vertices of this polyhedron can be bounded polynomially relative to the knot's crossing number. This provides a geometric boundary for the search space.

3. Mixed Integer Programming (MIP)

To identify the minimum genus surface, the search is formulated as a Mixed Integer Programming problem. Because the first Betti number ($b_1$) of a fixed manifold is constant, the authors can apply Lenstra’s algorithm. Lenstra’s algorithm is capable of solving MIP in polynomial time when the number of integer variables is fixed, which is the case here since $b_1$ is constant for the chosen manifold.

4. Certificate Verification

To establish that the problem is in co-NP, the authors provide a method to construct a certificate proving a knot's genus is strictly greater than a given value $g$. This involves a comprehensive description of the Thurston norm ball for the knot complement, ensuring that no surface of lower genus can exist within the homology classes.

Key Results

The research yields several significant findings for the field of computational topology:

  • Complexity Classification: The decision problem of whether a knot in a fixed closed orientable 3-manifold has genus $\le g$ is proven to be in co-NP (and NP), placing it in a much lower complexity class than the general problem.
  • Extension to Toroidal Boundaries: The results are not limited to closed manifolds; they extend to manifolds with toroidal boundaries (surfaces with the topology of a torus).
  • Algorithmic Bounds: The authors provide an algorithm to construct a triangulation of a knot complement and an efficient basis for its homology in time polynomial to the knot's crossing number. They prove that the number of vertices and faces of the Thurston norm ball for a manifold $X$ is at most $(2m+1)^{b_1^2}$, where $m$ represents the manifold's complexity.

Discussion and Future Directions

The "aha moment" of this work lies in the realization that while a general 3-manifold can possess arbitrarily complex homology, a fixed manifold's constant Betti number allows for a tightly bounded search space. By shifting the focus from finding a single surface to computing the entire Thurston norm ball, the authors capture global geometric information that simplifies the verification process.

However, several questions remain. It is currently unclear if the problem remains in co-NP if the manifold is allowed to vary while keeping the first Betti number ($b_1$) fixed. Additionally, while the authors conjecture that the result holds for manifolds with higher-genus boundaries, the current proof relies specifically on the properties of toroidal boundaries. Finally, while the verification is polynomial in theory, the constants involved in normal surface theory are likely too large for immediate practical implementation on current hardware, leaving a gap between theoretical complexity and computational practice.

Summary updated

Abstract

We show that the problem of deciding whether a knot in a fixed closed orientable 3-dimensional manifold bounds a surface of genus at most $g$ is in co-NP. This answers a question of Agol, Hass, and Thurston in 2002. Previously, this was known for rational homology 3-spheres, by the work of the first author.
BibTeX
@inproceedings{lackenby2020computational,
  author = {Marc Lackenby and Mehdi Yazdi},
  title = {{The computational complexity of knot genus in a fixed 3-manifold}},
  booktitle = {Proceedings of the London Mathematical Society},
  year = {2020},
}
Figure