Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Postage stamp problem
open-in-new
<h2 id="mathematical-definition">Mathematical definition</h2> <p>Mathematically, the problem can be formulated as follows: </p> Given an integer <i>m</i> and a set <i>V</i> of positive integers, find the smallest integer <i>z</i> that cannot be written as the sum <i>v</i>1 + <i>v</i>2 + ··· + <i>v</i><i>k</i> of some number <i>k</i> ≤ <i>m</i> of (not necessarily distinct) elements of <i>V</i>. <h2 id="complexity">Complexity</h2> <p>This problem can be solved by <a href="/facts/Brute_force_search/YU2fzBIt">brute force search</a> or <a href="/facts/Backtracking/Jm9vDUk8">backtracking</a> with maximum time proportional to |<i>V</i> |<i>m</i>, where |<i>V</i> | is the number of distinct stamp values allowed. Therefore, if the capacity of the envelope <i>m</i> is fixed, it is a <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> problem. If the capacity <i>m</i> is arbitrary, the problem is known to be <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a>.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Coin_problem/e5fTw9Yl">Coin problem</a></li> <li><a href="/facts/Knapsack_problem/HMIdVJH5">Knapsack problem</a></li> <li><a href="/facts/Subset_sum_problem/Guvrwy0L">Subset sum problem</a></li></ul> <h2 id="external-links">External links</h2> <ul><li>Lunnon, W. F. (1969). <a href="https://doi.org/10.1093%2Fcomjnl%2F12.4.377">"A postage stamp problem"</a>. <i>Comput. J</i>. 12 (4): 377–380. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1093%2Fcomjnl%2F12.4.377">10.1093/comjnl/12.4.377</a>.</li> <li>Alter, R.; Barnett, J. A. (1980). "A postage stamp problem". <i>Amer. Math. Monthly</i>. 87 (3): 206–210. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2321610">10.2307/2321610</a>. <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2321610">2321610</a>.</li> <li>Graham, R. L.; Sloane, N. J. A. (1980). "On additive bases and harmonious graphs". <i>SIAM J. Algebr. Discrete Methods</i>. 1 (4): 382–404. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.70.5521">10.1.1.70.5521</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F0601045">10.1137/0601045</a>.</li> <li>Challis, M. F. (1993). <a href="https://doi.org/10.1093%2Fcomjnl%2F36.2.117">"Two new techniques for computing extremal <i>h</i>-bases <i>A</i><i>k</i>"</a>. <i>Comput. J</i>. 36 (2): 117–126. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1093%2Fcomjnl%2F36.2.117">10.1093/comjnl/36.2.117</a>.</li> <li>Kohonen, J.; Corander, J. (2013). "Addition chains meet postage stamps: reducing the number of multiplications". <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1310.7090">1310.7090</a> [<a href="https://arxiv.org/archive/math.NT">math.NT</a>].</li> <li>Kohonen, Jukka (2014). "A meet-in-the-middle algorithm for finding extremal restricted additive 2-bases". <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1403.5945">1403.5945</a> [<a href="https://arxiv.org/archive/math.NT">math.NT</a>].</li> <li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a> <a href="https://mathworld.wolfram.com/PostageStampProblem.html">"Postage Stamp Problem"</a>. <i><a href="/facts/MathWorld/yc1jodbq">MathWorld</a></i>.</li> <li>OEIS <a href="https://oeis.org/A001212">sequence A001212 (Solution to the postage stamp problem with <i>n</i> denominations and 2 stamps)</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>"Art of Problem Solving". <a href="https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem" target="_blank">https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Jeffrey Shallit (2001), The computational complexity of the local postage stamp problem. SIGACT News 33 (1) (March 2002), 90-94. Accessed on 2009-12-30. <a href="https://arxiv.org/abs/math.NT/0112257" target="_blank">https://arxiv.org/abs/math.NT/0112257</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Jeffrey Shallit (2001), The computational complexity of the local postage stamp problem. SIGACT News 33 (1) (March 2002), 90-94. Accessed on 2009-12-30. <a href="https://arxiv.org/abs/math.NT/0112257" target="_blank">https://arxiv.org/abs/math.NT/0112257</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> </ol>