5
$\begingroup$

Motivated by Max-Flow: Detect if a given edge is found in some Min-Cut, I'd like to ask the following questions:

  1. Given a multiset of real numbers $B$, how hard is it to compute the minimal positive difference $\delta_\min$ $$\delta(B_1,B_2)=\left|\sum_{b\in B_1}b-\sum_{b\in B_2}b\right|$$ taken over all partitions $B_1\cup B_2=B$ of $B$ such that $\bf\delta(B_1,B_2)>0$?
  2. How hard is it to find a lower bound $\delta_- >0$ for $\delta_\min$?

Observe that (2) is easy for rational numbers, as you can compute the least common denominator $d$ and every positive difference is a multiple of $\frac{1}{d}$.

Assume that all $b\in B$ are from some subset (closed under addition and symmetric difference) of $\mathbb{R}$ for which we do have a representation by finite strings and all basic operations are performable in at most polynomial time.

$\endgroup$
  • $\begingroup$ I forgot the bold part, which drastically changed the problem. $\endgroup$ – frafl Jun 8 '13 at 14:41
  • $\begingroup$ Do you mean that your problem is not a subset sum because the value of $\delta$ should be bigger than zero? Actually general version of subset sum is exactly same as your problem, or I misunderstood your problem. $\endgroup$ – user742 Jun 8 '13 at 14:59
  • $\begingroup$ @SaeedAmiri: Yes, but I only asked (1) as an introduction to complete the picture. The connection to my answer to the other question is question (2). $\endgroup$ – frafl Jun 8 '13 at 15:06
  • $\begingroup$ Yes I see [...] $\endgroup$ – user742 Jun 8 '13 at 15:08
3
$\begingroup$

Original formulation

(Originally, the OP was interested in the minimum absolute difference rather than the minimum non-zero absolute difference.)

You are asking two different questions. For the first, consider the restricted version in which all numbers are rational, and the decision variant in which the problem is to decide whether your expression is at most some $\delta$. This problem is NP-complete by reduction from PARTITION. (Wlog all numbers are integers, and you can ask whether the difference is at most $1/2$.)

Your other question concerns the decision variant in which the problem is to decide whether your expression is at least some $\delta$. This problem is coNP-complete, and so unless NP=coNP, no nice lower bounds exist (that is, there are no polysize witnesses that the minimal difference is at least $\delta$ which can verified in polytime).

Revision 1

(The question has been changed, and now we are looking for the minimum non-zero absolute difference.)

The problem is NP-complete by reduction from PARTITION. This time assume all numbers are integers, and add to them the additional number $1/3$. Deciding whether the minimal non-zero absolute difference is at most $1/3$ is tantamount to solving PARTITION, and so is NP-complete.

$\endgroup$
  • $\begingroup$ Your answer is very good, but I made a serious blunder in my question, which renders it less interesting and destroys the connection to linked answer. $\endgroup$ – frafl Jun 8 '13 at 14:54
  • $\begingroup$ The edited problem is still NP-complete. $\endgroup$ – Yuval Filmus Jun 8 '13 at 16:43
  • $\begingroup$ How exactly would your reduction for PARTITION to (1) work? If both sets of a solution to PARTITION are of equal size the sum would be still be zero and so not a solution to (1). I think one had to add different (and a lot smaller, e.g. $\leq 1/(2|B|+1)$) numbers to each integer. $\endgroup$ – frafl Jun 8 '13 at 20:32
  • 1
    $\begingroup$ @frafl If the original set were $1,2,3,4$ then the new one is $1,2,3,4,1/3$. You don't add $1/3$ to each number, you add an additional number equal to $1/3$. The number $1/3$ satisfies the crucial inequality $1/3 < 1-1/3$, and that makes the reduction work. $\endgroup$ – Yuval Filmus Jun 8 '13 at 20:40
  • $\begingroup$ Ah, so obvious..., thanks. btw the word "element" instead of "number" would have been good, but "additional" makes it unambiguous as well. $\endgroup$ – frafl Jun 8 '13 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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