# Paritioning a set of numbers A into two sets B,C so that abs(prod(B) - prod(C)) is minimal

Let A = $\{a_1,...,a_n\}$ be a set of numbers. We can assume all elements of A are integers.

Is there any efficient way to partition A into two sets B = $\{b_1,...,b_k\}$ and C = $\{c_1,...,c_l\}$ such that $|(b_1...b_k) - (c_1...c_l)|$ is minimal?

Is the problem anything easier if we let A be a set of strictly positive integers? What if we only let prime numbers?

-
I assume you want the absolute value of prod(B) - prod(C)? Otherwise (at least for positive integers) it's trivial. –  Harrison Brown Dec 2 '09 at 1:31
You are right. I knew I missed something when writing down the problem.. Thanks –  Jernej Dec 2 '09 at 1:39

I suspect that it's NP-hard even to check whether you can get prod(B) - prod(C) = 0, although there's a problem with the obvious argument that I don't know off the top of my head how to fix.

"Reduction" from subset sum: If you have a set S of integers, replace each integer $k \in S$ with $2^k$. Then this new set can be partitioned into two parts with the same product iff the original set could be partitioned into two parts with the same sum.

The problem is that our new integers are exponentially large compared to the original ones, which means that this isn't actually allowed as a reduction. But I think it's morally correct, since the hardness of subset sum is controlled by the size of the set rather than the lengths of the elements.

-
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). –  Ryan Williams Feb 21 '10 at 6:45