Topology Seminar (Main Talk): Computational complexity and 3-manifolds and zombies

Seminar | January 25 | 4:10-5 p.m. | 3 Evans Hall

Eric Samperton, UC Davis

Department of Mathematics

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.

hongbins@berkeley.edu