Problem 11: 3SUM Hard Problems

Statement

Can the class of 3SUM hard problems be solved in subquadratic time? These problems can be reduced from the problem of determining whether, given three sets of integers, A, B, and C with total size n, there are elements a∈A, b∈B, and c∈C such that a + b = c.

Origin

[GO95].

Status/Conjectures

Open.

Motivation

Many fundamental geometric problems fall in this class, e.g., computing the area of the union of n triangles.

Partial and Related Results

Ω(n²) lower bounds are known for 3SUM and a few 3SUM-hard problems in restricted decision tree models of computation [ES95,Eri99a,Eri99b].

3SUM and its obvious generalizations (4SUM, 5SUM, etc.) are examples of linear satisfiability problems. A generic linear satisfiability problem asks, given an array of n integers, do any r of them satisfy the equation

α₁x₁ + α₂x₂ + ^... + α_rx_r = α₀

where α₀, α₁, α₂,..., α_r are fixed constants. Erickson [Eri99a] proved an Ω(n^⌈r/2⌉) lower bound for any problem of this type, in the restricted linear decision tree model. This lower bound is tight except for a logarithmic factor when r is even. Ailon and Chazelle generalized Erickson's bound and improve it for large r or for more than r variables [AC05].

Baran et al. [BDP05] show that subquadratic algorithms for 3SUM are possible in common models of computation that allow more direct manipulation of the numbers instead of just real arithmetic, such as the word RAM. The improvement they obtain is roughly quadratic in the parallelism offered by the model; for example, with lg n-bit words, they obtain an O(n²$\left(\vphantom{\frac{\lg \lg n}{\lg n}}\right.$${\frac{{\lg \lg n}}{{\lg n}}}$$\left.\vphantom{\frac{\lg \lg n}{\lg n}}\right)^{2}_{}$)-time algorithm. With this word size, the 3SUM problem becomes whether any improvement beyond polylogarithmic factors (or indeed, beyond Θ(lg²n)) is possible.

Appearances

[MO01]

Categories

lower bounds

Entry Revision History

J. O'Rourke, 2 Aug. 2001; Jeff Erickson, 20 June 2002; E. Demaine, 7 July 2005; Raphael Clifford, 7 July 2011.

Bibliography

AC05

N. Ailon and B. Chazelle.
Lower bounds for linear degeneracy testing.
Journal of the ACM (JACM), 52(2):157-171, 2005.

BDP05

Ilya Baran, Erik D. Demaine, and Mihai Ptraşcu.
Subquadratic algorithms for 3SUM.
In Proceedings of the 9th Workshop on Algorithms and Data Structures, Waterloo, Ontario, Canada, August 2005.
To appear.

Eri99a

Jeff Erickson.
Lower bounds for linear satisfiability problems.
Chicago J. Theoret. Comput. Sci., 1999(8), 1999.

Eri99b

Jeff Erickson.
New lower bounds for convex hull problems in odd dimensions.
SIAM J. Comput., 28:1198-1214, 1999.

ES95

Jeff Erickson and R. Seidel.
Better lower bounds on detecting affine and spherical degeneracies.
Discrete Comput. Geom., 13:41-57, 1995.

GO95

A. Gajentaan and M. H. Overmars.
On a class of O(n²) problems in computational geometry.
Comput. Geom. Theory Appl., 5:165-185, 1995.

MO01

J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573-582, 2001.
Also in SIGACT News 32(3):63-72 (2001), Issue 120.