Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $n$, $k$ and $m_1, \dots, m_k$ be positive integers. Which is the most efficient algorithm to find out whether there are positive integers $a_1, \dots, a_k$ such that $n = \sum_{i=1}^k a_i m_i$?

To make things nontrivial, think of $k$ being in the hundreds, and of $n$ and the $m_i$ having hundreds of decimal digits, each. -- Clearly if we would remove the requirement that the $a_i$ are positive, the Chinese Remainder Theorem would tell us the answer -- but we do require them to be positive.

share|improve this question
2  
MO is intended for topics at the graduate-school level and above. –  Andy Putman Nov 12 '13 at 4:10
13  
I don’t see how this is not at the graduate-school level or above, nevertheless the problem seems to be equivalent to the unbounded subset-sum problem, whose NP-completeness is mentioned in mathoverflow.net/a/144983/12705 . –  Emil Jeřábek Nov 12 '13 at 12:39
3  
The question sounds perfectly legitimate to me (and Emil Jeřábek provided an answer to it -- maybe he wants to post it as an actual answer as opposed to a comment, now that the question is reopened). –  André Henriques Nov 12 '13 at 12:47
2  
Andy, this is an important question related to the works of Sylvester and Frobenius where much was discovered in recent decades. –  Gil Kalai Nov 12 '13 at 13:58
add comment

1 Answer

The problem can be thought of as a coin problem. There are $k$ coins with denominations $m_1,\dots,m_k$ and you want to express an amount $n$ with these coins. As states, the problem is an integer programming question which is NP-complete when $k$ is part of the input. It is in P (with exponential dependence on $k$) when $k$ is fixed by an algorithm by Lenstra.

The problem is closely related the Frobenius/Sylvester coin problem - to find the minimum $n$ so that every larger integer has such a representation. See here and here. A polynomial algorithm when $k$ is bounded was achieved by Ravi Kannan. (The dependence on $k$ is double-exponential.)

These two problems (finding a representation for fixed $n$ and finding the value of $n$ above which a representation always exists) represent the first two levels in Presburger Hierarchy. An important open problem here is to find a P-algorithm for higher order problems in the Presburger Hierarchy.

Of course, another important question is how to solve such questions in practice. I suppose other people can answer that better than me. One method that certainly comes to mind is to consider the linear programming relaxation (i.e. to allow rational $a_i$s) and then apply some rounding and "local" improvement.

The range proposed by the OP where $k$ - (the number of coins) is in the hunderds is interesting. I don't know if current algorithms can scratch this value.

share|improve this answer
1  
the coin problem is to find the least integer which is not in the submonoid generated by some natural numbers (assuming the gcd is 1). The problem of the OP is the unbounded subset problem, as mentioned by Emil in his comment, and is NP complete. –  Benjamin Steinberg Nov 12 '13 at 14:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.