# Subset-Sum modulo small primes

I was thinking about the strategy of solving Subset-Sum (with a set of size n and integers having n bits each) by using Dynamic Programming (described here: http://en.wikipedia.org/wiki/Subset_sum_problem) modulo n small primes, 2,3,5,7,11,...,nth prime. The algorithm would then compute the intersection of the sets of answers modulo each prime. The solution to Subset-Sum would be in the intersection, and probably no wrong answers would be in the intersection.

Would such an algorithm be expected to run in polynomial-time? In other words, is it possible to compute the intersection of the sets of answers modulo each prime efficiently in the average case scenario?

(Note that in the worst-case scenario, this algorithm would have exponential running-time, since the intersection may have exponential size. I'm only talking about the average-case scenario here when there are only few or no solutions. This question has nothing to do with the P vs. NP problem.)

• “Would such an algorithm be expected to run in polynomial-time?” No, because for a fixed prime, it takes exponential time to list up all the solutions. Probably proving P=NP will be a little more challenging. – Tsuyoshi Ito Apr 22 '11 at 19:09
• The algorithm wouldn't list all the solutions modulo each prime. The Dynamic Programming method doesn't do this. – Craig Feinstein Apr 22 '11 at 19:15
• You are right in that the usual DP-based pseudo-polynomial-time algorithm cannot list up all the solutions. Your algorithm requires listing all the solutions for each prime, as you did in the last paragraph of your question. Therefore, either your algorithm takes exponential time or your algorithm does not work, depending on whether you list up all the solutions for each prime or not. – Tsuyoshi Ito Apr 22 '11 at 19:20
• Even though the DP-based algorithm doesn't explicitly list all the solutions, these solutions are still encoded in each step of the algorithm. From this, it may still be possible to compute the intersection in average-case polynomial-time. Also, the last paragraph of my question is not explaining how the algorithm works, only what it does. – Craig Feinstein Apr 22 '11 at 19:30
• What do "expected" and "average-case" mean? Over what input distribution? – Jeffε Apr 24 '11 at 15:51

I have been working the exact same idea for a while. What Tsuyoshi Ito said is not necessary correct!

Solving the subset-sum problem is the same as solving the following 0-1 Integer linear program

$Q$: $a_1 x_1 + \dots + a_n x_n = b$.

Let's define $Q(P)$ to be the constraint

$Q(M)$: $a_1 x_1 + \dots + a_n x_n \equiv b\ (\text{mod }M)$.

Let $A$ be the set of solutions to $Q$ and $A(M)$ be the set of solutions to $Q(P)$. Correctness of the following lemmas is easy to verify.

Lemma 1: If M is large enough, we have $A(M) = A$.

Lemma 2: We can safely assume all $a_i$'s are positive integers.

Lemma 3: If all coefficients are positive, for every $M > \sum a_i$, we have $A(M) = A$.

Lemma 4: $A(M_1 M_2) = A(M_1) \cap A(M_2)$.

Now, let $P = \{2, 3, \dots, P_m\}$ be the set of primes such that $\prod_{p \in P}\ p > A = \sum a_i$.

One can show that $|P| < \log A$, and also $P_m < O(\log A)$.

So then, computing the DP array of $Q$ ($P_i$) can be done in polynomial time w.r.t input size. And also, it is easy to compute $|A(P_i)|$ in polytime w.r.t. input size.

The next step is to find a $P_i$ s.t. $|A(P_i)|$ is minimal. If the number of solutions in $A(P_i)$ is small (polynomial in size of input), the one can enumerate all such solutions and check if any of them satisfies $Q$ or not.

In http://arxiv.org/abs/1104.1479, I used a very similar idea to encode ILP-program (PB-constraints) into SAT.

It can be observed that there are many subset-sum instances which can be solved in polynomial time, w.r.t. input using the above approach.

• But Tsuyoshi Ito was correct that the number of solutions in A(P_i) would be exponential for small P_i. Do you know how to compute the intersection of A(P_i) over 1<i<n in polynomial-time? I think it can be done but haven't coded this yet - the DP array of each Q(P_i) should be able to guide us in this direction. I'll try this. – Craig Feinstein Apr 24 '11 at 2:06
• computing the DP array of Q (P_i) can be done in polynomial time w.r.t input size. How? The modulus P_i is not a constant; it could be as large as A, the sum of the input values. So the standard memoization table could have size Ω(A), which is exponential in the number of input bits. – Jeffε Apr 24 '11 at 15:57
• @Craig: I said "What Tsuyoshi Ito said is not necessary correct", meaning that there are cases for which there are very few answers there. My initial approach, as I described above, is to count the number of answers to each Q(P_i) and then, select the smallest of them. By this way, one does not need to find the intersection of all A(P_i) or even list them. – Amir Apr 24 '11 at 20:40
• @JeffE: No. As I stated above, P_m is O(\log A). If you are interested, I can given you a proof sketch for that. – Amir Apr 24 '11 at 20:45
• I don't think it can be done. I've tried. – Craig Feinstein Apr 27 '11 at 18:14