Someone on FreeNode/#algos commented as follows: Conversation with cwenner on 11/11/2007 11:53:31 PM: (11:53:31 PM) cwenner: yao_ziyuan: I haven't, and won't, ponder about this much but some minor comments: "either (1) N_n is included, i.e. s_mod_P_i[n-1][(0 - P_i) mod P_i] = (11:53:36 PM) cwenner: true; (i=1..p) " -N_n mod P_i you mean? [for all 1 <= i <= p]. if you carefully choose fairly balanced primes, P_i^n =~ O(2^n), then P_i might not have to be exponential in the input size (some numbers may be much larger than others). If that is the case, your restricted branching is certainly interesting. If you can furthermore bound the probability of branching to at most 0.5 (or certain expressions (11:53:36 PM) cwenner: of n) (alternatively, to backtrack to this point) then the expected number of search steps would not be exponential either (linear at worst), hence with the first criteria it's RP, and you've shown RP=NP. of course, that seems unlikely and i could have erred
On Nov 11, 10:29 pm, Yao Ziyuan <[EMAIL PROTECTED]> wrote: > Problem: There are n integers N_1, N_2, ..., N_n; we wonder if the sum > of some or all of these integers (a subset sum) is 0. > > Solution: > > Suppose > (1) There are p different prime numbers P_1, P_2, ..., P_p; > (2) P_1 * P_2 * ... * P_p > the largest of the absolute values > of all subset sums; > (3) There is a subset sum M satisfying: M mod P_1 = 0; M mod > P_2 = 0; ...; M mod P_p = 0; > Then > M must be 0. > > For each P_i (i=1..p), use dynamic programming to compute the values > of "all subset sums mod P_i" and store them in the arrays s_mod_P_i[n] > [P_i]. For example, for the prime number P_1, we get an dynamic > programming array s_mod_P_1[n][P_1], where s_mod_P_1[i][j] = true > would mean there exists a subset among N_1, N_2, ..., N_i whose sum > mod P_1 equals j. > > With these p arrays s_mod_p_i (i=1..p), we can use search to restore > an M and one of its addition expression in terms of N_1, N_2, ..., > N_n, or prove that M doesn't exist: > > Suppose M exists, and we have an initial condition s_mod_P_i[n][0] = > true; (i=1..p) > > We want to determine whether an addition expression of M includes N_n > as an addend, then > either (1) N_n is included, i.e. s_mod_P_i[n-1][(0 - P_i) mod > P_i] = true; (i=1..p) > or (2) N_n is not included, i.e. s_mod_P_i[n-1][0] = true; > (i=1..p) > or (3) both (1) and (2) are true; > or (4) neither (1) or (2) is true. > > If (4) is true, it means M doesn't exist for the current search path > and we must backtrack; > If (1) or (2) is true (and (3) is not true), it means there is only > one outlet for the current search path and we don't have to branch > out; > > If (3) is true, it means we must branch out 2 branches for the current > search path; > > For (1), (2) or (3), we step forward to determine whether N_(n-1) can > be included in an addition expression of M. > > This search algorithm has a strong branch-cutting condition in (1) and > is supposed to save a lot of time. > > I originally thought this is a dynamic programming algorithm and > thanks to Lin He who pointed out that there is actually a possibility > for (3) and suggested it can still be an efficient search algorithm. > > Regards, > Yao Ziyuan --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
