wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

3sum (508B)

      1 # 3SUM
      2 
      3 https://en.wikipedia.org/wiki/3SUM
      4 
      5 Does a set of n real numbers contain 3 numbers summing to 0?
      6 
      7 Can be done in O(n^2) or O(n^2/log^2 n (log log n)^(O(1))) (even for reals : [chan2018more])
      8 
      9 [3sum_hypothesis]: not known to be solvable in O(n^{2-\epsilon})
     10 
     11 used for hardness of pattern matching tasks, cf [amir2014hardness]
     12 
     13 can be done in time O(N log N) for N the maximal value using [fast_fourier_transform]
     14 
     15 Up: [fine_grained_complexity_problems]
     16 
     17 See also: [negative_triangle], [ov_conjecture]