The computational complexity of the local postage stamp problem
<|reference_start|>The computational complexity of the local postage stamp problem: 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.<|reference_end|>
@article{shallit2001the,
    title={The computational complexity of the local postage stamp problem},
    author={Jeffrey Shallit},
    journal={arXiv preprint arXiv:math/0112257},
    year={2001},
    archivePrefix={arXiv},
    eprint={math/0112257},
    primaryClass={math.NT cs.CC math.CO}
}