3SUM

在计算复杂度理论中, 3SUM问题是指如下的问题：给定一个包含n个实数的集合，判断其中是否包含3个和为0的元素。问题也可以推广到一个更一般化的版本，rSUM，是要求判断集合中是否存在r个数的和为0。3SUM问题可以很容易地在$O(n^{2})$的时间复杂度内解决。对于某些特化的计算模型，这已经达到了它们$\Omega (n^{\lceil r/2\rceil })$的复杂度下界。

人们曾经猜想任何3SUM问题的确定性算法都至少需要$\Omega (n^{2})$的时间复杂度。然而在2014年，最初的3SUM被Allan Grønlund和Seth Pettie否决了。他们给出了一个能在能在$O(n^{2}/({\log n}/{\log \log n})^{2/3})$的时间复杂度内求解3SUM问题的确定性算法。目前仍然有人猜想3SUM是不可能在$O(n^{2-\Omega (1)})$的时间复杂度内解决的。