Is subset sum problem with multiplicities NP-complete? To be specific, the problem is formalized as follows.

Given a set of integers $\{a_1,\ldots,a_n\}$, determine whether there exist non-negative integers $x_1,\ldots,x_n$ such that $a_1x_1+\cdots+a_nx_n=0$ and at least one of $x_1,\ldots,x_n$ is positive. 

Note this is not a duplicate of this problem. In that problem, the target sum is given as input, while in our problem, the target sum is fixed to be $0$. 

I tried to follow the idea of the answer to that question to come up with a new reduction, but since a basic idea of that answer is to use big elements as well as big target to prevent an element from being chosen multiple times, while in our problem the target sum is $0$, I failed. 

Related question: Is the following Subset Sum variant NP-complete?
The problem can be solved in polynomial time.

If any of the $a_i$ are zero, then the answer is "yes" (you can set the corresponding $x_i$ to 1, and all other $x_j$ to 0).  So let's assume all of the $a_i$ are non-zero.

If all of the $a_i$ are strictly positive, then the answer is "no" (if $x_i$ is the one that's set to something non-zero, then $x_i&gt;0$ and $a_i&gt;0$, so $a_1 x_1 + \dots + a_n x_n \ge a_i x_i &gt; 0$).  So we can assume at least one of the $a_i$ is strictly negative.

If all of the $a_i$ are strictly negative, then the answer is "no" (if $x_i$ is the one that's set to something non-zero, then $x_i&gt;0$ and $a_i&lt;0$, so $a_1 x_1 + \dots + a_n x_n \le a_i x_i &lt; 0$).  So we can assume at least one of the $a_i$ is strictly negative.

If at least one of the $a_i$ is strictly positive and at least one is strictly negative, say $a_i&gt;0$ and $a_j&lt;0$, then the answer is "yes" (you can take $x_i=-a_j$, $x_j=a_i$, and set all other $x$'s to zero; then $a_1 x_1 + \dots + a_n x_n = a_i x_i + a_j x_j = -a_i a_j + a_i a_j = 0$).

These cases cover all the possibilities: at least one of the above cases must hold.  So, we obtain a polynomial-time algorithm for the original problem.

Credit: I got the key idea from Discrete lizard.