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

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

<p>$Q$: $a_1 x_1 + \dots + a_n x_n = b$.</p>

<p>Let's define $Q(P)$ to be the constraint</p>

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

<p>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.</p>

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

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

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

<p>Lemma 4: $A(M_1 M_2) = A(M_1) \cap A(M_2)$.</p>

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

<p>One can show that $|P| &lt; \log A$, and also $P_m &lt; O(\log A)$.</p>

<p>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.</p>

<p>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.</p>

<p>In <a href="http://arxiv.org/abs/1104.1479" rel="nofollow">http://arxiv.org/abs/1104.1479</a>, I used a very similar idea to encode ILP-program (PB-constraints) into SAT.</p>

<p>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.</p>

CC BY-SA 3.0
2011-04-24T02:06:26.833Z
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
CC BY-SA 3.0
2011-04-24T15:57:58.890Z
*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ε
CC BY-SA 3.0
2011-04-24T20:40:59.423Z
@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
CC BY-SA 3.0
2011-04-24T20:45:56.380Z
@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
CC BY-SA 3.0
2011-04-27T18:14:02.003Z
I don't think it can be done. I've tried.
Craig Feinstein
CC BY-SA 3.0
2011-04-28T19:31:28.753Z
@Craig: 
Let D[m][c] represent the number of answer for 
  a_1x_1+...+a_mx_m=c (mod P)

D [1][0]= 1
D [1][a_1 mod P]= 1
D [1][j]= 0 (j<> 0 and j<< a_1 mod P).

D [i][c]= D [i- 1][c]+ D [i- 1][(c- ai) mod P].

D [n][b] is the number of solutions for Q(P).
To compute D[n][b], one needs a memory of size at most n*P. As I said, P< \log A, so n*P is polynomial w.r.t input size.
Amir
CC BY-SA 3.0
2011-04-23T00:51:40.477Z
2011-08-24T06:00:35.470Z
2011-08-24T06:00:35.470Z
Amir
<p>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: <a href="http://en.wikipedia.org/wiki/Subset_sum_problem" rel="nofollow">http://en.wikipedia.org/wiki/Subset_sum_problem</a>) 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.</p>

<p>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?</p>

<p>(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.)</p>

CC BY-SA 3.0
2011-04-22T19:09:02.510Z
“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
CC BY-SA 3.0
2011-04-22T19:15:25.063Z
The algorithm wouldn't list all the solutions modulo each prime. The Dynamic Programming method doesn't do this.
Craig Feinstein
CC BY-SA 3.0
2011-04-22T19:20:56.217Z
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
CC BY-SA 3.0
2011-04-22T19:30:32.640Z
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
CC BY-SA 3.0
2011-04-22T19:32:39.923Z
I erased the last paragraph to avoid confusion.
Craig Feinstein
CC BY-SA 3.0
2011-04-24T15:51:57.007Z
What do "expected" and "average-case" mean?  Over what input distribution?
Jeffε
CC BY-SA 3.0
2011-04-24T23:26:48.103Z
@JeffE, the uniform distribution.
Craig Feinstein
CC BY-SA 3.0
2011-04-27T18:13:16.387Z
I'm now convinced that such an algorithm would be expected to run in exponential-time.
Craig Feinstein
<cc.complexity-theory>
Subset-Sum modulo small primes
Craig Feinstein
# Subset-Sum modulo small primes

(Asked by: username_0 on 2011-04-22)

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.)

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: “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.  
> **username_0**: The algorithm wouldn't list all the solutions modulo each prime. The Dynamic Programming method doesn't do this.  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_0**: I erased the last paragraph to avoid confusion.  
> **username_2**: What do "expected" and "average-case" mean?  Over what input distribution?  
> **username_0**: @JeffE, the uniform distribution.  
> **username_0**: I'm now convinced that such an algorithm would be expected to run in exponential-time.  

---

## 1 answers

### Answer by username_3 on 2011-04-23. Score: 0

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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: *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.  
> **username_3**: @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.  
> **username_3**: @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.  
> **username_0**: I don't think it can be done. I've tried.  
> **username_3**: @Craig:  Let D[m][c] represent the number of answer for    a_1x_1+...+a_mx_m=c (mod P)  D [1][0]= 1 D [1][a_1 mod P]= 1 D [1][j]= 0 (j<> 0 and j<< a_1 mod P).  D [i][c]= D [i- 1][c]+ D [i- 1][(c- ai) mod P].  D [n][b] is the number of solutions for Q(P). To compute D[n][b], one needs a memory of size at most n*P. As I said, P< \log A, so n*P is polynomial w.r.t input size.  

---

