In computational complexity theory

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

, 3SUM is the following computational problem conjectured to require roughly quadratic time:

Given a set S of n integers, are there elements a, b, c in S such that a + b + c = 0?

There is a simple algorithm to solve 3SUM in O(n²) time. This is the fastest algorithm known in models that do not decompose the integers into bits, but matching lower bounds are only known in very specialized models of computation. Slightly faster randomized algorithms are known that exploit computational-model

Model of computation

In computability theory and computational complexity theory, a model of computation is the definition of the set of allowable operations used in computation and their respective costs...

 parallelism on a RAM

Random access machine

In computer science, random access machine is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers...

 and in the external-memory and cache-oblivious models . When the integers are in the range [−u ... u], 3SUM can be solved in time O(n + u lg u) by representing S as a bit vector and performing a discrete convolution using FFT.

Quadratic algorithm

Assume we have as input array S with elements S[0]..S[n-1]. Then the following algorithm will solve 3SUM problem in quadratic time.
sort(S);
for i=0 to n-3 do
a = S[i];
k = i+1;
l = n-1;
while (kdo
b = S[k];
c = S[l];
if (a+b+c 0) then
output a, b, c;
exit;
else if (a+b+c > 0) then
l = l - 1;
else
k = k + 1;
end
end
end

Here is example how the above algorithm will find the result for some input (after it is sorted). Current values of a are shown in bold, values of b and c are shown in red.
-25 -10 -7 -3 2 4 8 10 (a+b+c-25)
-25 -10 -7 -3 2 4 8 10 (a+b+c

-22)
. . .
-25 -10 -7 -3 2 4 8 10 (a+b+c

-7)
-25 -10 -7 -3 2 4 8 10 (a+b+c

-7)
-25 -10 -7 -3 2 4 8 10 (a+b+c

-3)
-25 -10 -7 -3 2 4 8 10 (a+b+c

2)
-25 -10 -7 -3 2 4 8 10 (a+b+c

0)

3SUM-hardness

A problem is called 3SUM-hard if solving it in subquadratic time implies a subquadratic-time algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

 for 3SUM. The concept of 3SUM-hardness was introduced by in analysis of algorithms

Analysis of algorithms

To analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...

 in computational geometry

Computational geometry

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...

. By now there are a multitude of problems that fall into this category.

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.