Given a set of integers $S=\{a_1, \dots, a_n\}$ where $a_i > 0$ and $n$ is an even number, we want to find $A \subset S$ so that:

$$ \left| \sum_{a \in A}a - \sum_{b \in S-A}b \right| $$

is minimized. This problem is very well known to be NP-hard. If we add a constraint $|A| = |S-A|$, is the problem is still NP-hard?


Yes, because you can multiply all of the existing numbers in $S$ by $2|S|^2$ and extend $S$ with the numbers $1$ through $|S|$. A minimal solution to the extended problem with the $2|A|=|S|$ constraint will then also be a solution to the original problem without such constraint, just by ignoring what happened to the new integers in it.

If someone gives me a polynomial solver for the constrained problem, I can use this reduction to solve the original problem in polynomial time. Thus, since the original problem is known to be NP-hard, the constrained one is NP-hard too.

For example, $\{100,200,300\}$ without constraint reduces to $\{1,2,3,1800,3600,5400\}$ with constraint. The optimal solution to the latter problem is $\{3,1800,3600\},\{1,2,5400\}$, with a difference of $|5403-5403|=0$. Because this difference is strictly less than $3^2$, the original unconstrained $\{100,200,300\}$ has a solution with difference strictly less than 1.

  • 1
    $\begingroup$ @HenningMakholm: If I'm not wrong, you are converting my problem (say P1) to another problem (say P2) without the constraint. The solution to P2 is quite the same as the solution to P1 (after some conversion). That's a wise conversion. But it doesn't show P1 is NP-hard. To show P1 is NP-hard, you need to reduce a NP-hard problem, to P1. You did the reverse. Furthermore, the output of the algorithm shouldn't be touched (no conversion). $\endgroup$ – Helium Nov 24 '11 at 22:00
  • $\begingroup$ Well, assume you are given an instance of P2, which is the known problem, like $\{100, 200, 300\}$ and asked to partition it (that's the problem without constraint). The optimal partition is obviously $\{100,200\}, \{300\}$. How do you reduce this instance to the constraint version? $\endgroup$ – Helium Nov 24 '11 at 22:11
  • $\begingroup$ @Moshe: Reducing an NP-hard problem to P1 is what I did. The known NP-hard problem is the unconstrained partition problem; I'm reducing that to the constrained one. As for touching the output, NP is always about yes/no problems -- I'm assuming the usual convention for optimization problems that the actual question being asked is "is there a solution with such-and-such or better quality?" So the output from the problem being reduced to is just yes or no, and is unchanged. $\endgroup$ – hmakholm left over Monica Nov 24 '11 at 22:14
  • $\begingroup$ @HenningMakholm: I got it. You're wonderful man :) Actually, your description in the answer was a bit vague, but it's clear now. $\endgroup$ – Helium Nov 24 '11 at 22:30

Garey and Johnson, Computers and Intractability, page 223:

"A3.2 Weighted set problems

"[SP12] Partition

"Instance: Finite set $A$ and a size $s(a)$ in ${\bf Z}^+$ for each $a$ in $A$.

"Question: Is there a subset $A'\subseteq A$ such that $\sum_{a\in A'}s(a)=\sum_{a\in A-A'}s(a)$?

"Reference: [Karp, 1972]. Transformation from 3-dimensional matching (see Section 3.1.5).

"Comment: Remains NP-complete even if we require that $|A'|=|A|/2$ ...."

I'm aware that this is about equality while the original is about minimization. Still, might not be a bad idea to see what's in the book.

  • 3
    $\begingroup$ The statement you quoted alone already implies that the problem in the question is NP-hard. (Exercise: why?) $\endgroup$ – Tsuyoshi Ito Nov 25 '11 at 1:44

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.