Computational complexity and 3–manifolds and zombies

Kuperberg, Greg¹ ; Samperton, Eric¹

¹ Department of Mathematics, University of California, Davis, Davis, CA, United States

Geometry & topology, Tome 22 (2018) no. 6, pp. 3623-3670.

Résumé

We show the problem of counting homomorphisms from the fundamental group of a homology $3$–sphere $M$ to a finite, nonabelian simple group $G$ is almost parsimoniously $\#\mathsf{P}$–complete, when $G$ is fixed and $M$ is the computational input. In the reduction, we guarantee that every nontrivial homomorphism is a surjection. As a corollary, any nontrivial information about the number of nontrivial homomorphisms is computationally intractable assuming standard conjectures in computer science. In particular, deciding if there is a nontrivial homomorphism is $\mathsf{NP}$–complete. Another corollary is that for any fixed integer $m\ge 5$, it is $\mathsf{NP}$–complete to decide whether $M$ admits a connected $m$–sheeted covering.

Given a classical reversible circuit $C$, we construct $M$ so that evaluations of $C$ with certain initialization and finalization conditions correspond to homomorphisms ${\pi }_1\left(M\right)\to G$. An intermediate state of $C$ likewise corresponds to homomorphism ${\pi }_1\left({\Sigma }_g\right)\to G$, where ${\Sigma }_g$ is a Heegaard surface of $M$ of genus $g$. We analyze the action on these homomorphisms by the pointed mapping class group ${MCG}_{\ast }\left({\Sigma }_g\right)$ and its Torelli subgroup ${Tor}_{\ast }\left({\Sigma }_g\right)$. Using refinements of results of Dunfield and Thurston, we show that the actions of these groups are as large as possible when $g$ is large. Our results and our construction are inspired by universality results in topological quantum computation, even though the present work is nonquantum.

One tricky step in the construction is handling an inert “zombie” symbol in the computational alphabet, which corresponds to a trivial homomorphism from the fundamental group of a subsurface of the Heegaard surface.

Détail

DOI : 10.2140/gt.2018.22.3623

Classification : 20F10, 57M27, 68Q17
Keywords: NP–hardness, \#P–hardness, $3$–manifold invariants

Bibliographie

[1] S Aaronson, C Granade, G Kuperberg, V Russo, The complexity zoo, electronic resource

[2] D Aharonov, I Arad, The BQP-hardness of approximating the Jones polynomial, preprint (2000)

[3] G Alagic, C Lo, Quantum invariants of 3–manifolds and NP vs #P, preprint (2014)

[4] S Arora, B Barak, Computational complexity: a modern approach, Cambridge Univ. Press (2009) | DOI

[5] M Aschenbrenner, S Friedl, H Wilton, Decision problems for 3–manifolds and their fundamental groups, from: "Interactions between low-dimensional topology and mapping class groups" (editors R I Baykur, J Etnyre, U Hamenstädt), Geom. Topol. Monogr. 19, Geom. Topol. Publ. (2015) 201 | DOI

[6] R Barbanchon, On unique graph 3–colorability and parsimonious reductions in the plane, Theoret. Comput. Sci. 319 (2004) 455 | DOI

[7] H Bass, M Lazard, J P Serre, Sous-groupes d’indice fini dans SL(n,Z), Bull. Amer. Math. Soc. 70 (1964) 385 | DOI

[8] K Bauer, D Sen, P Zvengrowski, A generalized Goursat lemma, Tatra Mt. Math. Publ. 64 (2015) 1 | DOI

[9] R W Carter, Simple groups of Lie type, 28, Wiley (1972)

[10] H Chen, Applying TQFT to count regular coverings of Seifert 3–manifolds, J. Geom. Phys. 62 (2012) 1347 | DOI

[11] P Diaconis, R L Graham, W M A Kantor, The mathematics of perfect shuffles, Adv. in Appl. Math. 4 (1983) 175 | DOI

[12] R Dijkgraaf, E Witten, Topological gauge theories and group cohomology, Comm. Math. Phys. 129 (1990) 393 | DOI

[13] B R Donald, D R Chang, On the complexity of computing the homology type of a triangulation, from: "32nd Annual Symposium on Foundations of Computer Science", IEEE (1991) 650 | DOI

[14] N M Dunfield, W P Thurston, Finite covers of random 3–manifolds, Invent. Math. 166 (2006) 457 | DOI

[15] B Farb, D Margalit, A primer on mapping class groups, 49, Princeton Univ. Press (2012)

[16] E Fredkin, T Toffoli, Conservative logic, Internat. J. Theoret. Phys. 21 (1982) 219 | DOI

[17] D S Freed, F Quinn, Chern–Simons theory with finite gauge group, Comm. Math. Phys. 156 (1993) 435 | DOI

[18] M H Freedman, M Larsen, Z Wang, A modular functor which is universal for quantum computation, Comm. Math. Phys. 227 (2002) 605 | DOI

[19] M H Freedman, M J Larsen, Z Wang, The two-eigenvalue problem and density of Jones representation of braid groups, Comm. Math. Phys. 228 (2002) 177 | DOI

[20] G Frobenius, I Schur, Über die reellen Darstellungen der endlichen Gruppen, Sitzungsber. Königlich Preussischen Akad. Wiss. 8 (1906) 186

[21] M Goldmann, A Russell, The complexity of solving equations over finite groups, Inform. and Comput. 178 (2002) 253 | DOI

[22] E Goursat, Sur les substitutions orthogonales et les divisions régulières de l’espace, Ann. Sci. École Norm. Sup. 6 (1889) 9 | DOI

[23] P Hall, The Eulerian functions of a group, Quart. J. Math. 7 (1936) 134 | DOI

[24] F Jaeger, D L Vertigan, D J A Welsh, On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Cambridge Philos. Soc. 108 (1990) 35 | DOI

[25] D Johnson, The structure of the Torelli group, I : A finite set of generators for I, Ann. of Math. 118 (1983) 423 | DOI

[26] R Kannan, A Bachem, Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix, SIAM J. Comput. 8 (1979) 499 | DOI

[27] R Koenig, G Kuperberg, B W Reichardt, Quantum computation with Turaev–Viro codes, Ann. Physics 325 (2010) 2707 | DOI

[28] H Krovi, A Russell, Quantum Fourier transforms and the complexity of link invariants for quantum doubles of finite groups, Comm. Math. Phys. 334 (2015) 743 | DOI

[29] G Kuperberg, Involutory Hopf algebras and 3–manifold invariants, Internat. J. Math. 2 (1991) 41 | DOI

[30] G Kuperberg, Denseness and Zariski denseness of Jones braid representations, Geom. Topol. 15 (2011) 11 | DOI

[31] G Kuperberg, Algorithmic homeomorphism of 3–manifolds as a corollary of geometrization, preprint (2015)

[32] G Kuperberg, How hard is it to approximate the Jones polynomial ?, Theory Comput. 11 (2015) 183 | DOI

[33] G Kuperberg, E Samperton, Coloring invariants of knots and links are often intractable, in preparation

[34] W B R Lickorish, An introduction to knot theory, 175, Springer (1997) | DOI

[35] J Maher, Random Heegaard splittings, J. Topol. 3 (2010) 997 | DOI

[36] G A Margulis, Discrete subgroups of semisimple Lie groups, 17, Springer (1991) | DOI

[37] A D Mednykh, Determination of the number of nonequivalent coverings over a compact Riemann surface, Dokl. Akad. Nauk SSSR 239 (1978) 269

[38] J Mennicke, Zur Theorie der Siegelschen Modulgruppe, Math. Ann. 159 (1965) 115 | DOI

[39] C Mochon, Anyons from non-solvable finite groups are sufficient for universal quantum computation, preprint (2000)

[40] B H Neumann, Some remarks on infinite groups, J. London Math. Soc. 12 (1937) 120 | DOI

[41] G Nordh, P Jonsson, The complexity of counting solutions to systems of equations over finite semigroups, from: "Computing and combinatorics" (editors K Y Chwa, J I Munro), Lecture Notes in Comput. Sci. 3106, Springer (2004) 370 | DOI

[42] R W Ogburn, J Preskill, Topological quantum computation, from: "Quantum computing and quantum communications" (editor C P Williams), Lecture Notes in Comput. Sci. 1509, Springer (1999) 341 | DOI

[43] P Olum, Non-abelian cohomology and van Kampen’s theorem, Ann. of Math. 68 (1958) 658 | DOI

[44] B Poonen, Undecidable problems: a sampler, from: "Interpreting Gödel" (editor J Kennedy), Cambridge Univ. Press (2014) 211

[45] N Y Reshetikhin, V G Turaev, Ribbon graphs and their invariants derived from quantum groups, Comm. Math. Phys. 127 (1990) 1 | DOI

[46] N Reshetikhin, V G Turaev, Invariants of 3–manifolds via link polynomials and quantum groups, Invent. Math. 103 (1991) 547 | DOI

[47] K A Ribet, On l–adic representations attached to modular forms, Invent. Math. 28 (1975) 245 | DOI

[48] D P Roberts, A Venkatesh, Hurwitz monodromy and full number fields, Algebra Number Theory 9 (2015) 511 | DOI

[49] E C Rowell, Two paradigms for topological quantum computation, from: "Advances in quantum computation" (editors K Mahdavi, D Koslover), Contemp. Math. 482, Amer. Math. Soc. (2009) 165 | DOI

[50] V G Turaev, Quantum invariants of knots and 3–manifolds, 18, de Gruyter (1994)

[51] L G Valiant, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979) 189 | DOI

[52] L G Valiant, V V Vazirani, NP is as easy as detecting unique solutions, Theoret. Comput. Sci. 47 (1986) 85 | DOI