6
$\begingroup$

Given integers $a_1, \ldots, a_n, b \in \mathbb{N}$. What is the complexity of the following problem $$ \exists x_1, \ldots, x_n \in \mathbb{N} \text{ such that } a_1x_1 + \ldots a_nx_n = b? $$ I can't find this subset-sum variant in the literature.

$\endgroup$
  • 5
    $\begingroup$ Could you perhaps give us a bit more background? In the present form the question sounds like a homework problem, in which case it would be off-topic here. $\endgroup$ – Jukka Suomela Nov 14 '11 at 21:33
  • $\begingroup$ this is like a subset-sum with integer weights. Since the original subset problem (i.e., the weights are all 1) is NP-complete, then this version is also NP-complete. $\endgroup$ – Marcos Villagra Nov 15 '11 at 0:37
  • 5
    $\begingroup$ @MarcosVillagra: the reduction from SUBSET SUM is not obvious because the solution produced by this problem might not have only 0-1 weights $\endgroup$ – Suresh Venkat Nov 15 '11 at 4:04
  • 2
    $\begingroup$ @Marcos Villagra: Indeed, what is a (simple) reduction of 0-1 subset sum problem to this "multiple subset sum" problem? (The converse reduction is trivial: just take $n$ copies of each $a_i$.) If this is a homework, then it is not a bad one. $\endgroup$ – Stasys Nov 15 '11 at 18:15
  • 2
    $\begingroup$ A spoiler: A very simple way to show the NP-hardness of the usual 0-1 subset sum problem is a reduction from the exact cover problem. Now you can take the usual reduction and tweak it a bit to make sure that any non-0-1 solution is infeasible. In essence, you can first make sure that $\sum_i x_i > m$ is infeasible, and then make sure that $1 < x_i \le m$ is infeasible for each $i$. $\endgroup$ – Jukka Suomela Nov 16 '11 at 1:44
12
$\begingroup$

Here are some references, not a self-contained answer to the question. For self-contained answers, see other people’s answers and comments.

Assuming that symbol ℕ in the question denotes the set of nonnegative integers, your problem is called the feasibility version of the change-making problem. Chapter 5 of Martello and Toth [MT90] states that it is NP-complete, attributing the result to Lueker [Lue75]. I have not checked the report [Lue75].

Even if symbol ℕ in the question denotes the set of positive integers, the problem is still NP-complete because the nonnegative version can be easily reduced to the positive version.

References

[Lue75] G. S. Lueker. Two NP-complete problems in nonnegative integer programming. Report No. 178, Computer Science Laboratory, Princeton University, 1975.

[MT90] Silvano Martello and Paolo Toth. Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990. http://www.or.deis.unibo.it/knapsack.html

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

I think that SUBSET SUM reduces to this problem. Take an instance of subset sum, $a_i$, $b$, and for simplicity suppose every number has $n$ digits (possibly starting with zeros). Now we will make all the numbers much longer. We modify $b$ so that it starts with "n"00001000010000100001... where "n" is the base two representation of n, then it is followed by n zeros, a 1, n zeros, a 1 and so on n times. We also modify each $a_i$ so that it starts with 10000000000000010000.... where the second 1 is at the $in$-th position. We also add the extra numbers, $a_i$' whose beginning is the same as the new $a_i$'s, but then it ends with all zeros (so it contains only two 1's). Now I claim that if $b$ has a integer combination with these new $a_i$, then the coefficient of each of them has to be 0 or 1. This follows from the fact that the sum of their coefficients is $n$, plus the $i$-th 1 in $b$ can only be obtained from $a_i$ or $a_i$', exactly one of them must be used. Also, from this combination we can get back the original (same coeffs) and from the original we can get this (if $a_i$ has coeff 0, then take $a_i$' with coeff 1).

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Just another (perhaps simpler) reduction from Exact Cover by Three Sets (X3C).

Given a set of $3q$ elements $X = \{ x_1,...,x_{3q}\}$ and a collection of 3 elements subsets $C = \{ C_1,...,C_m \}$, does $C$ contain an exact cover for $X$, i.e. a subcollection $C′\subseteq C$, $|C'| = q$, such that every element of $X$ occurs in exactly one member of $C′$?

Reduction: pick $n$ such that $2^n > q$ and transform every subset $C_j = \{x_{i_1}, x_{i_2}, x_{i_3}\}$ into an integer:

$$a_j = 2^{6qn} + 2^{2(i_1-1)n} + 2^{2(i_2-1)n} + 2^{2(i_3-1)n}$$ and set as target sum:

$$b = q 2^{6qn} + 2^{2(3q-1)n} + \ldots + 2^{2n} + 2$$

$X$ has an exact cover if and only if there exist integers $y_1,...,y_{3q}$, $y_j \geq 0$ such that:

$$a_1 y_1 + \ldots + a_{3q} y_{3q} = b\quad (1)$$

enter image description here

Proof sketch:
$(\Rightarrow)$ It is easy to see that, by construction, if an exact cover $C' = \{ C_{j_1},...,C_{j_q} \}$ exists we can set $y_j = 1$ if $C_j \in C'$, $y_j = 0$ if $C_j \notin C'$, and equation $(1)$ holds.

$(\Leftarrow)$ Suppose that $(1)$ holds. Then at most $q$ from the $y_j$s can be different from $0$, otherwise the sum is greater than $(q+1)2^{6qn}>b$ (leftmost bits in the figure). Furthermore every $y_i$ must be $< 2^n$ otherwise $a_i y_i \geq 2^n 2^{6qn} \geq (q+1)2^{6qn} > b$.

But if $0 \leq y_j < 2^n$, the bit at position $2(i-1)n$ in $a_j$ corresponding to element $x_i$ of $X$ cannot be shifted to the left by the multiplication and "reach the position" $2(i-1)+n$, so even if $q$ of them are summed, they cannot reach and alter the bit $2in$ which correspond to the element $x_{i+1}$: $2^{2(i-1)n}y_jq<2^{2in}$ (informally the bits corresponding to elements $x_i$ cannot interfere with each other).

Every bit $2^{2(i-1)n}, i < 3q$ of $b$ must be "generated" by exactly one of the $a_j$, so $0 \leq y_j \leq 1$ and the $y_j \neq 0$ identify an exact cover of $X$: $C' = \{ C_j \mid y_j \neq 0 \}$.

| cite | improve this answer | |
$\endgroup$

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.