3SUM and its obvious generalizations (4SUM, 5SUM, etc.) are examples of linear satisfiability problems. A generic linear satisfiability problem asks, given an array of n integers, do any r of them satisfy the equation
Baran et al. [BDP05] show that subquadratic algorithms for 3SUM are possible in common models of computation that allow more direct manipulation of the numbers instead of just real arithmetic, such as the word RAM. The improvement they obtain is roughly quadratic in the parallelism offered by the model; for example, with lg n-bit words, they obtain an O(n^{2})-time algorithm. With this word size, the 3SUM problem becomes whether any improvement beyond polylogarithmic factors (or indeed, beyond Θ(lg^{2}n)) is possible.