{
  "id": "1109.6749",
  "version": "v1",
  "published": "2011-09-30T08:34:31.000Z",
  "updated": "2011-09-30T08:34:31.000Z",
  "title": "Characterizing the strongly jump-traceable sets via randomness",
  "authors": [
    "Noam Greenberg",
    "Denis Hirschfeldt",
    "Andre Nies"
  ],
  "comment": "41 pages",
  "categories": [
    "math.LO"
  ],
  "abstract": "We show that if a set $A$ is computable from every superlow 1-random set, then $A$ is strongly jump-traceable. This theorem shows that the computably enumerable (c.e.) strongly jump-traceable sets are exactly the c.e.\\ sets computable from every superlow 1-random set. We also prove the analogous result for superhighness: a c.e.\\ set is strongly jump-traceable if and only if it is computable from every superhigh 1-random set. Finally, we show that for each cost function $c$ with the limit condition there is a 1-random $\\Delta^0_2$ set $Y$ such that every c.e.\\ set $A \\le_T Y$ obeys $c$. To do so, we connect cost function strength and the strength of randomness notions. This result gives a full correspondence between obedience of cost functions and being computable from $\\Delta^0_2$ 1-random sets.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-09-30T08:34:31.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03D32"
    ],
    "keywords": [
      "strongly jump-traceable sets",
      "connect cost function strength",
      "characterizing",
      "computable",
      "full correspondence"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 41,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1109.6749G"
    }
  }
}