3SUM Hard Problems

The question is: “Can the class of 3SUM hard problems be solved in subquadratic time?” Its stated benchmark is the following decision problem. Given three finite sets of integers $A,B,C$ with total size $n=|A|+|B|+|C|$, determine whether

$$\exists a\in A,\ b\in B,\ c\in C\quad\text{such that}\quad a+b=c.$$

A problem is described as 3SUM-hard here if the 3SUM problem reduces to it. The question does not specify the reduction notion, or whether it asks for an algorithm for every problem in the class or for particular members; those distinctions are therefore left implicit, rather than supplying additional hypotheses not in the statement. TOPP, Problem 11: 3SUM Hard Problems

Background

Gajentaan and Overmars introduced the relevant class in computational geometry in 1995, identifying problems with quadratic-time algorithms that are hard by reduction from 3SUM. The connection made 3SUM hardness a way to explain why apparently different geometric tasks might resist faster algorithms. A motivating example is computing the area of the union of $n$ triangles. More broadly, the 3SUM conjecture has been used to obtain conditional lower bounds for problems in computational geometry and other areas of algorithms. Gajentaan and Overmars (1995) Chan (2020)

“Subquadratic” does not identify a single computational model or a single strength of improvement: a bound such as $O(n^2/\log n)$ is subquadratic, but is not of the form $O(n^{2-\varepsilon})$ for a fixed $\varepsilon>0$. This distinction matters in the history of 3SUM algorithms. Improvements depend on the model, including whether the algorithm works on a real-RAM, a word RAM with bounded-word operations, or a restricted decision tree. Lower bounds in a restricted decision-tree model do not by themselves give the same lower bound in the real-RAM or word-RAM models. TOPP, Problem 11: 3SUM Hard Problems Chan (2020)

Known results

The familiar quadratic barrier for 3SUM has been weakened by a sequence of upper bounds. Baran, Demaine, and Pătraşcu gave a subquadratic algorithm in common word-RAM settings; with $\lg n$-bit words, the reported time is $O\!\left(n^2(\lg\lg n/\lg n)^2\right)$. In the standard real-RAM model, Grønlund and Pettie gave a deterministic $O\!\left(n^2(\lg\lg n/\lg n)^{2/3}\right)$ algorithm in 2014. Gold and Sharir improved this to $O(n^2\lg\lg n/\lg n)$ in 2017, and Chan later obtained $O\!\left(n^2(\lg\lg n)^{O(1)}/\lg^2 n\right)$. These are genuine subquadratic bounds, though they do not establish a fixed-power improvement over $n^2$. Baran, Demaine, and Pătraşcu (2008) Grønlund and Pettie (2014) Gold and Sharir (2017) Chan (2020)

There are also faster decision-tree bounds: Gold and Sharir report randomized $O(n^{3/2})$ complexity for 3SUM in the 4-linear decision-tree model. Conversely, quadratic lower bounds are known for 3SUM and a few 3SUM-hard problems in restricted decision-tree models. The widely used 3SUM conjecture asserts that 3SUM has no $O(n^{2-\varepsilon})$-time algorithm, even in expectation, for any fixed $\varepsilon>0$. This is a conjecture, not a consequence of the restricted-model lower bounds, and it is compatible with the logarithmic-factor savings above. Gold and Sharir (2017) TOPP, Problem 11: 3SUM Hard Problems

Subquadratic algorithms are known for particular geometric problems in the class, so 3SUM-hardness does not mean that every individual member is known to require quadratic time. Chan gave bounds of $O\!\left(n^2(\lg\lg n)^{O(1)}/\lg^2 n\right)$ for several problems, including intersection of three simple polygons and offline triangle range searching for bichromatic segment intersections. For the latter task, given two sets of $n$ pairwise disjoint planar segments and $n$ triangles, the goal is to count, for each triangle, the intersections between the two segment sets that lie inside it. A 2021 result gives an $O(n^{60/31+\varepsilon})$ algebraic decision-tree algorithm for this range-searching task, for every $\varepsilon>0$. These results concern specified problems and models; they do not settle a universal interpretation of the question about the entire class. Chan (2020) Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model (2021)