{
  "id": "1805.09275",
  "version": "v1",
  "published": "2018-05-23T16:48:07.000Z",
  "updated": "2018-05-23T16:48:07.000Z",
  "title": "Computational Complexity of Enumerative 3-Manifold Invariants",
  "authors": [
    "Eric Samperton"
  ],
  "comment": "This is a Ph.D. dissertation based on arXiv:1707.03811 and other forthcoming work",
  "categories": [
    "math.GT",
    "cs.CC",
    "math.GR"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-05-23T16:48:07.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "computational complexity",
      "invariants",
      "complexity theoretic hardness results",
      "parsimonious levin reduction-the strictest type",
      "combinatorial topological quantum field theory"
    ],
    "tags": [
      "dissertation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}