{
  "id": "math/0112257",
  "version": "v1",
  "published": "2001-12-22T21:20:57.000Z",
  "updated": "2001-12-22T21:20:57.000Z",
  "title": "The computational complexity of the local postage stamp problem",
  "authors": [
    "Jeffrey Shallit"
  ],
  "categories": [
    "math.NT",
    "cs.CC",
    "math.CO"
  ],
  "abstract": "The well-studied local postage stamp problem (LPSP) is the following: given a positive integer k, a set of postive integers 1 = a1 < a2 < ... < ak and an integer h >= 1, what is the smallest positive integer which cannot be represented as a linear combination x1 a1 + ... + xk ak where x1 + ... + xk <= h and each xi is a non-negative integer? In this note we prove that LPSP is NP-hard under Turing reductions, but can be solved in polynomial time if k is fixed.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2001-12-22T21:20:57.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "11B13",
      "11D85",
      "68Q25",
      "11Y16"
    ],
    "keywords": [
      "computational complexity",
      "linear combination x1 a1",
      "well-studied local postage stamp problem",
      "smallest positive integer",
      "polynomial time"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2001math.....12257S"
    }
  }
}