Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
1  
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
add comment

actually it works the other way around. partition (partition elements into two sets that have equal sum) is polytime if the input sizes are written in unary. If you take this problem and take logs, then the decision problem of determining whether there's a solution where they are equal is solvable via the PARTITION dynamic program, and since the bit sizes are reduced, it's poly time.

there's some nastiness with the log, but I'll handwave and say that you only need enough bits to distinguish two integers, so you can do it with bounded number of bits.

p.s subset sum is poly in the size of the elements btw via the same DP

share|improve this answer
    
Subset sum is exponential in the number of bits of precision of its inputs. And to distinguish between integer products that may themselves be exponential in the input numbers, you need a polynomial number of bits of precision. So this doesn't seem to be good enough. –  David Eppstein Dec 2 '09 at 4:51
    
makes me wonder if a randomized fingerprinting strategy might work. –  Suresh Venkat Dec 2 '09 at 17:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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