-4
$\begingroup$

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

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ “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. $\endgroup$
    – Tsuyoshi Ito
    Apr 22, 2011 at 19:09
  • $\begingroup$ The algorithm wouldn't list all the solutions modulo each prime. The Dynamic Programming method doesn't do this. $\endgroup$
    – Craig Feinstein
    Apr 22, 2011 at 19:15
  • 3
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Apr 22, 2011 at 19:20
  • $\begingroup$ 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. $\endgroup$
    – Craig Feinstein
    Apr 22, 2011 at 19:30
  • 1
    $\begingroup$ What do "expected" and "average-case" mean? Over what input distribution? $\endgroup$
    – Jeffε
    Apr 24, 2011 at 15:51

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Craig Feinstein
    Apr 24, 2011 at 2:06
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Apr 24, 2011 at 15:57
  • 1
    $\begingroup$ @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. $\endgroup$
    – Amir
    Apr 24, 2011 at 20:40
  • $\begingroup$ @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. $\endgroup$
    – Amir
    Apr 24, 2011 at 20:45
  • $\begingroup$ I don't think it can be done. I've tried. $\endgroup$
    – Craig Feinstein
    Apr 27, 2011 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.