Is there an efficient algorithm for WEAK-PARTITION?

Question

Suppose that we are given a list of non-zero integers $(a_1,...,a_n)$ and we want to decide whether there exist $(x_1,...,x_n)$ such that

$x_1a_1 + x_2a_2 + ... + x_na_n = 0,ドル

$x_i$ $\in$ $\{-1,0,1\},ドル with at least one $x_i \neq$ 0.

Note that this is not the same as PARTITION, where the restriction $x_i \in \{-1,1\}$ would give a solution. Of course we should also be aware that with $x_i \in \{0,1\}$ is the NP complete problem SUBSET-SUM. I don't see any obvious way of reducing SUBSET-SUM or PARTITION to this problem. For example, attempting to reduce a 0-1 problem to $\{-1,0,1\}$ problem by appending the list with negative elements appears to accomplish nothing.

The closest problem that I found was described this post, calling the problem WEAK-PARTITION. However, the link that the original poster provided is currently broken.

I would like to know whether there is an efficient (i.e. polynomial time) algorithm known for this problem and whether anyone knows of further references to this problem.

Answer 1

Your problem is NP-complete, as proved by Adi Shamir in his paper On the cryptocomplexity of knapsack systems.

• Kevin: Thanks, Theorem 3 and Lemma 4 are the relevant parts if anyone comes across this.