3SUM

From Wikipedia, the free encyclopedia

In computational complexity theory, 3SUM is the following computational problem conjectured to require roughly quadratic time:

Given a set S of n integers, are there elements a, b, c in S such that a + b + c = 0?

There is a simple algorithm to solve 3SUM in O(n²) time. This is the fastest algorithm known in models that do not decompose the integers into bits, but matching lower bounds are only known in very specialized models of computation.

Slightly faster randomized algorithms are known that exploit computational-model parallelism on a RAM and in the external-memory and cache-oblivious models [BDP05].

When the integers are in the range [0 ... u], 3SUM can be solved in time O(u lg u) by representing S as a bit vector and performing a convolution using FFT.

[edit] 3SUM-hardness

A problem is called 3SUM-hard if solving it in subquadratic time implies a subquadratic-time algorithm for 3SUM. The concept of 3SUM-hardness was introduced by Anka Gajentaan and Mark Overmars [GO95] in analysis of algorithms in computational geometry. By now there is a multitude of problems that falls into this category.

[edit] References

• [BDP05]: Ilya Baran, Erik D. Demaine, and Mihai Pǎtraşcu. Subquadratic Algorithms for 3SUM. [1]
• [DMO04]: Erik D. Demaine, Joseph S. B. Mitchell, and Joseph O'Rourke. The Open Problems Project, Problem 11.
• [GO95]: Anka Gajentaan and Mark H. Overmars. On a class of O(n²) problems in computational geometry. Comput. Geom. Theory Appl., 5:165-185, 1995.