Galactus the Devourer

On efficient algorithms, the Exponential Time Hypothesis, and losing the plot.

Hi there, argmin readers! Today’s post is about the history of failing to rigorously define efficiency in computer science. Like my previous post on Fourier transforms, it’s more technical than usual, but I tried to make it as accessible as possible.

---

I’ve always been fascinated by this pernicious pattern in the practice of applied mathematics, which I wrote about here a few weeks ago:

Applied mathematicians often need to build a giant scaffolding of mathematical modeling to solve a problem. This scaffolding creates new mathematical puzzles that aren’t directly connected to the original problem of interest, but that entice problem solvers. You’ll then see dozens of follow-up papers solving the puzzles but forgetting the problem we cared about in the first place.

There is probably no better example of such forgetting than the field of complexity theory.

In 1965, Jack Edmonds came up with a clever way to find a maximum matching in a graph. He wanted to argue that his algorithm could be computed “efficiently,” as the procedure was a bit complicated and required a computer to run. But he found he didn’t have the language to describe what it would mean for an algorithm to be efficient. In Section 2 of his paper, named “Digression,” he wrote,

According to the dictionary, “efficient” means “adequate in operation or performance.” This is roughly the meaning I want—in the sense that it is conceivable for maximum matching to have no efficient algorithm. Perhaps a better word is “good.”

I am claiming, as a mathematical result, the existence of a good algorithm.

Edmonds noted that he could enumerate every possible solution to the matching problem and find the largest one. This would be a correct algorithm. However, the number of total matchings is exponentially large in the size of the graph. Blindly writing all possible matchings down and picking the one that achieved the maximum was a “not good” algorithm. You might call it a “bad” algorithm. His new procedure was vastly more efficient.

So Edmonds spent two pages constructing a definition of good. He demanded that everyone agree on a reasonable definition for a problem size. For his matching problem, he said the size was the number of vertices plus the number of edges in the graph. A good algorithm would then have a running time upper-bounded by some well-defined function of that size, no matter how large the instance. He demanded that the running-time bound hold for every conceivable size, because he feared someone might rig the problem by planting a few small instances that were unnaturally hard.

Edmonds wasn’t completely satisfied with this definition. Indeed, he wrote:

It would be unfortunate for any rigid criterion to inhibit the practical development of algorithms which are either not known or known not to conform nicely to the criterion. Many of the best algorithmic ideas known today would suffer by such theoretical pedantry. In fact, an outstanding open question is, essentially: “how good” is a particular algorithm for linear programming, the simplex method? And, on the other hand, many important algorithmic ideas in electrical switching theory are obviously not “good” in our sense.¹

With this caveat noted, he concluded his digression by announcing the complexity of his new blossom algorithm: “An upper bound on the order of difficulty of the matching algorithm is n⁴, where n is the number of vertices in the graph.”

Edmonds did not make any further arguments for what he meant by good. He asserted that exponential time is bad. For most algorithm designers, linear time, proportional to the input length, was naturally excellent. Moreover, our grade-school multiplication algorithm took quadratic time (multiply two three-digit numbers out by hand like you were taught in school and count the number of digits you write down when you calculate it), and that seemed pretty good. Edmonds had a matching algorithm that required a quartic number of operations. To later formalists like Richard Karp, it seemed like a “polynomial” number of operations was a reasonable definition for goodness. Polynomial time is good. Exponential time is bad. This created the field of complexity theory, with the goal of proving that all sorts of algorithms run in polynomial time and characterizing the problems for which no polynomial-time algorithm existed.

But polynomial time probably haunted Edmonds. It is not a “good” algorithm if your procedure scales like n¹⁰⁰⁰, even if this is technically a polynomial. More absurdly,

is a polynomial bigger than the exponential function 2ⁿ for any n we could ever encounter. Polynomial was always an imperfect definition of good, but we ran with it. Thousands of papers later, we just have a zoo of confusing complexity results unmoored from the realities of computation.

Indeed, asymptotic thinking about how polynomials differ from exponentials enables the bad habit of designing “galactic algorithms,” conceptual procedures with running times so large they could never be implemented in our universe. I mentioned these in my earlier post about OpenAI’s Faster Fourier Transform.

This brings me back to our beneficent friends at OpenAI. This week they declared their latest breakthrough in theoretical computer science. They provided an algorithm for the satisfiability problem that ran in “subexponential time.” Satisfiability is one of the most well-known “NP complete problems, and I don’t want to go into the details of P vs NP today, but suffice it to say that you would win a Clay Millennium Prize if you could find a polynomial-time algorithm for satisfiability.²

Now, subexponential time does not mean polynomial time. It merely means that the running time can be bounded as

Where n is the problem size, and f is a “sublinear” function, meaning the limit of f(n)/n goes to zero as n goes to infinity.

Indeed, in the case of OpenAI’s new algorithm for the satisfiability problem, the bound was

For some unspecified constant numbers d and C. Ugly as this expression is, this was touted on Twitter as the biggest moment in theoretical computer science in 50 years. It was covered all over the tech press this week. OpenAI clearly wanted us to think it was a big fucking deal. And many theoretical computer scientists took to social media to agree.

Since it was such a big deal, I wanted to see if I could understand the algorithm a bit. Of course, as I’ve told all of you, we’re not supposed to read these papers. We’re supposed to ask ChatGPT what they say. And ChatGPT told me there was a catch.

The derived algorithm runs exhaustive search—the algorithm Edmonds declared bad in 1965—if the number of variables is less than 10^10,000,000,000,000,000,000,000,000.

This is a completely unfathomable number.³ There are something like 10^80 atoms in the universe. That’s 10^9,999,999,999,999,999,999,999,920 times smaller. Up until this barely finite threshold, the magic new algorithm calls an exponential-time subroutine. For any problem that we could ever consider, the procedure is exponential time. The “result” is that only in some bizarre, unknowable neighborhood of infinity, satisfiability problems are solved in subexponential time.

The claimed subexponential algorithm for satisfiability is definitive evidence that our definition of efficient was even worse than we thought it was 50 years ago. The answer tells us nothing about efficiency or goodness. Sometimes you need to answer your question to realize you wanted something else.

I’m not a betting man, but I have a prediction. It’s going to turn out that P=NP in some galactic sense, and all we’ll learn is that we spent fifty years answering the wrong question.

1. It’s funny that Edmonds references the simplex algorithm in his musings here. The simplex algorithm is the most important algorithm ever invented, and we now know that, technically speaking, its running time is exponential. Most of the time it’s fast, but you can construct weird cases where it takes an exponential number of steps. And yet, it is deployed all over the globe, determining optimal programs for exponentially diverse applications in optimization. Edmonds foresaw this sharp disconnect between theory and practice in 1965!

2. What’s particularly ironic is that we have incredibly efficient algorithms to solve industrial-scale satisfiability problems. Conventional computers can solve problems with millions of variables and millions of clauses. This guy at Intel solved a problem with a billion variables and 4 billion clauses in a day.

3. I confirmed this crazy number by plugging the paper into Claude. ChatGPT and Claude hate each other, so if they agree, it must be true.