3
$\begingroup$

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?

$\endgroup$
9
  • 1
    $\begingroup$ Where did you encounter this problem? Could you provide a reference? $\endgroup$ Sep 3 '21 at 5:10
  • $\begingroup$ Hint: Consider different cases for the largest element in the set. Example case (the easiest): Suppose the largest element has size in the range $\lceil\frac{1}{2}T\rceil \dots \lfloor\frac{3}{4}T\rfloor$. $\endgroup$ Sep 3 '21 at 7:29
  • 1
    $\begingroup$ @InuyashaYagami I came to this problem while trying to prove the hardness of another problem. I didn't find any reference to this problem at any place. $\endgroup$ Sep 3 '21 at 8:06
  • $\begingroup$ @j_random_hacker If the largest element has size in the range of the target interval, the answer is always yes. What about other cases? Is the general case NP-hard? $\endgroup$ Sep 3 '21 at 8:10
  • 1
    $\begingroup$ @InuyashaYagami Both cases (positive and mixed integers) are interesting to me. $\endgroup$ Sep 3 '21 at 8:31
4
$\begingroup$

With positive integers only

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

  1. $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.
  2. $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.
  3. $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.
  4. $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.

$\endgroup$
4
  • $\begingroup$ Great, thanks for the answer. I managed to reduce the interval target to $\lceil \frac{1}{2} T \rceil .. \lfloor \frac{5}{8} T \rfloor$. I adapted the cases to the new interval, switching the $\frac{3}{4} T$ to $\frac{5}{8}T$. Cases 1, 2, and 3 are easy, exactly like you explained. For the case 4, when $a_m \in [0, \lceil \frac{3}{8}T \rceil)$, I can't reach the same contradiction since the element $a_i$ must be strictly above $\lceil \frac{1}{8}T \rceil$, but this is not enough to contradict the maximality of $a_m$. Does changing the target interval make the problem NP-hard? $\endgroup$ Sep 3 '21 at 12:30
  • 2
    $\begingroup$ You're welcome! Yes, it's possible that the problem becomes NP-hard for some target interval sizes. It's also possible that in this new case specifically, it remains poly-time-solvable, but showing this requires a stronger argument. E.g., it would suffice to show that there is some constant $k$ independent of $p$ such that all instances having $p \ge k$ elements are trivially YES-instances (because there must be "enough small elements"). $\endgroup$ Sep 3 '21 at 13:44
  • $\begingroup$ Ok, thanks for the hint. Which NP-hard problem could I use to try to prove that this new case (with target interval $\lceil \frac{1}{2} T \rceil .. \lfloor \frac{5}{8} T \rfloor$) is NP-hard? $\endgroup$ Sep 3 '21 at 14:39
  • 2
    $\begingroup$ I would definitely start by trying to reduce ordinary Subset Sum to the problem. Several quite constrained variants are already equivalent to it; I suggest googling around and looking at how they are proved. A transformation that is sometimes useful for constraining solutions is multiplying all inputs by a constant (e.g., if you double all input elements, add in some odd-valued elements and force the target range to be a single odd number, at least one of the odd-valued elements must be chosen). $\endgroup$ Sep 3 '21 at 14:47
3
$\begingroup$

With negative integers permitted

Unlike the SSITP problem restricted to positive integers, when negative integers are permitted the problem is NP-complete. I'll show this by reduction from ordinary Subset Sum (SS). The idea of the reduction is to append extra numbers that force the target range to collapse to the single value 3, and to mess with the numbers in the original input so that the odd target value can only be achieved in very constrained ways that correspond straightforwardly to solutions to the original instance. I needed to add the "crumb" elements to make sure that when we have an SSITP solution, at least one element from the original SS instance must be chosen.

Reduction

Given an instance $X = b_1, \dots, b_n$ of SS, where each $b_i$ can be positive, negative or zero and the target value is zero, we construct an instance $Y = a_1, \dots, a_p$ of SSITP as follows:

  • Set $a_i = 8nb_i + 4$ for all $i \in [n]$. Call these elements the meat, $M$.
  • Append $a_{n+1} = 2-8nU$, where $U = \sum_i{b_i}$. (I think of this element as "ballast" -- it exists only to weigh the sum down towards zero.)
  • Append $a_{n+2} = 3-4n$. (I think of this element as the "cornerstone" -- we can show that any solution must contain it.)
  • Finally append $n-1$ copies of 4, and $n-1$ copies of -4, as $a_{n+3}, \dots, a_{3n}$. Call these elements the crumbs, $C$. (So in all there are $p=3n$ elements.)

Appending the extra numbers forces the total $T=\sum_i^p{a_i}$ to be 5. This shrinks the "interval" of allowed values to the single value $\lceil\frac{1}{2}5\rceil = \lfloor\frac{3}{4}5\rfloor = 3$.

$X$ is a YES-instance of SS $\implies$ $Y$ is a YES-instance of SSITP: For each $b_i$ in the solution to $X$, choose $a_i$ for the solution to $Y$. Suppose there are $k \ge 1$ such elements: The sum so far is $8n(0)+4k=4k$. Now choose $n-k$ copies of 4, bringing the sum so far to $4n$. Finally choose $a_{n+2} = 3-4n$, bringing the total to 3.

$Y$ is a YES-instance of SSITP $\implies$ $X$ is a YES-instance of SS: The target is 3, which is odd, so the solution to $Y$ must contain an odd number. The only odd number available is $a_{n+2} = 3-4n$, so it must appear in the solution. If $a_{n+1} = 2-8nU$ also appears in the solution, then the remaining elements must sum to $3-(3-4n)-(2-8nU) = 4n+8nU-2$ -- but that number is not divisible by 4, and all other elements are multiples of 4, so this is not possible. Therefore the solution to $Y$ contains only $a_{n+2} = 3-4n$, in addition to a subset of $M\cup C$ that sums to $4n$. Observe that this subset must contain at least one meat element, since the greatest sum achievable using only crumbs is $4(n-1)$.

We want the $8nb_i$-terms within the chosen subset of $k \ge 1$ meat elements to sum to zero, so that we can simply choose the corresponding elements $a_i$ to get a solution to $X$. Suppose towards contradiction that they do not: Then either the chosen subset of $M$ sums to at least $8n + 4k \ge 8n$, or it sums to at most $-8n+4k \le -4n$. In the first case, to reach a total of $4n$ from $8n$ we must use crumbs to subtract $4n$, but the most we can subtract this way is $4(n-1)$, so this case cannot happen. Similarly, in the second case, to reach a total of $4n$ from $-4n$ we must use crumbs to add $8n$, but the most we can add this way is $4(n-1)$, so this case cannot happen either. Therefore the only way that the chosen subset of $M\cup C$ can sum to $4n$ is if the $8nb_i$-terms of the chosen subset of $M$ sum to zero, as desired. Then we can simply choose corresponding elements $a_i$ to get a solution to $X$.

We have established that a YES solution to the constructed instance of SSITP $\iff$ the original SS instance has a YES solution, so a NO solution to the constructed instance of SSITP $\iff$ the original SS instance has a NO solution. The construction is clearly polynomial-time, so SSITP with negative integers permitted is NP-complete.

$\endgroup$
2
  • $\begingroup$ Very nice! Thank you very much! This is very helpful. There is a lot to learn from your answer. That could help me find a reduction for the SSITP with positive integers only, and target interval $\lceil \frac{1}{2}T \rceil .. \lfloor \frac{5}{8}T \rfloor$. $\endgroup$ Sep 4 '21 at 22:51
  • $\begingroup$ You're welcome :) Yes, I would hope that similar kinds of tricks could be employed to show that some positive-only problem variants are hard (if indeed they are!) For this proof, I started without the "crumbs", and got quite far before realising that it was possible for a YES-instance of SSITP to correspond to choosing no elements in the original SS instance, which of course is forbidden. I'm also lucky that you wrote "multiset" rather than "set" in the problem definition, since it would not be possible to have many identical crumb elements with the latter. $\endgroup$ Sep 5 '21 at 1:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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