3SUM (3SUM)

Description

Given a set $S$ of integers, determine whether there is a subset of $S$ of size 3 that sums to 0.

Related Problems

Generalizations: Real 3SUM

Subproblem: 3SUM', All-Integers 3SUM

Related: All-Integers 3SUM

Parameters

S: the set of integers
n: the number of integers in the set

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions TO Problem

Problem	Implication	Year	Citation	Reduction
3SUM'	if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$ then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$	1995	https://doi.org/10.1016/0925-7721(95)00022-2	link
3 Points on Line	if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$ then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$	1995	https://doi.org/10.1016/0925-7721(95)00022-2	link
Local Alignment	if: to-time $N^{2-\delta-\epsilon} for two strings of size $n$ and alphabet of size $n^{1-\delta}$ for some $\espilon > {0}$,$\delta \in ({0},{1})$ then: from-time: $n^{2-\epsilon'}$ for some $\epsilon' > {0}$	2014	https://link.springer.com/chapter/10.1007/978-3-662-43948-7_4	link
All-Integers 3SUM	if: to-time: $T(n)$ then: from-time: $O(T(n))$			link

Reductions FROM Problem

Problem	Implication	Year	Citation	Reduction
3SUM'	if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$ then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$	1995	https://doi.org/10.1016/0925-7721(95)00022-2	link
All-Integers 3SUM	if: to-time: $O(n^{2-\epsilon})$ for some $\epsilon > {0}$ then: from-time: $O(n^{1.5} + n^{2-\epsilon / 2})$	2018	https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 8.1	link

References/Citation

https://link.springer.com/article/10.1007/s00453-007-9036-3