Volume 22, issue 6 (2018)

 Recent Issues
 The Journal About the Journal Editorial Board Editorial Interests Editorial Procedure Subscriptions 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
Abstract

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\phantom{\rule{0.3em}{0ex}}$, we construct $M$ so that evaluations of $C$ with certain initialization and finalization conditions correspond to homomorphisms ${\pi }_{1}\left(M\right)\to G\phantom{\rule{0.3em}{0ex}}$. An intermediate state of $C$ likewise corresponds to homomorphism ${\pi }_{1}\left({\Sigma }_{g}\right)\to G\phantom{\rule{0.3em}{0ex}}$, 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.

However, your active subscription may be available on Project Euclid at
https://projecteuclid.org/gt

We have not been able to recognize your IP address 18.204.56.185 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

or by using our contact form.

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