Timeline for Paritioning a set of numbers A into two sets B,C so that abs(prod(B) - prod(C)) is minimal
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 3, 2012 at 12:31 | vote | accept | Jernej | ||
| Feb 21, 2010 at 6:45 | comment | added | Ryan Williams | Here's how to fix it (sorry for being 2 months late but I just saw the question). There's a randomized reduction that works based on your observation. Let M be the absolute value of the largest number in S, and note all numbers of S are represented in O(log M) bits. Pick a random prime p in the interval [2, 2^n n^2 log(M)]. Now replace each k in S with 2^k mod p. It is easy to see the above is a polytime reduction. It works whp because the total number of subsets is at most 2^n, and the probability that some S has a solution (when it really shouldn't) can be seen to be at most 1/(n 2^n). | |
| Dec 2, 2009 at 1:44 | history | answered | Harrison Brown | CC BY-SA 2.5 |