Efficient algorithms, the Exponential Time Hypothesis, and losing the plot

The essay argues that computer science never found a fully satisfactory mathematical definition of an “efficient” algorithm. In 1965, Jack Edmonds described his graph-matching method as good because it ran in polynomial time, while warning that rigid criteria could misrepresent useful algorithms. Complexity theory later treated polynomial time as efficient and exponential time as inefficient. Recht says this distinction is useful in theory but can become detached from practice: a polynomial with an enormous exponent may be slower than an exponential algorithm for every realistic input. The simplex method illustrates the gap: it has exponential worst-case behavior yet is widely used and often performs well. Asymptotic definitions can therefore produce “galactic” algorithms that are formally significant but impossible to run.

Recht applies this criticism to OpenAI’s claimed subexponential algorithm for satisfiability. Its bound only applies asymptotically, and the method falls back on exhaustive search below an astronomically large variable-count threshold, so it offers no practical improvement for any conceivable problem. He sees this as evidence that complexity theory’s standard measure of efficiency can miss the question people actually care about. A commenter adds important nuance: ETH and SETH were intended as hypotheses for mapping relationships between problems, not definitive claims about practical efficiency. There are meaningful intermediate milestones between exponential algorithms and polynomial time, and improvements can affect other problems through reductions even when their direct SAT application requires impossible input sizes. The commenter also notes that gigantic constants have appeared in theoretical algorithms before AI.