The efficient certification of knottedness and Thurston norm

Marc LackenbyAdvances 2021 · DOI · arXiv

Introduction

In computational topology, the "Unknot Recognition" problem asks whether a given knot diagram represents a trivial circle. While it has been known since 1999 that verifying a knot is the unknot is in NP, the converse—proving that a knot is non-trivial (Knottedness)—remained a significant challenge. This research provides the first unconditional proof that Knottedness is in NP, thereby placing Unknot Recognition in the rare complexity class NP ∩ co-NP.

The Thurston Norm as a Certificate

The core of the proof lies in the Thurston norm, a measure of the complexity of surfaces within a 3-manifold. By demonstrating that calculating this norm is in NP, the author provides a definitive certificate for knottedness: a knot is non-trivial if and only if its genus is greater than zero. Previous attempts to establish this result often relied on unproven assumptions like the Generalized Riemann Hypothesis (GRH); this work removes those dependencies.

Methodology: Sutured Manifold Hierarchies

The proof departs from standard tetrahedral triangulations, utilizing handle structures and Sutured Manifold Hierarchies. This technique, originally developed by David Gabai, involves decomposing a 3-manifold by repeatedly cutting it along specific surfaces.

Figure 1: The decomposition of the knot $5_1$ through a sutured manifold hierarchy, showing the knot, the initial surface, the manifold exterior, and subsequent surfaces in the hierarchy.

To prevent "complexity explosion" during this decomposition—where the number of handles could grow exponentially—the author introduces several algorithmic innovations:

  1. Regulated Surfaces: These are specialized normal surfaces that respect the manifold's sutures.
  2. Parallelity Bundles: Instead of tracking numerous parallel surface sheets individually, they are treated as a single "bundle" (an $I$-bundle), allowing the algorithm to bypass redundant geometric data.
Figure 6: A schematic representation of the cutting process and the resulting transformation of sutures and surfaces within the manifold hierarchy.

Key Results

The primary result is Theorem 1.1, stating that Knottedness is in NP. Additionally, the paper establishes that:

  • Determining the Thurston norm of a homology class is in NP (Theorem 1.5).
  • Identifying whether a 3-manifold has an incompressible boundary is in NP ∩ co-NP (Theorem 1.7).

Conclusion and Future Outlook

While this work establishes a polynomial-time verifier, it does not yet provide a polynomial-time solver (putting the problem in P). However, the classification of Knottedness within NP ∩ co-NP strongly suggests that a polynomial-time algorithm may eventually be discovered. The techniques developed here, particularly the use of parallelity bundles to compress geometric information, offer a robust framework for future research in 3-manifold topology and computational complexity.

Summary updated

BibTeX
@inproceedings{lackenby2021efficient,
  author = {Marc Lackenby},
  title = {{The efficient certification of knottedness and Thurston norm}},
  booktitle = {Advances},
  year = {2021},
  doi = {10.1016/j.aim.2021.107796},
}
Figure