MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this community
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.
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.
