Subset-sum prob. (congruence variation)

Question

I'm wondering about the NP-completeness of a variation of the Subset-sub problem:

Subset-sum problem: Given a set of integers and an integer s, does any non-empty subset sum to s?

This problem is known to be in NP and be NP-complete. Now consider the variation:

Subset-sum problem (congruence variation): Given two integers s and m and a set of integers modulo m, does any non-empty subset sum to s mod m?

(i.e., all the numbers in the set are modulo m and the expected sum s is also in mod m).

I'm wondering if this problem has been studied before? (Would like to know if it is NP-complete or not). Does anyone know if there is any paper or similar variation of the Subset-sum problem? Thank you!

Answer 1

Yes, this problem is also NP-complete. Since normal subset sum is NP complete, there is a reduction of some other NP-complete problem to subset sum.

The same reduction will also work to prove that modular subset sum is NP complete, if you can additionally generate a sufficiently large modulus with a size that is polynomial in the input size. The modulus just has to be bigger than the largest number used in the subset sum solution, and then the difference between subset sum and modular subset sum is irrelevant.

For any reduction I can think of, it is easy to generate such a modulus. Remember that it is only the size of the modulus that has to be polynomial in the input size, so, say 100^(N^2) works fine -- it's only 2*(N^2) digits long.