Volume 22, issue 6 (2018)

Download this article
Download this article For screen
For printing
Recent Issues

Volume 28
Issue 3, 1005–1499
Issue 2, 497–1003
Issue 1, 1–496

Volume 27, 9 issues

Volume 26, 8 issues

Volume 25, 7 issues

Volume 24, 7 issues

Volume 23, 7 issues

Volume 22, 7 issues

Volume 21, 6 issues

Volume 20, 6 issues

Volume 19, 6 issues

Volume 18, 5 issues

Volume 17, 5 issues

Volume 16, 4 issues

Volume 15, 4 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 5 issues

Volume 11, 4 issues

Volume 10, 4 issues

Volume 9, 4 issues

Volume 8, 3 issues

Volume 7, 2 issues

Volume 6, 2 issues

Volume 5, 2 issues

Volume 4, 1 issue

Volume 3, 1 issue

Volume 2, 1 issue

Volume 1, 1 issue

The Journal
About the Journal
Editorial Board
Editorial Procedure
Submission Guidelines
Submission Page
Policies for Authors
Ethics Statement
ISSN (electronic): 1364-0380
ISSN (print): 1465-3060
Author Index
To Appear
Other MSP Journals
Computational complexity and $3$–manifolds and zombies

Greg Kuperberg and Eric Samperton

Geometry & Topology 22 (2018) 3623–3670

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 #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 NP–complete. Another corollary is that for any fixed integer m 5, it is 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 π1(M) G. An intermediate state of C likewise corresponds to homomorphism π1(Σg) G, where Σg is a Heegaard surface of M of genus g. We analyze the action on these homomorphisms by the pointed mapping class group MCG(Σg) and its Torelli subgroup Tor(Σg). 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.

NP–hardness, \#P–hardness, $3$–manifold invariants
Mathematical Subject Classification 2010
Primary: 20F10, 57M27, 68Q17
Received: 18 July 2017
Revised: 28 January 2018
Accepted: 12 February 2018
Published: 23 September 2018
Proposed: Ian Agol
Seconded: Walter Neumann, Rob Kirby
Greg Kuperberg
Department of Mathematics
University of California, Davis
Davis, CA
United States
Eric Samperton
Department of Mathematics
University of California, Davis
Davis, CA
United States