search

# Equivalence of 3SUM problems

#### Wed, Apr 27, 2016 02:00 CEST

###### Tags:Algorithms

Are different versions of the 3SUM problem equivalent?

## Reducing 3SUMx1 on S with multiple pick to 3SUMx3 on A,B,C

Trivially with $$A=B=C=S$$.

## Reducing 3SUMx1 on S with unique pick to 3SUMx3 on A,B,C

Construct $$t=\Theta(\log n)$$ instances of 3SUMx3 where S is partitioned into $$A,B,C$$ of size $$\frac{n}{3}$$ each uniformly at random.

By construction, no instance has a triple $$a + b + c = 0$$ with $$a = b = s_i$$ or $$b = c = s_i$$ or $$a = c = s_i$$.

If $$s_1 + s_2 + s_3 = 0$$ then, with high probability, at least one of the $$\Theta(\log n)$$ instances has $$s_1 \in A$$, $$s_2 \in B$$, and $$s_3 \in C$$.

The probability that this is not the case is $$(\frac{27-3!}{27})^m$$.

Hence, with $$m = \Theta(\log n)$$, the probability that at least one instance has the triple is $$1 - n^{-\Omega(1)}$$.

## Reducing 3SUMx3 to 3SUMx1 (with multiple or unique pick)

$$10 a + 1, 10 b + 2, 10 c - 3$$

$$a + b + c = 0 \implies 10 a + 1 + 10 b + 2 + 10 c - 3 = 0$$

$$1 + 2 - 3 = 0$$

$$1 + 1 + 1 = 3$$

$$2 + 2 + 2 = 6$$

$$-3 - 3 - 3 = -9$$

$$1 + 1 + 2 = 4$$

$$1 + 2 + 2 = 5$$

$$1 + 1 - 3 = -1$$

$$1 - 3 - 3 = -5$$

$$2 + 2 - 3 = 1$$

$$2 - 3 - 3 = -4$$ 