3sum

Encyclopedia : 3 : 3S : 3SU : 3sum

In computational complexity theory, a problem is called 3sum-hard if solving it in subquadratic time implies a subquadratic-time algorithm for the following problem:

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, but matching lower bounds are only known in very specialized models of computation.

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.

References

[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.

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.