# 3SUM

In computational geometry 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*?

^{2}) 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 Gajentaan and Overmars [GO95]. By now there is a multitude of problems that falls into this category. (Add REFS)

## 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
^{2}) problems in computational geometry.*Comput. Geom. Theory Appl.*, 5:165-185, 1995.