User:Erel Segal/Reduction

Reduction to set intersection

The 3SUMx3 problem can be reduced to the following set intersection problem:

Given two collections of sets, S and T, find a set from collection S that intersects a set from collection T.

The reduction uses an almost linear hash function.

The hash function maps every element in the three input arrays, X Y and Z, to the range {0,...,R-1}, where R is a certain constant.

Create a collection S based on the elements of X in the following way:

For every $j=0,...,{\sqrt {R}}-1$:

$S_{j}={h(x_{1})-j,...,h(x_{n})-j}$

Create a collection T based on the elements of Y in the following way:

For every $k=0,...,{\sqrt {R}}-1$:

$T_{k}={-h(y_{1})+k{\sqrt {R}},...,-h(y_{n})+k{\sqrt {R}}}$

Any element in the intersection of $S_{j}$ and $T_{k}$ corresponds to an $x\in X$ and a $y\in Y$ such that:

$h(x)-j=-h(y)+k{\sqrt {R}}$

$h(x)+h(y)=j+k{\sqrt {R}}$

The expression $j+k{\sqrt {R}}$ is always in the range 0,...,R-1, which is the range of h. If there is a $z\in Z$ such that $h(z)=j+k{\sqrt {R}}$, then we have:

$h(x)+h(y)=h(z)$

so we have a candidate for a triple having:

$x+y=z$

---

The main loop is (given arrays A, B and C):

For every z in array C:

If check(z, A,B)

Return

Where the check function checks if there are elements x∈A and y∈B such that: x+y=z.

The check function can be implemented using 2SUM; this takes time O(n), and since it is activated for every element of C, the total run time is O(n^2). But with a solver for an intersection problem, we can do better.