Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

We consider the computational complexity of counting homomorphisms from 3-manifold groups to fixed finite groups $G$. Let $G$ either be non-abelian simple or $S_m$, where $m \geq 5$. Then counting homomorphisms from fundamental groups of 3-manifolds to $G$ is $\#\mathsf{P}$-complete. In particular, for fixed $m \geq 5$, it is $\mathsf{NP}$-complete to decide when a 3-manifold admits a connected $m$-sheeted cover.

These results follow from an analysis of the action of the pointed mapping class group $\text{Mod}_*(\Sigma_g)$ on the set of homomorphisms $X_g := \{\pi_1(\Sigma_g) \to G\}$. We build on ideas of Dunfield-Thurston that were originally used in the context of random 3-manifolds. In particular, we show that when $g$ is large enough, there exists a subgroup of $\text{Mod}_*(\Sigma_{2g})$ that acts on $X_g^2$ in a manner that allows us to produce gadgets encoding reversible logic gates. Our construction can be considered as a classical analogue of topological quantum computing. This is joint work with Greg Kuperberg.