3SUM

3SUM

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(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 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 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 using FFT.

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 harvtxt|Gajentaan|Overmars|1995 in analysis of algorithms in computational 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.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • 3sum — is an Alcopop infused with the energy components caffeine, ginseng, and taurine. The flavored drink is produced by United Brands Company in La Mesa, California. 3SUM is considered an energy drink and a flavored alcoholic beverage. 3SUM is… …   Wikipedia

  • 3SUM — Threesome …   Abbreviations SMS and Internet

  • List of computability and complexity topics — This is a list of computability and complexity topics, by Wikipedia page. Computability theory is the part of the theory of computation that deals with what can be computed, in principle. Computational complexity theory deals with how hard… …   Wikipedia

  • List of mathematics articles (0-9) — NOTOC 0 −0 (number) −1 (number) −40 (number) Σ compact space Ω consistent theory Γ convergence Δ hyperbolic space Ω logic Ε net Ε quadratic form Μ recursive function yllion 0 (number) Ε₀ 0,1 simple lattice 0.999... ( 2, 3, 7) pretzel knot (2,3,7) …   Wikipedia

  • Malt beverage — is an American term for both alcohol containing and non alcoholic fermented beverages, in which the primary ingredient is the grain, or seed of the barley plant, which has been allowed to sprout in a traditional way called ( malting ) slightly… …   Wikipedia

  • Remy Ma — in July 2005 Background information Birth name Reminisce Smith Also known as Remy …   Wikipedia

  • Tilt (drink) — Infobox Beverage name=Tilt bgcolor=orange type=Malt beverage/Energy drink flavour=Berry, Lemon Lime colour=Orange, Green abv=6.6%, 8.0% manufacturer=Anheuser Busch origin=USA introduced= discontinued= related= Sparks (drink), Red Bull… …   Wikipedia

  • Boisson energisante — Boisson énergisante Une boisson énergisante, à ne pas confondre avec une boisson énergétique, est une boisson destinée à donner un regain d énergie à son consommateur, en utilisant un mélange de différents ingrédients stimulants. Les boissons… …   Wikipédia en Français

  • Boisson Énergisante — Une boisson énergisante, à ne pas confondre avec une boisson énergétique, est une boisson destinée à donner un regain d énergie à son consommateur, en utilisant un mélange de différents ingrédients stimulants. Les boissons énergisantes comportent …   Wikipédia en Français

  • Boisson énergisante — Une boisson énergisante, à ne pas confondre avec une boisson énergétique, est une boisson destinée à donner un regain d énergie à son consommateur, en utilisant un mélange de différents ingrédients stimulants. Les boissons énergisantes comportent …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”