#### Volume 22, issue 6 (2018)

 Recent Issues
 The Journal About the Journal Editorial Board Subscriptions Editorial Interests Editorial Procedure Submission Guidelines Submission Page Ethics Statement ISSN (electronic): 1364-0380 ISSN (print): 1465-3060 Author Index To Appear Other MSP Journals
Computational complexity and $3$–manifolds and zombies

### Greg Kuperberg and Eric Samperton

Geometry & Topology 22 (2018) 3623–3670
##### Abstract

We show the problem of counting homomorphisms from the fundamental group of a homology $3$–sphere $M$ to a finite, nonabelian simple group $G$ is almost parsimoniously $#\mathsf{P}$–complete, when $G$ is fixed and $M$ is the computational input. In the reduction, we guarantee that every nontrivial homomorphism is a surjection. As a corollary, any nontrivial information about the number of nontrivial homomorphisms is computationally intractable assuming standard conjectures in computer science. In particular, deciding if there is a nontrivial homomorphism is $\mathsf{NP}$–complete. Another corollary is that for any fixed integer $m\ge 5$, it is $\mathsf{NP}$–complete to decide whether $M$ admits a connected $m$–sheeted covering.

Given a classical reversible circuit $C\phantom{\rule{0.3em}{0ex}}$, we construct $M$ so that evaluations of $C$ with certain initialization and finalization conditions correspond to homomorphisms ${\pi }_{1}\left(M\right)\to G\phantom{\rule{0.3em}{0ex}}$. An intermediate state of $C$ likewise corresponds to homomorphism ${\pi }_{1}\left({\Sigma }_{g}\right)\to G\phantom{\rule{0.3em}{0ex}}$, where ${\Sigma }_{g}$ is a Heegaard surface of $M$ of genus $g$. We analyze the action on these homomorphisms by the pointed mapping class group ${MCG}_{\ast }\left({\Sigma }_{g}\right)$ and its Torelli subgroup ${Tor}_{\ast }\left({\Sigma }_{g}\right)$. Using refinements of results of Dunfield and Thurston, we show that the actions of these groups are as large as possible when $g$ is large. Our results and our construction are inspired by universality results in topological quantum computation, even though the present work is nonquantum.

One tricky step in the construction is handling an inert “zombie” symbol in the computational alphabet, which corresponds to a trivial homomorphism from the fundamental group of a subsurface of the Heegaard surface.

##### Keywords
NP–hardness, \#P–hardness, $3$–manifold invariants
##### Mathematical Subject Classification 2010
Primary: 20F10, 57M27, 68Q17