Computational complexity and 3–manifolds and zombies

Kuperberg, Greg; Samperton, Eric

doi:10.2140/gt.2018.22.3623

Download this article
	For screen
	For printing

Recent Issues

The Journal

Submission Guidelines

Submission Page

Policies for Authors

Ethics Statement

ISSN 1364-0380 (online)

ISSN 1465-3060 (print)

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

DOI: 10.2140/gt.2018.22.3623

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 $# 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 \geq 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) \to G$ . An intermediate state of $C$ likewise corresponds to homomorphism $π_{1} (Σ_{g}) \to 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.

Keywords

NP–hardness, \#P–hardness, $3$–manifold invariants

Mathematical Subject Classification 2010

Primary: 20F10, 57M27, 68Q17

References

Publication

Received: 18 July 2017

Revised: 28 January 2018

Accepted: 12 February 2018

Published: 23 September 2018

Proposed: Ian Agol

Seconded: Walter Neumann, Rob Kirby

Authors

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

Volume 22, issue 6 (2018)