3SUM Hard Problems

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

For finite integer sets $A,B,C$, put $n=|A|+|B|+|C|$. The three-set 3SUM decision problem asks whether $a+b=c$ for some $a\in A,b\in B,c\in C$. A problem is 3SUM-hard in the source's sense when 3SUM reduces to it with sufficiently small overhead to transfer a subquadratic algorithm. Subquadratic means $o(n^2)$; a truly subquadratic bound is $O(n^{2-\varepsilon})$ for a fixed $\varepsilon>0$. Bounds depend on the computational model.

Statement recorded in the supplied source.

Can the class of 3SUM-hard problems be solved in subquadratic time? Is 3SUM impossible in $O(n^{2-\varepsilon})$ time for every fixed $\varepsilon>0$, even in expectation? The source reports logarithmic improvements below quadratic time in the real-RAM and word-RAM models; these do not resolve this sharper question. [S2]

Short English statement

Can the class of 3SUM-hard problems be solved in subquadratic time? Is 3SUM impossible in $O(n^{2-\varepsilon})$ time for every fixed $\varepsilon>0$, even in expectation? The source reports logarithmic improvements below quadratic time in the real-RAM and word-RAM models; these do not resolve this sharper question.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 5500011 (AMR-054-0011). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Erik D. Demaine, Joseph S. B. Mitchell and Joseph O'Rourke (editors), The Open Problems Project, maintained original source, Problem 11, Statement and complete Partial/Related Results. https://github.com/edemaine/topp/blob/main/Problems/P.000011.