Separated 3Sum versus 3Sum problem

Question

Does it matter in the 3Sum problem if the numbers to be summed belong to the same set or to distinct sets?

Let's define

• the problem "$k$-Sum" as follows: given a single finite set of integers $X\subset N$ of size $n$, decide if there exists $k$ integers $x_1,\ldots,x_k\in X$ such that their sum $\sum_{i=1}^k x_i$ is null; and
• the problem "Separated $k$-Sum" as follows: given $k$ finite sets of integers $X_1,\ldots,X_k\subset N$ of respective sizes $n_1,\ldots,n_k\in[1..n]\subset N$, decide if there exist a vector $(x_1,\ldots,x_k)\in X_1\times\ldots\times X_k$ such that their sum $\sum_{i=1}^k x_i$ is null.

I was assuming that those two problems were equivalent, and I was using the second one as a pedagogical example for some parameterization technique (while there is an algorithm running in $O(n^2)$ for both, the second one can take advantage of variations in the size of the sets to solve the problem much faster, down to $O(n_1 n_3+\sum n_i\lg n_i)$ and $O(n_1 n_2 \lg \frac{n_3}{n_2}+\sum n_i\lg n_i)$).

But I realized today that I did not know how to prove this equivalence, and I might even start to think that they are not.

Answer 1

You can reduce the SEPARATED k-SUM problem to a (k+1)-SUM problem in the following way:

Given $X_1,...,X_n$, let $b$ such that $2^b > \max( abs(X_1) \cup ... \cup \;abs(X_n))$, where $abs(X_i) = \{ |x| \mid x \in X_i \}$, and let $c$ such that $2^c > k 2^b$

For $i = 1,...,k$ build $Y_i = \{ 2^{c+ki} + 2^{b} + x_j \mid x_j \in X_i \}$;
let $u = - \sum_{i=1}^k 2^{c+ki} -k2^b$

Build an equivalent (k+1)-SUM problem picking $X = \{ u \} \cup Y_1 \cup ... \cup Y_k$

Note that every $Y_i$ contains only positive elements.

Informally we require a $k+1$ elements subset $C$ from $X$ whose elements sum to zero. We cannot build a solution only with the negative element $u$; so we must include in $C$ at least one element $y$ from one of the $Y_i$; but the $2^{c+ki}$ "component" of $y$ can be balanced only if $u$ is also included; but including $u$ implies that exactly one of the elements of each $Y_i$ is included (the $- \sum_{i=1}^k 2^{c+ki}$ component of $u$ allows to keep the separation between the elements of the original $X_i$). But we also have $\sum_{j=1}^k (2^b + x_j) = k2^b$ and this implies that the original $x_j$s (coming from distinct $X_i$s as seen above) sum to zero.