{
  "id": "1707.03811",
  "version": "v1",
  "published": "2017-07-12T17:39:46.000Z",
  "updated": "2017-07-12T17:39:46.000Z",
  "title": "Computational complexity and 3-manifolds and zombies",
  "authors": [
    "Greg Kuperberg",
    "Eric Samperton"
  ],
  "comment": "20 pages",
  "categories": [
    "math.GT",
    "cs.CC"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-07-12T17:39:46.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "computational complexity",
      "non-trivial homomorphism",
      "non-abelian simple group",
      "finalization conditions correspond",
      "sharp classical universality property"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}