Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

We show that counting homomorphisms from fundamental groups of 3-manifolds to a fixed target group G is hard, when G is a finite, nonabelian, simple group. More precisely, deciding if a 3-manifold has fundamental group which admits a nontrivial map to G is NP-complete, and computing the number of nontrivial maps is #P-complete. We will start by giving a brief introduction to the relevant complexity classes. We then explain how the problem reduces to understanding the action of the mapping class group of a surface with boundary on the set of homomorphisms from that surface's fundamental group to G. This is joint work with my advisor, Greg Kuperberg.