Computational Complexity of Enumerative 3-Manifold Invariants

MaRDI QIDQ6302009zbMATH OpenFDO

Authors Eric Samperton

Publication date 23 May 2018

Abstract: Fix a finite group $G$. We analyze the computational complexity of the problem of counting homomorphisms $p{i}_1(X)oG$, 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}setminusK$ 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 $p{i}_1(M)oG$ (up to automorphisms of $G$) is $$-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}setminusK$ is the complement of a knot. Both proofs proceed by studying the action of the pointed mapping class group $mathrm{MCG}_{\ast }(Sigma)$ on the set of homomorphisms $p{i}_1(Sigma)oG$ 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}setminusK$ 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.

This page was built for publication: Computational Complexity of Enumerative 3-Manifold Invariants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6302009)