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.