<p>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. </p>

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

<p>This will work whether $\{a_i\}$ is a set or a multiset.</p>

<p><em>Informal Proof</em></p>

<p>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\}$).</p>

<p>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).</p>

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

<p>$\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}$</p>

<p>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}$).</p>

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

CC BY-SA 3.0
2016-02-06T20:47:50.967Z
why the minus? the op asked for a proof that the answer is always yes.
Michael Christoff
CC BY-SA 3.0
2016-02-06T20:50:25.860Z
Is there an error in the (informal) proof?  Please clarify what your issue is with this answer.
Michael Christoff
CC BY-SA 3.0
2016-02-06T21:56:07.807Z
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.
Michael Christoff
CC BY-SA 3.0
2016-02-06T20:37:20.007Z
2016-02-07T09:47:33.147Z
2016-02-07T09:47:33.147Z
Michael Christoff
<p>I need to prove that <strong>decision</strong> problem:</p>

<p>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\}] $?</p>

<p>is <strong>NP</strong>-hard.</p>

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

CC BY-SA 3.0
2016-02-04T01:53:27.437Z
This is not NP-hard because the answer is always yes.
Rosetta
CC BY-SA 3.0
2016-02-04T01:54:29.117Z
Are you sure about the formulation of the problem? Such a subset always exists...
Boson
CC BY-SA 3.0
2016-02-04T05:12:29.157Z
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?
Alec
<np-hardness><proof-complexity><subset-sum>
NP-completeness of one generalized subset sum problem (target sum belongs to interval)
Alec
# NP-completeness of one generalized subset sum problem (target sum belongs to interval)

(Asked by: username_0 on 2016-02-04)

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?

**Tags:** np-hardness, proof-complexity, subset-sum
> **Comments:**
> **username_1**: This is not NP-hard because the answer is always yes.  
> **username_2**: Are you sure about the formulation of the problem? Such a subset always exists...  
> **username_0**: 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?  

---

## 1 answers

### Answer by username_3 on 2016-02-06. Score: 0 | Accepted answer

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}\}$.

> **Comments:**
> **username_3**: why the minus? the op asked for a proof that the answer is always yes.  
> **username_3**: Is there an error in the (informal) proof?  Please clarify what your issue is with this answer.  
> **username_3**: 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.  

---

