Our Three Body Problem
The three body problem, computer theory style
Ellis Horowitz is one of the founders of the theory of algorithms. His thesis with George Collins in 1969 had the word “algorithm” in the title: “Algorithms for Symbolic Integration of Rational Functions.” He is known for many things, including an algorithm that after forty years is still the best known.
Today I want to talk about this algorithm, and one of the most annoying open problems in complexity theory.
We have just recently talked about the three body problem from physics, but now it is our turn in computer theory. Our version is called the 3SUM problem. The problem—I guess you probably know it already—is given three sets of integers, are there , , and so that
Suppose the sets each contain at most elements and the elements are bounded by a polynomial in , then there is a trivial algorithm that takes : just try all triples. Our friends at Wikipedia say
3SUM can be easily solved in time
This is unfair. The algorithm may be simple, but it is in my opinion very clever. It is due essentially to Ellis and his then PhD student Sartaj Sahni, who proved in 1974 a related algorithm for knapsack. More on knapsack in a moment. They called their result a “square root improvement.”
The Quadratic Upper Bound
Here is the general idea. Build a table of all possible values and then check to see if is in the table. With some care this can be done in time . I once talked about this result—it is one of my favorite algorithms. For example it can be used to solve the knapsack problem in time . Recall this is the problem of finding that are so that
Here and are given integers. This is what Ellis and Sahni did in 1974.
In ancient times, before 3SUM was called 3SUM, I thought about how to improve the above algorithm. The idea of breaking things into three or more sets was natural. I worked pretty hard on trying to get a better method. I failed. Here is what I said in the previous discussion:
A natural problem is what happens with a set like ? Is there a way to tell if is in this set in time , for example? If this is possible, then the knapsack problem has an algorithm whose exponential term is . I have thought about this and related approaches quite often. I have yet to discover anything, I hope you have better luck.
The 3SUM Problem
Actually the usual version now is that we are given one set . Then we must determine whether there are three elements in so that
It is not hard to show that having one set instead of three is essentially no real change: just code the set name into the number.
There are lower bounds on the 3SUM problem in various restricted models of computation. Jeff Erickson showed a quadratic lower bound provided the elements are real numbers and the computation is a special type of decision tree. The result is interesting because it is an adversary argument where it is useful to use infinitesimals in the argument. See the paper for details.
Back to the 3SUM problem for integers. If the set has all elements less than in absolute value, then 3SUM can be computed in time
The trick is to cheat: use more than comparisons as in Erickson’s model.
Suppose that is a set of positive numbers less than —this is not needed but I hope makes the idea clearer. The problem is to see if contains an element from another set . Define the polynomial by
Note it’s degree is at most . Using the Fast Fourier transform we can compute in the time . The critical point is that is equal to where
and is equal to the number of in so that . But we are almost done. Just check each element from to see if its coefficient in is positive.
I wish I could report that the problem has been solved, that there is a sub-quadratic algorithm now for 3SUM. That we have finally beat Horowitz and Sahni. But that is not the case. We do have some results that are additional evidence that either the old algorithm is best, or that it will be hard to improve it.
The modern view is to make a failure to find an algorithm into a useful tool. Modern cryptography is based on this: factoring has been studied forever and no polynomial-time algorithm is known, so we purpose that it is hard and use it for the basis of crypto-systems. Think RSA.
The same as been done to 3SUM. Since in forty years we cannot beat quadratic, let’s assume that there is no sub-quadratic algorithm and use this as a tool to “prove” conditional lower bounds on problems. It’s lemons into lemonade.
Well to be careful there are better algorithms. The work of Ilya Baran, Erik Demaine, and the late Mihai Pǎtraşcu give slightly better times on RAM machines. These results are interesting, but do not get , for example. See their paper for details. Pǎtraşcu also showed a tight reduction from 3-SUM to listing 3-cliques.
There is other work on why the 3SUM problem is hard by Amir Abboud, Kevin Lewi, and Ryan Williams: in the paper: Losing Weight by Gaining Edges. They prove many interesting results; here is one that I especially like:
Theorem 1 For any , if -Clique can be solved in time , then -SUM can be solved in time .
Of course -SUM is the generalization to 3SUM where we seek numbers in a set that sum to zero.
Is there a sub-quadratic algorithm for 3SUM? I would love to see one. The problem seems hard, very hard. It has been open for forty years, and perhaps it will be open for another forty. Who knows. As always I believe that there could very well be a better algorithm—I am always optimistic about the existence of new clever algorithms.