Computational complexity and 3-manifolds and zombies

Fix a nonabelian, finite, simple group G. We show the problem of counting homomorphisms from fundamental groups of 3-manifolds to G is computationally intractable---assuming standard conjectures in computer science. More precisely, the problem is #P-complete. Similarly, the problem of deciding when a 3-manifold admits a nontrivial homomorphism to G is NP-complete. The proof of these theorems is conceptually related to topological quantum computing. The key topological idea involved in our proof is a stable description of the action of the mapping class group of a compact surface with one boundary component, on the set of homomorphisms from the surface group to G. This is joint work with Greg Kuperberg.