Algorithms with huge running times
David Johnson is a renown computer theorist who was awarded the 2009 Knuth Prize, for his seminal contributions to theory. He is famous for: his many great papers on various aspects of algorithmic theory, his classic book “Computers and Intractability: A Guide to the Theory of NP-Completeness” with Mike Garey, and his continuing interest in the practical aspects of computing. He has been the driving force behind many experimental studies of how well algorithms perform on “real” data.
Today I want to discuss the issue of galactic algorithms. A galactic algorithm is an algorithm that is wonderful in its asymptotic behavior, but is never used to actual compute anything.
The power of asymptotic analysis is that we can predict the behavior of an algorithm without ever running it. This ability is one of the great achievements of modern complexity theory. That we can predict, often with great accuracy, how fast an algorithm would run, if executed, is indeed a major triumph. Yet, often algorithms are created that cannot be run because their running time is too large, or there are less sophisticated ones that would out-perform them on realistic data.
The name “galactic algorithm” is due to Ken Regan—I suggested the concept, but he came up with the name—my original name was terrible. Not actually “terrible,” but not as good as Ken’s. Perhaps there is a better name, for now it is the one I will use.
The thought behind it is simple: some algorithms are wonderful, so wonderful that their discovery is hailed as a major achievement. Yet these algorithms are never used and many never will be used—at least not on terrestrial data sets. They do, however, play several important roles in our field, which I will dicuss in the next section.
The danger in giving examples is that I may make some people upset—this is not my intent. If they are the proud creators of an algorithm they may be offended if I point out that their prize creation is galactic—that it will not get used in practice. I think this misses several key points. There is nothing wrong with galactic algorithms, they abound throughout complexity theory. They are still of immense value for several reasons:
A galactic algorithm may contain new techniques that can be used to create other algorithms that can be used. This happens all the time.
A galactic algorithm may eventually become a real algorithm as computer architectures change.
A galactic algorithm may lead to a series of research advances. The initial algorithm may run in a huge polynomial, but further improvements may yield practical algorithms. This has happen a number of times.
A galactic algorithm may show us that lower bounds that were conjectured are wrong. This alone could be important and often is a great reason for finding such algorithms. For an example, if there were tomorrow a discovery that showed there is a factoring algorithm with a huge but provably polynomial time bound that would change our beliefs about factoring. The algorithm might never be used, but would certainly shape the future research into factoring.
Here are some examples of galactic algorithms. Again please keep all of the above in mind. This is not any criticism.
Nash Equilibrium: I thought I would start with an algorithm of my own. Not because it is the most important, but to make it clear that I too have worked on galactic algorithms. The result is the best current bound for non-zero sum games. The result is due to Evangelos Markakis, Aranyak Mehta, and myself: it proves that every such game has a strategy that is an Nash solution, and it finds this solution in time at most
Note, this is clearly a galactic algorithm: even for modest approximations the exponent is huge, and the algorithm cannot be used. Yet researchers in algorithmic game theory would be thrilled if one could prove a bound of the form
where the dependence on is reduced. Note, this would still be a galactic algorithm.
Quantum Factoring: The famous quantum factoring algorithm of Peter Shor may or may not be a galactic algorithm. It is of course one of the great results in theory, ever. It has sparked funding for research centers on quantum computation that have promoted many other advances.
If and when practical quantum computers are built Peter’s algorithm will be one of the first algorithms run on them. Right now it is a galactic algorithm. But, perhaps it is the best example of the importance of galactic algorithms. Peter’s great breakthrough in the discovery of his algorithms has lead to the creation of thousands of new results and papers.
Neil Robertson and Paul Seymour proved their famous graph minor theorem. This theorem proves that every minor closed family , there is a polynomial time algorithm to check if a graph contains a forbidden minor from . The algorithms that arise from this general technology unfortunately contain huge constants that make the algorithms galactic. There has been recent work trying to make the results potentially practical. In any event, David Johnson famously once said,
For any instance that one could fit into the known universe, one would easily prefer to even constant time, if that constant had to be one of Robertson and Seymour’s.
Matrix Product: One of the most beautiful two results are the initial brilliant result of Volker Strassen on fast matrix product, and the subsequent deep work of Don Coppersmith and Shmuel Winograd on an even faster matrix product algorithm. These results are used by hundreds—perhaps thousands of papers. Clearly, these are galactic algorithms. Even the initial one due to Strassen was not used in actual computation for many years. Apparently today as computers have became able to perform huge matrix products it is unclear if Strassen can be used. Wikipedia claims that even for matrices of size by the improvement is marginal.
Sorting: Miklos Ajtai, János Komlós, and Endre Szemerédi proved the existence of a sorting network of depth and size. This solved a long standing open problem, but due to the hidden constants it is a galactic algorithm.
Galactic algorithms can be of immense importance. They can lead to new methods, new directions, and sometimes can be made practical. If you found a SAT algorithm that runs in time bounded by
or proved that any SAT algorithm requires time
then you would be famous. The first would prove P=NP so that would be huge, the later would prove a non-linear lower bound on SAT. That would also be huge—at least to those of us who have tried to prove such theorems.
Is this classification of algorithms useful? What is your favorite galactic algorithm? What do you all think?