{
  "id": "1302.5671",
  "version": "v1",
  "published": "2013-02-22T18:36:27.000Z",
  "updated": "2013-02-22T18:36:27.000Z",
  "title": "Knapsack Problems in Groups",
  "authors": [
    "Alexei Myasnikov",
    "Andrey Nikolaev",
    "Alexander Ushakov"
  ],
  "comment": "28 pages, 12 figures",
  "categories": [
    "math.GR"
  ],
  "abstract": "We generalize the classical knapsack and subset sum problems to arbitrary groups and study the computational complexity of these new problems. We show that these problems, as well as the bounded submonoid membership problem, are P-time decidable in hyperbolic groups and give various examples of finitely presented groups where the subset sum problem is NP-complete.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-02-22T18:36:27.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03D15",
      "20F65",
      "20F10",
      "68Q17"
    ],
    "keywords": [
      "knapsack problems",
      "subset sum problem",
      "bounded submonoid membership problem",
      "hyperbolic groups",
      "computational complexity"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 28,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1302.5671M"
    }
  }
}