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)})$的時間複雜度內解決的。