2018/05/23 by Eric Samperton, Samperton, Eric
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #FOS: Mathematics #Geometric Topology (math.GT) #Geometric and Algebraic Topology #Group Theory (math.GR) #cs.CC #math.GR #math.GT
paper · pdf · doi:10.48550/arxiv.1805.09275
This is a Ph.D. dissertation based on arXiv:1707.03811 and other forthcoming work
arxiv created 2018/05/23 · openalex publication_date 2018/05/23 · arxiv updated 2018/05/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Fix a finite group G. We analyze the computational complexity of the problem of counting homomorphisms π1(X) → G, where X is a topological space treated as computational input. We are especially interested in requiring G to be a fixed, finite, nonabelian, simple group. We then consider two cases: when the input X=M is a closed, triangulated 3-manifold, and when X=S3 ∖ K is the complement of a knot (presented as a diagram) in S3. We prove complexity theoretic hardness results in both settings. When M is closed, we show that counting homomorphisms π1(M) → G (up to automorphisms of G) is #P-complete via parsimonious Levin reduction---the strictest type of polynomial-time reduction. This remains true even if we require M to be an integer homology 3-sphere. We prove an analogous result in the case that X=S3 ∖ K is the complement of a knot. Both proofs proceed by studying the action of the pointed mapping class group MCG_*(Σ) on the set of homomorphisms \π1(Σ) → G\ for an appropriate surface Σ. In the case where X=M is closed, we take Σ to be a closed surface with large genus. When X=S3 ∖ K is a knot complement, we take Σ to be a disk with many punctures. Our constructions exhibit classical computational universality for a combinatorial topological quantum field theory associated to G. Our "topological classical computing" theorems are analogs of the famous results of Freedman, Larsen and Wang establishing the quantum universality of topological quantum computing with the Jones polynomial at a root of unity. Instead of using quantum circuits, we develop a circuit model for classical reversible computing that is equivariant with respect to a symmetry of the computational alphabet.