Complexity of a subset sum variant

Question

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.

Answer 1

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 2

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

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