Lesson plan
3SUM
In computational complexity theory, the 3SUM problem asks if a given set of n real numbers contains three elements that sum to zero. A generalized version, k -SUM, asks the same question on k elements, rather than simply 3. 3SUM can be easily solved in O(n^2) time, and matching \Omega(n^{\lceil k/2 \rceil}) lower bounds are known in some specialized models of computation . It was conjectured that any deterministic algorithm for the 3SUM requires \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}) time. Additionally, Grønlund and Pettie showed that the 4-linear decision tree complexity of 3SUM is 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}) time. Kane, Lovett, and Moran showed that the 6-linear decision tree complexity of 3SUM is 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-\Omega(1)}) expected time.…
Article summary
In computational complexity theory, the 3SUM problem asks if a given set of n real numbers contains three elements that sum to zero. A generalized version, k -SUM, asks the same question on k elements, rather than simply 3. 3SUM can be easily solved in O(n^2) time, and matching \Omega(n^{\lceil k/2 \rceil}) lower bounds are known in some specialized models of computation . It was conjectured that any deterministic algorithm for the 3SUM requires \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}) time. Additionally, Grønlund and Pettie showed that the 4-linear decision tree complexity of 3SUM is 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}) time. Kane, Lovett, and Moran showed that the 6-linear decision tree complexity of 3SUM is 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-\Omega(1)}) expected time.…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.