3 years ago

Computational Complexity of Enumerative 3-Manifold Invariants.

Eric Samperton

Fix a finite group $G$. We analyze the computational complexity of the problem of counting homomorphisms $\pi_1(X) \to G$, where $X$ is a topological space treated as computational input. We are especially interested in requiring $G$ to be a fixed, finite, nonabelian, simple group. We then consider two cases: when the input $X=M$ is a closed, triangulated 3-manifold, and when $X=S^3 \setminus K$ is the complement of a knot (presented as a diagram) in $S^3$. We prove complexity theoretic hardness results in both settings. When $M$ is closed, we show that counting homomorphisms $\pi_1(M) \to G$ (up to automorphisms of $G$) is $\#\mathsf{P}$-complete via parsimonious Levin reduction---the strictest type of polynomial-time reduction. This remains true even if we require $M$ to be an integer homology 3-sphere. We prove an analogous result in the case that $X=S^3 \setminus K$ is the complement of a knot.

Both proofs proceed by studying the action of the pointed mapping class group $\mathrm{MCG}_*(\Sigma)$ on the set of homomorphisms $\{\pi_1(\Sigma) \to G\}$ for an appropriate surface $\Sigma$. In the case where $X=M$ is closed, we take $\Sigma$ to be a closed surface with large genus. When $X=S^3 \setminus K$ is a knot complement, we take $\Sigma$ to be a disk with many punctures. Our constructions exhibit classical computational universality for a combinatorial topological quantum field theory associated to $G$. Our "topological classical computing" theorems are analogs of the famous results of Freedman, Larsen and Wang establishing the quantum universality of topological quantum computing with the Jones polynomial at a root of unity. Instead of using quantum circuits, we develop a circuit model for classical reversible computing that is equivariant with respect to a symmetry of the computational alphabet.

Publisher URL: http://arxiv.org/abs/1805.09275

DOI: arXiv:1805.09275v1

You might also like
Never Miss Important Research

Researcher is an app designed by academics, for academics. Create a personalised feed in two minutes.
Choose from over 15,000 academics journals covering ten research areas then let Researcher deliver you papers tailored to your interests each day.

  • Download from Google Play
  • Download from App Store
  • Download from AppInChina

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.