Subset Sum With Interval Target

Define the subset sum with interval target problem (SSITP) as follows:

SSITP Input:

A multiset $S = \{a_1, …, a_p\}$ of positive integers $a_i$ such that $\sum_{a_i \in S} a_i = T$.

SSITP Output:

• True, if there is a subset $S’ \subseteq S$ such that $\sum_{x \in S'} x \in \lceil \frac{1}{2}T \rceil .. \lfloor \frac{3}{4}T \rfloor$.

• False, otherwise.

Where $a .. b$, for two integers $a$ and $b$, is an integer interval including every integer between $a$ and $b$: $a, a+1, a+2, \dots, b-2, b-1, b$.

Is SSITP NP-hard?

Does introducing negative integers in the multiset $S$ change the hardness of the SSITP?

With positive integers only

Consider the largest element $a_m$ in the input. We have the following cases:

• $a_m \in [\lceil\frac{1}{2}T\rceil, \lfloor\frac{3}{4}T\rfloor]$. We can simply choose $\{a_m\}$ and we are done: the answer is YES.

• $a_m \in (\lfloor\frac{3}{4}T\rfloor, T]$. Any subset that includes $a_m$ is too large, and taking all the remaining elements together is strictly less than $T-\lfloor\frac{3}{4}T\rfloor = \lceil\frac{1}{4}T\rceil$, which is too small: the answer is NO.

• $a_m \in [\lceil\frac{1}{4}T\rceil, \lceil\frac{1}{2}T\rceil)$. We can always take all elements except $a_m$ and get a subset in the correct range: the answer is YES.

• $a_m \in [0, \lceil\frac{1}{4}T\rceil)$. We can choose elements in any order, stopping as soon as we get a total in the desired range. To see that this must occur, note that the elements sum to strictly more than $\lfloor\frac{3}{4}T\rfloor$, and for it not to occur would require that choosing some element $a_i$ takes the sum of elements chosen so far from strictly below $\lceil\frac{1}{2}T\rceil$ to strictly above $\lfloor\frac{3}{4}T\rfloor$ -- but such an element would have to be at least $\lfloor\frac{3}{4}T\rfloor - \lceil\frac{1}{2}T\rceil + 2 = \lfloor\frac{3}{4}T\rfloor + \lfloor-\frac{1}{2}T\rfloor + 2 \ge \lfloor\frac{1}{4}T\rfloor + 1 \ge \lceil\frac{1}{4}T\rceil > a_m$, which contradicts the maximality of $a_m$. So the desired range must be hit, and the answer is YES.

The solution can always be found in linear time by checking all cases, so the problem cannot be NP-complete unless P=NP.

StackExchange Computer Science Q#143632, answer score: 4