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.
Our approach to th:main (and that of Krovi and Russell for their results) is inspired by quantum computation and topological quantum field theory. Every unitary modular tensor category (UMTC) @math yields a unitary 3-dimensional topological quantum field theory @cite_37 @cite_31 @cite_42 . The topological quantum field theory assigns a vector space @math , or , to every oriented, closed surface. It also assigns a state space @math to every oriented, closed surface with @math boundary circles, where @math is an object in @math interpreted as the color" of each boundary circle. Each state space @math has a projective action of the mapping class group @math . (In fact the unpointed mapping class group @math acts, but we will keep the basepoint for convenience.) These mapping class group actions then extend to invariants of 3-manifolds and links in 3-manifolds.
@cite_37 @cite_42 @cite_31
2088353214 2080743555
The generalization of Jones polynomial of links to the case of graphs inR3 is presented. It is constructed as the functor from the category of graphs to the category of representations of the quantum groups. The aim of this paper is to construct new topological invariants of compact oriented 3-manifolds and of framed links in such manifolds. Our invariant of (a link in) a closed oriented 3-manifold is a sequence of complex numbers parametrized by complex roots of 1. For a framed link in S 3 the terms of the sequence are equale to the values of the (suitably parametrized) Jones polynomial of the link in the corresponding roots of 1. In the case of manifolds with boundary our invariant is a (sequence of) finite dimensional complex linear operators. This produces from each root of unity q a 3-dimensional topological quantum field theory