0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ I assume you want the absolute value of prod(B) - prod(C)? Otherwise (at least for positive integers) it's trivial. $\endgroup$
    – Harrison Brown
    Commented Dec 2, 2009 at 1:31
  • $\begingroup$ You are right. I knew I missed something when writing down the problem.. Thanks $\endgroup$
    – Jernej
    Commented Dec 2, 2009 at 1:39

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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). $\endgroup$
    – Ryan Williams
    Commented Feb 21, 2010 at 6:45
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Commented Dec 2, 2009 at 4:51
  • $\begingroup$ makes me wonder if a randomized fingerprinting strategy might work. $\endgroup$
    – Suresh Venkat
    Commented Dec 2, 2009 at 17:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .