Some Conditionally Hard Problems on Links and 3-Manifolds

Marc Lackenby

Abstract

In low-dimensional topology, many fundamental decision problems are known to be algorithmically solvable, yet their computational efficiency remains poorly understood. Marc Lackenby addresses this gap by establishing the conditional hardness of several key problems. This paper proves that determining the Thurston complexity of unoriented links in the 3-sphere is NP-complete and that the sublink problem is NP-hard. Furthermore, it provides a Karp-reduction from the Graph Isomorphism problem to the 3-manifold homeomorphism problem. These results offer a rigorous complexity-theoretic foundation for the observed difficulty of these topological puzzles.

Introduction

The field of low-dimensional topology has long grappled with the distinction between "solvability" and "efficiency." While algorithms exist for the homeomorphism problem of 3-manifolds and the equivalence of links, their practical utility is often limited by unknown or high computational complexity. Prior to this work, few problems involving "classical" links—those specifically in the 3-sphere ($S^3$)—were known to be conditionally hard. Most existing hardness results were confined to more abstract or complex 3-manifolds. Lackenby bridges this divide by demonstrating that even in the relatively simple setting of $S^3$, natural topological questions can be computationally formidable.

Methodology: Complexity Reductions

Lackenby employs computational complexity reductions to map known hard problems from computer science onto topological questions.

  1. Thurston Complexity: The author reduces the 1-in-3-SAT problem (an NP-complete logic problem) to the task of finding the minimal Thurston complexity of an unoriented link. By utilizing Normal Surface Theory, he provides a "certificate" for the upper bound that can be verified in polynomial time, placing the problem firmly in NP.
  2. 3-Manifold Homeomorphism: A Karp-reduction is established from the Graph Isomorphism (GI) problem. Lackenby constructs a specific 3-manifold $M(\Gamma)$ from a graph $\Gamma$ such that two manifolds are homeomorphic if and only if their parent graphs are isomorphic.
  3. The Sublink Problem: The Hamiltonian Path problem is reduced to the sublink problem (deciding if one link is a subset of another) through the construction of "trefoil chains" that encode graph paths.

Key Insights: Encoding Logic in Topology

A central insight of the paper is the role of orientation. While determining the genus of a knot is likely not NP-complete (residing in NP $\cap$ co-NP), removing the orientation requirement for a link makes the problem NP-complete. This subtle shift significantly alters the computational landscape.

To achieve the NP-hardness result for Thurston complexity, Lackenby uses "satellite links." He places link components inside a "sentence solid torus" based on a specific knot $K$. This construction allows Boolean constraints to be encoded directly into the topology of the surface bounded by the link.

The basic satellite link component $K$ used to encode Boolean constraints.

The full reduction for Thurston complexity involves a complex arrangement where variables and clauses are represented by linked components, as seen in the construction for a 1-in-3-SAT instance.

A link construction representing a 1-in-3-SAT instance, where variables $v_i$ and clauses $c_j$ are encoded into the link's topology.

For the homeomorphism problem, the author leverages the JSJ decomposition of 3-manifolds. This topological "DNA" allows for the creation of manifolds where Seifert fiber space components and their connections mirror the vertices and edges of a graph. Similarly, for the sublink problem, "trefoil chains" (alternating trefoils and unknots) act as a topological ruler to verify the existence of a Hamiltonian path.

Key Results and Implications

The paper establishes three major theorems:

  • Theorem 1.1: Determining an upper bound for the Thurston complexity of an unoriented classical link is NP-complete. This is a definitive result, providing both lower and upper bounds on difficulty.
  • Theorem 1.2: The Graph Isomorphism problem is Karp-reducible to the homeomorphism problem for closed 3-manifolds. This sets a non-trivial lower bound for identifying 3-manifolds.
  • Theorem 1.3: The Sublink Problem is NP-hard.

Conclusion and Future Directions

While these results significantly advance our understanding of topological complexity, the "holy grail" remains: proving that the equivalence problem for classical knots is NP-hard. The equivalence problem is more rigid than the sublink problem, making reductions more challenging. Additionally, since Graph Isomorphism is not known to be NP-complete (currently sitting in quasipolynomial time), the result for 3-manifold homeomorphism provides a lower bound but does not yet prove NP-hardness. Future work will likely focus on tightening these bounds and tackling the knot equivalence problem.

Summary updated

Abstract

We show that three natural decision problems about links and 3-manifolds are computationally hard, assuming some conjectures in complexity theory. The first problem is determining whether a link in the 3-sphere bounds a Seifert surface with Thurston norm at most a given integer; this is shown to be NP-complete. The second problem is the homeomorphism problem for closed 3-manifolds; this is shown to be at least as hard as the graph isomorphism problem. The third problem is determining whether a given link in the 3-sphere is a sublink of another given link; this is shown to be NP-hard.
BibTeX
@article{lackenby2017some,
  author = {Marc Lackenby},
  title = {{Some Conditionally Hard Problems on Links and 3-Manifolds}},
  journal = {Discret. Comput. Geom.},
  year = {2017},
  doi = {10.1007/s00454-017-9905-8},
}
Figure