0
$\begingroup$

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

SSIITP Input:

  • A multiset $S = \{a_1, …, a_p\}$ of positive integers $a_i$.
  • An integer $T$.

SSIITP Output:

  • True, if there is a subset $S’ \subseteq S$ such that $\sum_{x \in S'} x \in T .. 2T$.
  • 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 SSIITP NP-hard?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ In English: If there's a term whose value is between T and 2T, then it trivially satisfies the criteria; We can ignore any term whose value is >2T. It can't be part of a solution; If the remaining terms sum to <T there's no solution; Otherwise, we can start with the empty set and arbitrarily add terms to it until arriving at something which is >=T. Since no one term is >=T, it's not possible, by adding a single term, to have the sum jump from <T to >2T (since the new sum is just the old sum plus the new term) $\endgroup$
    – dspyz
    Nov 3, 2021 at 17:34
  • $\begingroup$ @dspyz. Great explanation! A straightforward implementation of the algorithm in my answer requires time $\Theta(n \log n)$, while an implementation of the steps in your comment only requires linear time. (Perhaps the comment can be turned into an answer?) $\endgroup$
    – Steven
    Nov 3, 2021 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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