{
  "id": "1605.00598",
  "version": "v1",
  "published": "2016-05-02T18:17:08.000Z",
  "updated": "2016-05-02T18:17:08.000Z",
  "title": "Computational complexity and the conjugacy problem",
  "authors": [
    "Alexei Miasnikov",
    "Paul E. Schupp"
  ],
  "comment": "17 pages, 1 figure; Computability, to appear",
  "doi": "10.3233/COM-160060",
  "categories": [
    "math.GR",
    "math.LO"
  ],
  "abstract": "The conjugacy problem for a finitely generated group $G$ is the two-variable problem of deciding for an arbitrary pair $(u,v)$ of elements of $G$, whether or not $u$ is conjugate to $v$ in $G$. We construct examples of finitely generated, computably presented groups such that for every element $u_0$ of $G$, the problem of deciding if an arbitrary element is conjugate to $u_0$ is decidable in quadratic time but the worst-case complexity of the global conjugacy problem is arbitrary: it can be any c.e. Turing degree , can exactly mirror the Time Hierarchy Theorem, or can be $\\mathcal{NP}$-complete. Our groups also have the property that the conjugacy problem is generically linear time: that is, there is a linear time partial algorithm for the conjugacy problem whose domain has density $1$, so hard instances are very rare. We also consider the complexity relationship of the \"half-conjugacy\" problem to the conjugacy problem. In the last section we discuss the extreme opposite situation: groups with algorithmically finite conjugation.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-05-02T18:17:08.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "20F10",
      "20F06"
    ],
    "keywords": [
      "computational complexity",
      "linear time partial algorithm",
      "extreme opposite situation",
      "time hierarchy theorem",
      "global conjugacy problem"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}