{
  "id": "2203.16298",
  "version": "v1",
  "published": "2022-03-30T13:41:27.000Z",
  "updated": "2022-03-30T13:41:27.000Z",
  "title": "Algebraic properties of the first-order part of a problem",
  "authors": [
    "Giovanni Solda",
    "Manlio Valenti"
  ],
  "categories": [
    "math.LO",
    "cs.LO"
  ],
  "abstract": "In this paper we study the notion of first-order part of a computational problem, first introduced by Dzhafarov, Solomon, and Yokoyama, which captures the \"strongest computational problem with codomain $\\mathbb{N}$ that is Weihrauch reducible to $f$\". This operator is very useful to prove separation results, especially at the higher levels of the Weihrauch lattice. We explore the first-order part in relation with several other operators already known in the literature. We also introduce a new operator, called unbounded finite parallelization, which plays an important role in characterizing the first-order part of parallelizable problems. We show how the obtained results can be used to explicitly characterize the first-order part of several known problems.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-03-30T13:41:27.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03D78",
      "03D30",
      "03D55"
    ],
    "keywords": [
      "first-order part",
      "algebraic properties",
      "strongest computational problem",
      "weihrauch lattice",
      "higher levels"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}