1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Isn't 1a special case of 3? So in the worst case you cannot solve it faster than 3-SUM? $\endgroup$ – Kaveh Aug 29 '14 at 18:31
  • $\begingroup$ @Kaveh: 1-SUM = Separated 1-SUM, but otherwise k-Sum is not a particular case of Separated k-Sum: if anything, the separation of X into subsets should only make the problem easier in limiting the number of solutions to consider. On the other hand, both have solutions running in time within $O(n^2)$. $\endgroup$ – Jeremy Aug 29 '14 at 20:47
  • 3
    $\begingroup$ @Jeremy: Just pick $X_1 = X_2 = ... = X_k = X$ and you can solve k-SUM using SEPARATED k-SUM. For the opposite direction take a look to my answer. $\endgroup$ – Marzio De Biasi Aug 29 '14 at 20:53
  • 1
    $\begingroup$ Have you checked Gajentaan and Overmars 1995? It is a must-read paper about 3SUM and related problems. $\endgroup$ – Tsuyoshi Ito Aug 30 '14 at 13:53
  • $\begingroup$ @MarzioDeBiasi: how could I miss this? Thanks! $\endgroup$ – Jeremy Aug 31 '14 at 1:14
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @Mario De Biasi: Should one correct s (not defined) into v (defined and unused) in the defintion of $X$? $\endgroup$ – Jeremy Aug 29 '14 at 21:02
  • $\begingroup$ And also "But also the 2b component" should be "But also the 2^b component" $\endgroup$ – Jeremy Aug 29 '14 at 21:03
  • $\begingroup$ @Jeremy: answer written too fast :-S, you're right; I fixed them ($v$ is used in the last part of the informal proof). Also note that the quantity $2^{c+ki}$ could be adjusted/optimized (e.g. replacing it with $2^{c+d(i-1)}$ where $d$ is the smaller integer such that $2^d > k$). $\endgroup$ – Marzio De Biasi Aug 29 '14 at 21:24
  • $\begingroup$ @Jeremy: reading my answer again (?) I see that in fact you can use $\{u+v\}$ instead of $\{u,v\}$ ... in other words you can reduce the SEPARATED k-SUM to (k+1)-SUM $\endgroup$ – Marzio De Biasi Aug 29 '14 at 21:30
  • $\begingroup$ @mario: Gajentaan and Overmars 1995 showed that 3SUM = Separated 3SUM. I will have to study more their proof, but maybe one can show that kSUM = Separated kSUM? $\endgroup$ – Jeremy Sep 1 '14 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.