3SUM

EN Texte en anglais Pas encore d'article dans ta langue : extrait en anglais.

In computational complexity theory, the 3SUM problem asks if a given set of n {\displaystyle n} real numbers contains three elements that sum to zero. A generalized version, k {\displaystyle k} -SUM, asks the same question on k {\displaystyle k} elements, rather than simply 3. 3SUM can be easily solved in O ( n 2 ) {\displaystyle O(n^{2})} time, and matching Ω ( n ⌈ k / 2 ⌉ ) {\displaystyle \Omega (n^{\lceil k/2\rceil })} lower bounds are known in some specialized models of computation (Erickson 1999). It was conjectured that any deterministic algorithm for the 3SUM requires Ω ( n 2 ) {\displaystyle \Omega (n^{2})} time. In 2014, the original 3SUM conjecture was refuted by Allan Grønlund and Seth Pettie who gave a deterministic algorithm that solves 3SUM in O ( n 2 / ( log ⁡ n / log ⁡ log ⁡ n ) 2 / 3 ) {\displaystyle O(n^{2}/({\log n}/{\log \log n})^{2/3})} time. Additionally, Grønlund and Pettie showed that the 4-linear decision tree complexity of 3SUM is O ( n 3 / 2 log ⁡ n ) {\displaystyle O(n^{3/2}{\sqrt {\log n}})} . These bounds were subsequently improved. The current best known algorithm for 3SUM runs in O ( n 2 ( log ⁡ log ⁡ n ) O ( 1 ) / log 2 ⁡ n ) {\displaystyle O(n^{2}(\log \log n)^{O(1)}/{\log ^{2}n})} time. Kane, Lovett, and Moran showed that the 6-linear decision tree complexity of 3SUM is O ( n log 2 ⁡ n ) {\displaystyle O(n{\log ^{2}n})} . The latter bound is tight (up to a logarithmic factor). It is still conjectured that 3SUM is unsolvable in O ( n 2 − Ω ( 1 ) ) {\displaystyle O(n^{2-\Omega (1)})} expected time. When the elements are integers in the range [ − N , … ,...