An elementary proof that linking problems are hard
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908542720540672 |
|---|---|
| author | Cheng, Shannon Chlopecki, Anna Nazar, Saarah Samperton, Eric |
| author_facet | Cheng, Shannon Chlopecki, Anna Nazar, Saarah Samperton, Eric |
| contents | We give a new, elementary proof of what we believe is the simplest known example of a ``natural'' problem in computational 3-dimensional topology that is $\mathsf{NP}$-hard -- namely, the \emph{Trivial Sublink Problem}: given a diagram $L$ of a link in $S^3$ and a positive integer $k$, decide if $L$ contains a $k$ component sublink that is trivial. This problem was previously shown to be $\mathsf{NP}$-hard in independent works of Koenig-Tsvietkova and de Mesmay-Rieck-Sedgwick-Tancer, both of which used reductions from $\mathsf{3SAT}$. The reduction we describe instead starts with the Independent Set Problem, and allows us to avoid the use of Brunnian links such as the Borromean rings. On the technical level, this entails a new conceptual insight: the Trivial Sublink Problem is hard entirely due to mod 2 pairwise linking, with no need for integral or higher order linking. On the pedagogical level, the reduction we describe is entirely elementary, and thus suitable for introducing undergraduates and non-experts to complexity-theoretic low-dimensional topology. To drive this point home, in this work we assume no familiarity with low-dimensional topology, and -- other than Reidemeister's Theorem and Karp's result that the Clique Problem is $\mathsf{NP}$-hard -- we provide more-or-less complete definitions and proofs. We have also constructed a web app that accompanies this work and allows a user to visualize the new reduction interactively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_13120 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An elementary proof that linking problems are hard Cheng, Shannon Chlopecki, Anna Nazar, Saarah Samperton, Eric Computational Complexity Computational Geometry Geometric Topology We give a new, elementary proof of what we believe is the simplest known example of a ``natural'' problem in computational 3-dimensional topology that is $\mathsf{NP}$-hard -- namely, the \emph{Trivial Sublink Problem}: given a diagram $L$ of a link in $S^3$ and a positive integer $k$, decide if $L$ contains a $k$ component sublink that is trivial. This problem was previously shown to be $\mathsf{NP}$-hard in independent works of Koenig-Tsvietkova and de Mesmay-Rieck-Sedgwick-Tancer, both of which used reductions from $\mathsf{3SAT}$. The reduction we describe instead starts with the Independent Set Problem, and allows us to avoid the use of Brunnian links such as the Borromean rings. On the technical level, this entails a new conceptual insight: the Trivial Sublink Problem is hard entirely due to mod 2 pairwise linking, with no need for integral or higher order linking. On the pedagogical level, the reduction we describe is entirely elementary, and thus suitable for introducing undergraduates and non-experts to complexity-theoretic low-dimensional topology. To drive this point home, in this work we assume no familiarity with low-dimensional topology, and -- other than Reidemeister's Theorem and Karp's result that the Clique Problem is $\mathsf{NP}$-hard -- we provide more-or-less complete definitions and proofs. We have also constructed a web app that accompanies this work and allows a user to visualize the new reduction interactively. |
| title | An elementary proof that linking problems are hard |
| topic | Computational Complexity Computational Geometry Geometric Topology |
| url | https://arxiv.org/abs/2509.13120 |