{
  "id": "1302.0580",
  "version": "v2",
  "published": "2013-02-04T04:02:20.000Z",
  "updated": "2013-10-13T12:10:18.000Z",
  "title": "Complexity of equivalence relations and preorders from computability theory",
  "authors": [
    "Egor Ianovski",
    "Keng Meng Ng",
    "Russell Miller",
    "Andre Nies"
  ],
  "comment": "To appear in J. Symb. Logic",
  "categories": [
    "math.LO"
  ],
  "abstract": "We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relations $R, S$, a componentwise reducibility is defined by $ R\\le S \\iff \\ex f \\, \\forall x, y \\, [xRy \\lra f(x) Sf(y)]. $ Here $f$ is taken from a suitable class of effective functions. For us the relations will be on natural numbers, and $f$ must be computable. We show that there is a $\\Pi_1$-complete equivalence relation, but no $\\Pi k$-complete for $k \\ge 2$. We show that $\\Sigma k$ preorders arising naturally in the above-mentioned areas are $\\Sigma k$-complete. This includes polynomial time $m$-reducibility on exponential time sets, which is $\\Sigma 2$, almost inclusion on r.e.\\ sets, which is $\\Sigma 3$, and Turing reducibility on r.e.\\ sets, which is $\\Sigma 4$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2013-10-13T12:10:18.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "computability theory",
      "complete equivalence relation",
      "reducibility",
      "exponential time sets",
      "polynomial time"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1302.0580I"
    }
  }
}