Computational complexity and 3-manifolds and zombies

• Published in 2017
• Added on 2017-07-13

We show the problem of counting homomorphisms from the fundamental group of a homology $3$-sphere $M$ to a finite, non-abelian simple group $G$ is #P-complete, in the case that $G$ is fixed and $M$ is the computational input. Similarly, deciding if there is a non-trivial homomorphism is NP-complete. In both reductions, we can guarantee that every non-trivial homomorphism is a surjection. As a corollary, for any fixed integer $m \ge 5$, it is NP-complete to decide whether $M$ admits a connected $m$-sheeted covering. Our construction is inspired by universality results in topological quantum computation. 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(M) \to G$. An intermediate state of $C$ likewise corresponds to a homomorphism $\pi_1(\Sigma_g) \to G$, where $\Sigma_g$ is a pointed Heegaard surface of $M$ of genus $g$. We analyze the action on these homomorphisms by the pointed mapping class group $\text{MCG}_*(\Sigma_g)$ and its Torelli subgroup $\text{Tor}_*(\Sigma_g)$. By results of Dunfield-Thurston, the action of $\text{MCG}_*(\Sigma_g)$ is as large as possible when $g$ is sufficiently large; we can pass to the Torelli group using the congruence subgroup property of $\text{Sp}(2g,\mathbb{Z})$. Our results can be interpreted as a sharp classical universality property of an associated combinatorial $(2+1)$-dimensional TQFT.

Links

• http://arxiv.org/abs/1707.03811v1
• http://arxiv.org/pdf/1707.03811v1

Other information

BibTeX entry

@article{Computationalcomplexityand3manifoldsandzombies,
	key = {Computationalcomplexityand3manifoldsandzombies},
	type = {article},
	title = {Computational complexity and 3-manifolds and zombies},
	author = {Greg Kuperberg and Eric Samperton},
	abstract = {We show the problem of counting homomorphisms from the fundamental group of a
homology {\$}3{\$}-sphere {\$}M{\$} to a finite, non-abelian simple group {\$}G{\$} is
{\#}P-complete, in the case that {\$}G{\$} is fixed and {\$}M{\$} is the computational input.
Similarly, deciding if there is a non-trivial homomorphism is NP-complete. In
both reductions, we can guarantee that every non-trivial homomorphism is a
surjection. As a corollary, for any fixed integer {\$}m \ge 5{\$}, it is NP-complete
to decide whether {\$}M{\$} admits a connected {\$}m{\$}-sheeted covering.
  Our construction is inspired by universality results in topological quantum
computation. 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(M) \to G{\$}. An intermediate state of {\$}C{\$}
likewise corresponds to a homomorphism {\$}\pi{\_}1(\Sigma{\_}g) \to G{\$}, where
{\$}\Sigma{\_}g{\$} is a pointed Heegaard surface of {\$}M{\$} of genus {\$}g{\$}. We analyze the
action on these homomorphisms by the pointed mapping class group
{\$}\text{\{}MCG{\}}{\_}*(\Sigma{\_}g){\$} and its Torelli subgroup {\$}\text{\{}Tor{\}}{\_}*(\Sigma{\_}g){\$}. By
results of Dunfield-Thurston, the action of {\$}\text{\{}MCG{\}}{\_}*(\Sigma{\_}g){\$} is as
large as possible when {\$}g{\$} is sufficiently large; we can pass to the Torelli
group using the congruence subgroup property of {\$}\text{\{}Sp{\}}(2g,\mathbb{\{}Z{\}}){\$}. Our
results can be interpreted as a sharp classical universality property of an
associated combinatorial {\$}(2+1){\$}-dimensional TQFT.},
	comment = {},
	date_added = {2017-07-13},
	date_published = {2017-12-07},
	urls = {http://arxiv.org/abs/1707.03811v1,http://arxiv.org/pdf/1707.03811v1},
	collections = {Attention-grabbing titles,Basically computer science},
	url = {http://arxiv.org/abs/1707.03811v1 http://arxiv.org/pdf/1707.03811v1},
	urldate = {2017-07-13},
	archivePrefix = {arXiv},
	eprint = {1707.03811},
	primaryClass = {math.GT},
	year = 2017
}