Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Define the subset sum with interval integer target problem (SSIITP) as follows:
SSIITP Input:
SSIITP Output:
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 SSIITP NP-hard?
The problem is solvable in polynomial time and hence it is not $\mathsf{NP}$-hard (unless $\mathsf{P}=\mathsf{NP}$).
Here is a polynomial-time algorithm: assume without loss of generality that $T \ge 1$, that $a_n > 2T$, and that, for $i=1,\dots,n-1$, $a_i \le a_{i+1}$. Moreover, we can also assume that there is no $a_j$ that satisfies $T \le a_j \le 2T$ (since otherwise the answer is trivially "true").
Define $\sigma(j) = \sum_{i=1}^j a_i$. If there is any $j \in \{1,\dots, n\}$ that satisfies $T \le \sigma(j) \le 2T$ then $\{a_1, \dots, a_j\}$ is a feasible solution and the answer is "true".
On the contrary, if for every $j$ you have $\sigma(j) < T$ or $\sigma(j)>2T$, then you can immediately answer "false".
To see that this is indeed the case, define $j^* \ge 1$ as the smallest value of $j$ that satisfies $\sigma(j)>2T$ (notice that $j^*$ always exists since $\sigma(n) \ge a_n > 2T$). We must simultaneously have $\sigma(j^*-1) < T$ and $\sigma(j^*) > 2T$, hence $a_{j^*} = \sigma(j^*) - \sigma(j^*-1) > T$, which implies $a_{j^*} > 2T$.
Clearly, for all $j \ge j^*$ we have $a_j \ge a_{j^*} > 2T$ and hence no solution can possibly contain $a_j$. However, the sum of the elements in any subset of $S \setminus \{a_{j^*}, \dots, a_n\} = \{a_1, \dots, a_{j^*-1}\}$ can be at most $\sigma(j^*-1)<T$. This shows that there is no feasible solution.
