Computational complexity and 3-manifolds and zombies
arXiv:1707.03811 · doi:10.2140/gt.2018.22.3623
Abstract
We show the problem of counting homomorphisms from the fundamental group of a homology -sphere to a finite, non-abelian simple group is #P-complete, in the case that is fixed and 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 , it is NP-complete to decide whether admits a connected -sheeted covering. Our construction is inspired by universality results in topological quantum computation. Given a classical reversible circuit , we construct so that evaluations of with certain initialization and finalization conditions correspond to homomorphisms . An intermediate state of likewise corresponds to a homomorphism , where is a pointed Heegaard surface of of genus . We analyze the action on these homomorphisms by the pointed mapping class group and its Torelli subgroup . By results of Dunfield-Thurston, the action of is as large as possible when is sufficiently large; we can pass to the Torelli group using the congruence subgroup property of . Our results can be interpreted as a sharp classical universality property of an associated combinatorial -dimensional TQFT.
arXiv comment20 pages
References in corpus (14)
- Chern-Simons Theory with Finite Gauge Group
- Quantum computation with Turaev-Viro codes
- Anyons from non-solvable finite groups are sufficient for universal quantum computation
- The two-eigenvalue problem and density of Jones representation of braid groups
- The BQP-hardness of approximating the Jones Polynomial
- A modular functor which is universal for quantum computation
- Finite covers of random 3-manifolds
- How hard is it to approximate the Jones polynomial?
- Random Heegaard splittings
- Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization
- Quantum Fourier Transforms and the Complexity of Link Invariants for Quantum Doubles of Finite Groups
- Hurwitz Monodromy and Full Number Fields
- Applying TQFT to count regular coverings of Seifert 3-manifolds
- Coloring invariants of knots and links are often intractable