- 3SUM
In
computational complexity theory , 3SUM is the following computational problem conjectured to require roughlyquadratic 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(n2) 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 specializedmodels 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 harv|Baran|Demaine|Pǎtraşcu|2008.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 usingFFT .3SUM-hardness
A problem is called 3SUM-hard if solving it in
subquadratic time implies a subquadratic-timealgorithm for 3SUM. The concept of 3SUM-hardness was introduced by harvtxt|Gajentaan|Overmars|1995 in analysis of algorithms incomputational geometry . By now there are a multitude of problems that fall into this category.References
*citation
last1 = Baran | first1 = Ilya
last2 = Demaine | first2 = Erik D. | author2-link = Erik Demaine
last3 = Pǎtraşcu | first3 = Mihai
doi = 10.1007/s00453-007-9036-3
issue = 4
journal = Algorithmica
pages = 584–596
title = Subquadratic algorithms for 3SUM
url = http://erikdemaine.org/papers/3SUM_Algorithmica/
volume = 50
year = 2008.*citation
last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
last2 = Mitchell | first2 = Joseph S. B.
last3 = O'Rourke | first3 = Joseph | author3-link = Joseph O'Rourke (professor)
date = July 2005
publisher = [http://maven.smith.edu/~orourke/TOPP/Welcome.html The Open Problems Project]
title = Problem 11: 3SUM Hard Problems
url = http://cs.smith.edu/~orourke/TOPP/P11.html.*citation
last1 = Gajentaan | first1 = Anka
last2 = Overmars | first2 = Mark H. | author2-link = Mark Overmars
doi = 10.1016/0925-7721(95)00022-2
issue = 3
journal = Computational Geometry: Theory and Applications
pages = 165–185
title = On a class of O(”n”2) problems in computational geometry
volume = 5
year = 1995.*citation
last = King | first = James
title = A survey of 3SUM-hard problems
url = http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf
year = 2004.
Wikimedia Foundation. 2010.