The computational complexity of the local postage stamp problem
| dc.creator | Shallit, Jeffrey | |
| dc.date | 2001-12-22 | |
| dc.date.accessioned | 2026-07-07T04:45:28Z | |
| dc.date.available | 2026-07-07T04:45:28Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/math/0112257 | |
| dc.identifier | http://arxiv.org/abs/math/0112257 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/62964 | |
| dc.subject | Number Theory | |
| dc.subject | Computational Complexity | |
| dc.subject | Combinatorics | |
| dc.subject | 11B13 (primary); 11D85; 68Q25; 11Y16 (secondary) | |
| dc.title | The computational complexity of the local postage stamp problem | |
| dc.type | text |