We show the problem of counting homomorphisms from the fundamental group of a homology @math -sphere @math to a finite, non-abelian simple group @math is #P-complete, in the case that @math is fixed and @math 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 @math , it is NP-complete to decide whether @math admits a connected @math -sheeted covering. Our construction is inspired by universality results in topological quantum computation. Given a classical reversible circuit @math , we construct @math so that evaluations of @math with certain initialization and finalization conditions correspond to homomorphisms @math . An intermediate state of @math likewise corresponds to a homomorphism @math , where @math is a pointed Heegaard surface of @math of genus @math . We analyze the action on these homomorphisms by the pointed mapping class group @math and its Torelli subgroup @math . By results of Dunfield-Thurston, the action of @math is as large as possible when @math is sufficiently large; we can pass to the Torelli group using the congruence subgroup property of @math . Our results can be interpreted as a sharp classical universality property of an associated combinatorial @math -dimensional TQFT.
Freedman, Kitaev, and Wang (2002), and later Aharonov, Jones, and Landau (2009), established a quantum algorithm to "additively" approximate the Jones polynomial V(L;t) at any principal root of unity t. The strength of this additive approximation depends exponentially on the bridge number of the link presentation. Freedman, Larsen, and Wang (2002) established that the approximation is universal for quantum computation at a non- lattice, principal root of unity. We show that any value-distinguishing approximation of the Jones polynomial at these non-lattice roots of unity is #P-hard. Given the power to decide whetherjV(L;t)j b for fixed constants 0 1, T(G; x; y) is #P-hard to approximate within a factor of c even for planar graphs G. Along the way, we clarify and generalize both Aaronson's theorem and the Solovay- Kitaev theorem. Recently, Frumkin (9) pointed out that none of the well-known algorithms that transform an integer matrix into Smith (16) or Hermite (12) normal form is known to be polynomially bounded in its running time. In fact, Blankinship (3) noticed--as an empirical fact--that intermediate numbersmaybecome quite large during standard calculations Of these canonical forms. Here we present new algorithms in which both the number of algebraic operations and the number of (binary) digits of all intermediate numbers are bounded by polynomials in the length of the input data (assumed to be encoded in binary). These algorithms also find the multiplier-matrices K, U' and K' such thatAK and U'AK' are the Hermite and Smith normal forms of the given matrix A. This provides the first proof that multipliers with small enough entries exist. 1. Introduction. Every nonsingular integer matrix can be transformed into a lower triangular integer matrix using elementary column operations. This was shown by Hermite ((12), Theorem 1 below). Smith ((16), Theorem 3 below) proved that any integer matrix can be diagonalized using elementary row and column operations. The Smith and Hermite normal forms play an important role in the study of rational matrices (calculating their characteristic equations), polynomial matrices (determining the latent roots), algebraic group theory (Newman 15)), system theory (Heymann and Thorpe (13)) and integer programming (Garfi!akel and Nemhauser (10)). Algorithms that compute Smith andHermite normal forms of an integer matrix are given (among others) by Barnette and Pace (1), Bodewig (5), Bradley (7), Frumkin (9) and Hu (14). The methods of Hu, Bodewig and Bradley are based on the explicit calculation of the greatestcommon divisor (GCD) and a set of multiplierswhereas other algorithms ((1)) perform GCD calculations implicitly. As Frumkin (9) pointed out, none of these algorithms is known to be polynomial. In transforming an integer matrix into Smith or Hermite normal form using known techniques, the number of digits of intermediate numbers does not appear to be bounded by a polynomial in the length of the input data as was pointed out by Blankinship (3), (4-1 and Frumkin (9). We show that determining the Jones polynomial of an alternating link is #P-hard. This is a special case of a wide range of results on the general intractibility of the evaluation of the Tutte polynomial T(M;x,y) of a matroid M except for a few listed special points and curves of the (x,y)-plane