# Computational complexity and 3-manifolds and zombies

- Published in 2017
- Added on

In the collections

We show the problem of counting homomorphisms from the fundamental group of a homology $3$-sphere $M$ to a finite, non-abelian simple group $G$ is #P-complete, in the case that $G$ is fixed and $M$ is the computational input. Similarly, deciding if there is a non-trivial homomorphism is NP-complete. In both reductions, we can guarantee that every non-trivial homomorphism is a surjection. As a corollary, for any fixed integer $m \ge 5$, it is NP-complete to decide whether $M$ admits a connected $m$-sheeted covering. Our construction is inspired by universality results in topological quantum computation. Given a classical reversible circuit $C$, we construct $M$ so that evaluations of $C$ with certain initialization and finalization conditions correspond to homomorphisms $\pi_1(M) \to G$. An intermediate state of $C$ likewise corresponds to a homomorphism $\pi_1(\Sigma_g) \to G$, where $\Sigma_g$ is a pointed Heegaard surface of $M$ of genus $g$. We analyze the action on these homomorphisms by the pointed mapping class group $\text{MCG}_*(\Sigma_g)$ and its Torelli subgroup $\text{Tor}_*(\Sigma_g)$. By results of Dunfield-Thurston, the action of $\text{MCG}_*(\Sigma_g)$ is as large as possible when $g$ is sufficiently large; we can pass to the Torelli group using the congruence subgroup property of $\text{Sp}(2g,\mathbb{Z})$. Our results can be interpreted as a sharp classical universality property of an associated combinatorial $(2+1)$-dimensional TQFT.

## Links

### BibTeX entry

@article{Computationalcomplexityand3manifoldsandzombies, title = {Computational complexity and 3-manifolds and zombies}, abstract = {We show the problem of counting homomorphisms from the fundamental group of a homology {\$}3{\$}-sphere {\$}M{\$} to a finite, non-abelian simple group {\$}G{\$} is {\#}P-complete, in the case that {\$}G{\$} is fixed and {\$}M{\$} is the computational input. Similarly, deciding if there is a non-trivial homomorphism is NP-complete. In both reductions, we can guarantee that every non-trivial homomorphism is a surjection. As a corollary, for any fixed integer {\$}m \ge 5{\$}, it is NP-complete to decide whether {\$}M{\$} admits a connected {\$}m{\$}-sheeted covering. Our construction is inspired by universality results in topological quantum computation. Given a classical reversible circuit {\$}C{\$}, we construct {\$}M{\$} so that evaluations of {\$}C{\$} with certain initialization and finalization conditions correspond to homomorphisms {\$}\pi{\_}1(M) \to G{\$}. An intermediate state of {\$}C{\$} likewise corresponds to a homomorphism {\$}\pi{\_}1(\Sigma{\_}g) \to G{\$}, where {\$}\Sigma{\_}g{\$} is a pointed Heegaard surface of {\$}M{\$} of genus {\$}g{\$}. We analyze the action on these homomorphisms by the pointed mapping class group {\$}\text{\{}MCG{\}}{\_}*(\Sigma{\_}g){\$} and its Torelli subgroup {\$}\text{\{}Tor{\}}{\_}*(\Sigma{\_}g){\$}. By results of Dunfield-Thurston, the action of {\$}\text{\{}MCG{\}}{\_}*(\Sigma{\_}g){\$} is as large as possible when {\$}g{\$} is sufficiently large; we can pass to the Torelli group using the congruence subgroup property of {\$}\text{\{}Sp{\}}(2g,\mathbb{\{}Z{\}}){\$}. Our results can be interpreted as a sharp classical universality property of an associated combinatorial {\$}(2+1){\$}-dimensional TQFT.}, url = {http://arxiv.org/abs/1707.03811v1 http://arxiv.org/pdf/1707.03811v1}, author = {Greg Kuperberg and Eric Samperton}, comment = {}, urldate = {2017-07-13}, archivePrefix = {arXiv}, eprint = {1707.03811}, primaryClass = {math.GT}, year = 2017, collections = {Attention-grabbing titles,Basically computer science} }