I need to prove that decision problem:

for a given set of positive integers $a_1, ..., a_n$, does it exist a subset that sums up to a value within interval $[\frac{1}{2}\sum a_i; \frac{1}{2}\sum a_i+max\{a_i\}] $?

is NP-hard.

This looks more general than canonical subset sum problem, though reminds me of a binary knapsack. Thoughts?

  • 4
    $\begingroup$ This is not NP-hard because the answer is always yes. $\endgroup$ – Rosetta Feb 4 '16 at 1:53
  • 1
    $\begingroup$ Are you sure about the formulation of the problem? Such a subset always exists... $\endgroup$ – Boson Feb 4 '16 at 1:54
  • $\begingroup$ Thank you guys. It might be you're right, and I'm using a wrong problem. Do you have a proof that the answer is always yes, then? $\endgroup$ – Alec Feb 4 '16 at 5:12

Current answers to this post explain that the problem always resolves to "yes", but at the time my answer was posted, there was no proof of 'why' this was the case.

The post below attempts to complete the answer by showing 'why' the answer is always "yes".

This will work whether $\{a_i\}$ is a set or a multiset.

Informal Proof

We know that there is at least one subset $C$ of $\{a_i\}$ for which $\sum C \ge \frac{1}{2} \sum {a_i}$ (we just let $C = \{a_i\}$).

Amongst all the subsets whose sum is $\ge \frac{1}{2} \sum {a_i}$, let $\{c_j\}$ be an arbitrary one whose sum is minimal (clearly $\{c_j\}$ exists).

Now assume for contradiction that $\sum{c_j} \gt \frac{1}{2} \sum {a_i} + \max \{a_i\}$. Then we have that

$\sum {c_j} - \max \{{c_j}\} \gt \frac{1}{2} \sum {a_i} + \max\{{a_i}\} - \max\{{c_j}\} \ge \frac{1}{2} \sum {a_i}$

But this contradicts the assumption that $\{c_j\}$ had a minimal sum $\ge \frac{1}{2} \sum {a_i}$ (since $\{c_j\} \setminus \{\max\{c_j\}\}$ has a smaller sum $\ge \frac{1}{2} \sum {a_i}$).

Therefore it must be that $\sum {c_j} \le \frac{1}{2} \sum {a_i} + \max \{{a_i}\}$.

  • $\begingroup$ why the minus? the op asked for a proof that the answer is always yes. $\endgroup$ – Michael Christoff Feb 6 '16 at 20:47
  • $\begingroup$ Is there an error in the (informal) proof? Please clarify what your issue is with this answer. $\endgroup$ – Michael Christoff Feb 6 '16 at 20:50
  • $\begingroup$ I've edited my post to clarify this answer contributes to a full answer to the original question. The first part was answered (e. g. : the answer is always yes), the second part is "why" is it always yes. It is the second part that this post answers. I would hope that people would only downvote an answer based on the merit (or lack thereof) of the answer, and not downvote it due to any perceived lack of merit in the original question. $\endgroup$ – Michael Christoff Feb 6 '16 at 21:56

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