From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Low-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Low Priority
 Field: Discrete mathematics

Subquadratic algorithms[edit]

I suggest citing this paper which obtains subquadratic algorithms for 3SUM when you can manipulate the bits in the input integers. I hesitate to add the citation myself because I am an author of the paper. —Erik Demaine 05:27, 13 February 2007 (UTC)

Now we need an update for Mglisse (talk) 08:15, 6 January 2015 (UTC)

Correctness of quadratic algorithm[edit]

The explanation of why the posted algorithm works seemingly contained some errors, which I hopefully managed to fix. What is still missing is some explanation of how this algorithm makes use of the sortedness of the array. As it stands, it doesn't really help the reader to understand what's going on much at all. Wppds (talk) 07:31, 7 April 2014 (UTC)

Subquadratic 3SUM[edit]

I think there is no need to mention the results of Baran, Demaine and Pătraşcu in the first paragraph as they are appropriate only for Integer3SUM. Also their significance is shadowed by the new result of Gronlund and Pettie.

Opening statment[edit]

The opening statment characterizes 3SUM as the problem of determining whether a subset of size three of a set of REALS sums zero, when the input set should be composed of integers.

The problem has been considered both for integers (represented in binary on a word RAM, where you can hash them and use them as indices into lookup tables and so on) and for numbers in a real model of computation where all you can do is add them and compare them. Saying that it is only for integers is too dogmatic, and misses important aspects of the problem. —David Eppstein (talk) 03:06, 3 February 2017 (UTC)