{
  "id": "1408.6509",
  "version": "v1",
  "published": "2014-08-27T19:46:14.000Z",
  "updated": "2014-08-27T19:46:14.000Z",
  "title": "Knapsack problems in products of groups",
  "authors": [
    "Elizaveta Frenkel",
    "Andrey Nikolaev",
    "Alexander Ushakov"
  ],
  "comment": "12 pages, 5 figures",
  "categories": [
    "math.GR",
    "cs.CC"
  ],
  "abstract": "The classic knapsack and related problems have natural generalizations to arbitrary (non-commutative) groups, collectively called knapsack-type problems in groups. We study the effect of free and direct products on their time complexity. We show that free products in certain sense preserve time complexity of knapsack-type problems, while direct products may amplify it.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-08-27T19:46:14.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03D15",
      "20F65",
      "20F10",
      "68Q45"
    ],
    "keywords": [
      "knapsack problems",
      "sense preserve time complexity",
      "direct products",
      "knapsack-type problems",
      "natural generalizations"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1408.6509F"
    }
  }
}