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.

Improve this question
$\endgroup$
4
  • $\begingroup$ I forgot the bold part, which drastically changed the problem. $\endgroup$
    – frafl
    Jun 8, 2013 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, 2013 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, 2013 at 15:06
  • $\begingroup$ Yes I see [...] $\endgroup$
    – user742
    Jun 8, 2013 at 15:08

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\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, 2013 at 14:54
  • $\begingroup$ The edited problem is still NP-complete. $\endgroup$
    – Yuval Filmus
    Jun 8, 2013 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, 2013 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, 2013 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, 2013 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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