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

<p>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].</p>

<p>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.</p>

<h3>References</h3>

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

<p>[MT90] Silvano Martello and Paolo Toth.  <em>Knapsack Problems: Algorithms and Computer Implementations</em>, Wiley, 1990.  <a href="http://www.or.deis.unibo.it/knapsack.html">http://www.or.deis.unibo.it/knapsack.html</a></p>

CC BY-SA 3.0
2011-11-16T01:05:46.257Z
2011-11-16T14:33:33.337Z
2011-11-16T14:33:33.337Z
Tsuyoshi Ito
<p>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).</p>

CC BY-SA 3.0
2011-11-15T22:29:58.600Z
2011-11-15T22:29:58.600Z
domotorp
<p>Just another (perhaps simpler) reduction from Exact Cover by Three Sets (X3C).</p>

<p>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′$?</p>

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

<p>$$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:</p>

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

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

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

<p><img src="https://i.sstatic.net/Y5SJ5.png" alt="enter image description here"></p>

<p>Proof sketch:<br> $(\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.</p>

<p>$(\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}&gt;b$ (leftmost bits in the figure).
Furthermore every $y_i$ must be $&lt; 2^n$ otherwise $a_i y_i \geq 2^n 2^{6qn} \geq (q+1)2^{6qn} &gt; b$.</p>

<p>But if $0 \leq y_j &lt; 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&lt;2^{2in}$ (informally the bits corresponding to elements $x_i$ cannot interfere with each other).</p>

<p>Every bit $2^{2(i-1)n}, i &lt; 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 \}$.</p>

CC BY-SA 3.0
2014-01-30T23:04:43.863Z
2014-01-30T23:04:43.863Z
Marzio De Biasi
<p>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.</p>

CC BY-SA 3.0
2011-11-14T21:33:16.850Z
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.
Jukka Suomela
CC BY-SA 3.0
2011-11-15T00:37:53.523Z
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.
Marcos Villagra
CC BY-SA 3.0
2011-11-15T04:04:26.777Z
@MarcosVillagra: the reduction from SUBSET SUM is not obvious because the solution produced by this problem might not have only 0-1 weights
Suresh Venkat
CC BY-SA 3.0
2011-11-15T18:15:09.943Z
@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.
Stasys
CC BY-SA 3.0
2011-11-15T20:17:10.707Z
$\exists b': \forall b > b' \in \mathbb{N} : \sum_{i=1}^{n}x_{i}a_{i}=b$ always has solutions $x_{i} \in \mathbb{N} \cup 0$ when $a_{i} \in \mathbb{N}$. I do not think removing $0$ from possible candidates for $x_{i}$ would change the result. So deciding whether there is a solution or not depends on $a_{i}$, $b$ and $n$. When $n = 2$, the answer is known if $x_{i}$ takes $0$ as well. Look at Kannan's work on the Frobenius problem. I think it is in Poly. But I am not 100% sure.
v s
CC BY-SA 3.0
2011-11-16T00:01:50.397Z
aah I see that now after looking more closely :-)
Marcos Villagra
CC BY-SA 3.0
2011-11-16T01:44:22.577Z
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$.
Jukka Suomela
<cc.complexity-theory><np-hardness><subset-sum>
Complexity of a subset sum variant
Paul
# Complexity of a subset sum variant

(Asked by: username_0 on 2011-11-14)

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.

**Tags:** cc.complexity-theory, np-hardness, subset-sum
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_3**: @MarcosVillagra: the reduction from SUBSET SUM is not obvious because the solution produced by this problem might not have only 0-1 weights  
> **username_4**: @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.  
> **username_5**: $\exists b': \forall b > b' \in \mathbb{N} : \sum_{i=1}^{n}x_{i}a_{i}=b$ always has solutions $x_{i} \in \mathbb{N} \cup 0$ when $a_{i} \in \mathbb{N}$. I do not think removing $0$ from possible candidates for $x_{i}$ would change the result. So deciding whether there is a solution or not depends on $a_{i}$, $b$ and $n$. When $n = 2$, the answer is known if $x_{i}$ takes $0$ as well. Look at Kannan's work on the Frobenius problem. I think it is in Poly. But I am not 100% sure.  
> **username_2**: aah I see that now after looking more closely :-)  
> **username_1**: 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$.  

---

## 3 answers

### Answer by username_6 on 2011-11-16. Score: 12

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>


---

### Answer by username_7 on 2011-11-15. Score: 7

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).


---

### Answer by username_8 on 2014-01-30. Score: 3

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](https://i.sstatic.net/Y5SJ5.png)

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 \}$.


---

