Hacker News Reader

If anyone is interested in the problem in general, it is equivalent to finding solutions to a Diophantine equation. http://en.wikipedia.org/wiki/Diophantine_equation

View on HN

It is not, because it is a single linear equality and all variables are >= 0. This is not just nitpicking: solving Diophantine problems is in general undecidable, but this problem can be solved in pseudo-polynomial time (linear in the sum of all coefficients)

The study of solutions to equations only in the positive integers, or other subsets of integers also falls under Diophantine equations, as far as I know.

Subset sum problems are obviously decidable since the number of values that must be tried to find a solution is finite. However, subset sum is NP complete even when restricted to positive integers [Garey and Johnson, p223] so there is no polynomial time algorithm.

It is NP-complete in the weak sense: the reduction from, say, CNF-SAT, introduces very large coefficients (in the order of 2^n). The pseudo-polynomial algorithm has complexity linear in the magnitude of the coefficients, not in the size of their binary representation (hence pseudo). If the coefficients are small, that algorithm is efficient. See: http://en.wikipedia.org/wiki/Pseudo-polynomial_time

Reply on news.ycombinator.com