A useful way to study spaces is to understand their covering spaces. This is especially true of 3-manifolds, for which we have powerful results like the virtually Haken and virtually fibered theorems. A related fact is that hyperbolic 3-manifold groups are LERF, which is one way of saying that hyperbolic 3-manifolds have lots of finite sheeted covers. So, one might be interested in the following very basic question: given a fixed integer k, does a 3-manifold M admit a k-sheeted cover?

We show that, if k is at least 5, then this question is NP-complete when we regard M as computational input. Thus, unless P = NP, there is no efficient algorithm to decide when a 3-manifold admits a 5-sheeted cover. More generally, for a fixed finite, nonabelian, simple group G, we show that it is #P-complete to count homomorphisms from \pi_1(M) to G, and that this is true even if M is restricted to be a homology 3-sphere. We also have analogous results for when M is a knot complement. In this talk, I’ll introduce the complexity theory needed to make all of this precise and give a sketch of the proof.