RECORD
Computational Complexity of Enumerative 3-Manifold Invariants
Geometric Topology · Submitted 23 May 2018
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We prove complexity theoretic hardness results in both settings.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Fix a finite group $G$. We analyze the computational complexity of the problem of counting homomorphisms $\pi_1(X) \to G$, where $X$ is a topological space treated as computational input. We are especially interested in requiring $G$ to be a fixed, finite, nonabelian, simple group. We then consider two cases: when the input $X=M$ is a closed, triangulated 3-manifold, and when $X=S^3 \setminus K$ is the complement of a knot (presented as a diagram) in $S^3$. We prove complexity theoretic hardness results in both settings. When $M$ is closed, we show that counting homomorphisms $\pi_1(M) \to G$ (up to automorphisms of $G$) is $\#\mathsf{P}$-complete via parsimonious Levin reduction---the strictest type of polynomial-time reduction. This remains true even if we require $M$ to be an integer homology 3-sphere. We prove an analogous result in the case that $X=S^3 \setminus K$ is the complement of a knot. Both proofs proceed by studying the action of the pointed mapping class group $\mathrm{MCG}_*(\Sigma)$ on the set of homomorphisms $\{\pi_1(\Sigma) \to G\}$ for an appropriate surface $\Sigma$. In the case where $X=M$ is closed, we take $\Sigma$ to be a closed surface with large genus. When $X=S^3 \setminus K$ is a knot complement, we take $\Sigma$ to be a disk with many punctures. Our constructions exhibit classical computational universality for a combinatorial topological quantum field theory associated to $G$. Our "topological classical computing" theorems are analogs of the famous results of Freedman, Larsen and Wang establishing the quantum universality of topological quantum computing with the Jones polynomial at a root of unity. Instead of using quantum circuits, we develop a circuit model for classical reversible computing that is equivariant with respect to a symmetry of the computational alphabet.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Fix a finite group $G$. | background 0.95 | 0.20 | 0.01 | unclear 0.66 |
| s1 | We analyze the computational complexity of the problem of counting homomorphisms $\pi_1(X) \to G$, where $X$ is a topological space treated as computational input. | contribution 0.92 | 0.86 | 0.07 | asserted 0.87 |
| s2 | We are especially interested in requiring $G$ to be a fixed, finite, nonabelian, simple group. | contribution 0.50 | 0.25 | 0.03 | asserted 0.59 |
| s3 | We then consider two cases: when the input $X=M$ is a closed, triangulated 3-manifold, and when $X=S^3 \setminus K$ is the complement of a knot (presented as a diagram) in $S^3$. | contribution 0.72 | 0.50 | 0.03 | asserted 0.85 |
| s4 | We prove complexity theoretic hardness results in both settings. | result 0.51 | 0.95 | 0.24 | asserted 1.00 |
| s5 | When $M$ is closed, we show that counting homomorphisms $\pi_1(M) \to G$ (up to automorphisms of $G$) is $\#\mathsf{P}$-complete via parsimonious Levin reduction---the strictest type of polynomial-time reduction. | result 1.00 | 0.96 | 0.58 | asserted 1.00 |
| s6 | This remains true even if we require $M$ to be an integer homology 3-sphere. | result 1.00 | 0.92 | 0.09 | asserted 1.00 |
| s7 | We prove an analogous result in the case that $X=S^3 \setminus K$ is the complement of a knot. | result 0.93 | 0.94 | 0.15 | asserted 1.00 |
| s8 | Both proofs proceed by studying the action of the pointed mapping class group $\mathrm{MCG}_*(\Sigma)$ on the set of homomorphisms $\{\pi_1(\Sigma) \to G\}$ for an appropriate surface $\Sigma$. | method 0.99 | 0.91 | 0.06 | asserted 1.00 |
| s9 | In the case where $X=M$ is closed, we take $\Sigma$ to be a closed surface with large genus. | method 0.99 | 0.91 | 0.03 | asserted 1.00 |
| s10 | When $X=S^3 \setminus K$ is a knot complement, we take $\Sigma$ to be a disk with many punctures. | method 0.98 | 0.89 | 0.03 | asserted 1.00 |
| s11 | Our constructions exhibit classical computational universality for a combinatorial topological quantum field theory associated to $G$. | interpretation 0.71 | 0.93 | 0.17 | asserted 1.00 |
| s12 | Our "topological classical computing" theorems are analogs of the famous results of Freedman, Larsen and Wang establishing the quantum universality of topological quantum computing with the Jones polynomial at a root of unity. | interpretation 0.92 | 0.36 | 0.07 | asserted 1.00 |
| s13 | Instead of using quantum circuits, we develop a circuit model for classical reversible computing that is equivariant with respect to a symmetry of the computational alphabet. | method 0.82 | 0.93 | 0.06 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Fix a finite group $G$. We analyze the computational complexity of the problem of counting homomorphisms $\pi_1(X) \to G$, where $X$ is a topological space treated as computational input. We are especially interested in requiring $G$ to be a fixed, finite, nonabelian, simple group. We then consider two cases: when the input $X=M$ is a closed, triangulated 3-manifold, and when $X=S^3 \setminus K$ is the complement of a knot (presented as a diagram) in $S^3$. We prove complexity theoretic hardness results in both settings. When $M$ is closed, we show that counting homomorphisms $\pi_1(M) \to G$ (up to automorphisms of $G$) is $\#\mathsf{P}$-complete via parsimonious Levin reduction---the strictest type of polynomial-time reduction. This remains true even if we require $M$ to be an integer homology 3-sphere. We prove an analogous result in the case that $X=S^3 \setminus K$ is the complement of a knot. Both proofs proceed by studying the action of the pointed mapping class group $\mathrm{MCG}_*(\Sigma)$ on the set of homomorphisms $\{\pi_1(\Sigma) \to G\}$ for an appropriate surface $\Sigma$. In the case where $X=M$ is closed, we take $\Sigma$ to be a closed surface with large genus. When $X=S^3 \setminus K$ is a knot complement, we take $\Sigma$ to be a disk with many punctures. Our constructions exhibit classical computational universality for a combinatorial topological quantum field theory associated to $G$. Our "topological classical computing" theorems are analogs of the famous results of Freedman, Larsen and Wang establishing the quantum universality of topological quantum computing with the Jones polynomial at a root of unity. Instead of using quantum circuits, we develop a circuit model for classical reversible computing that is equivariant with respect to a symmetry of the computational alphabet.
Human review
How the literature uses it
1 arXiv paper cite this in 1 sentence
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.