The computational complexity of the local postage stamp problem

Details The computational complexity of the local postage stamp problem The computational complexity of the local postage stamp problem

2001-12-22

arxiv.org/abs/math/0112257v1

Mathematics

Number Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The computational complexity of the local postage stamp problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The computational complexity of the local postage stamp problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The computational complexity of the local postage stamp problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-454797