Computational complexity and 3-manifolds and zombies

Understand

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.