Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient

Question

This is somewhat of a meta-cstheory question, and is more historical in nature. What are some good examples of problems for which the literature followed the develpment below:

1. The original algorithms, despite being hopelessly intractable (e.g. exponential or high-degree polynomial), were considered breakthroughs at the time by the TCS community;
2. Since then, extremely efficient (e.g. provably linear or sublinear, maybe sub-quadratic) algorithms have been developed and are used in practice.

So, 1) precludes algorithms which have inefficient solutions (e.g. brute-force), but also have efficient solutions. The idea is that these are problems that were initially considered so difficult that even inefficient algorithms were considered a breakthrough by the research community. 2) is meant exclude problems that have shown incremental progress, even if those incremental developments are/were considered theoretically significant (e.g. exponential to high-degree polynomial).

In other words, have we gone from problems that were considered theoretical curiosities to practical, usable algorithms that are widely adopted in practice?

Answer 1

Computing a generating set of invariants (sometimes called the computational problem of "Noether's Normalization Lemma") for the action of $SL_3$ on an $n$-dimensional vector space $V$. (You can also talk about $SL_m$, but it's just a little cleaner to state the results when $m=3$.)

Went from non-constructive proof of finiteness, to computable, to EXPSPACE, to nearly-polynomial, over the course of over a century.

As discussed in GCT V: Hilbert originally proved that the invariant ring $\mathbb{C}[V]^{SL_3}$ was finitely generated non-constructively. After Gordan's criticism, Hilbert [1893] gave an algorithm, showing (in modern language) that a finite generating set can be computed in finitely many steps (so, the problem became computable). Degree bounds proved nearly a century later by Popov and then Derksen combined with Gröbner basis puts it into $\mathsf{EXPSPACE}$. In GCT V, Mulmuley put this problem into time $n^{O(\log \log n)}$.

Answer 2

The task of unification went from an exponential solution to linear time in the timespan of about a decade. The original exponential algorithm was a corner-stone for symbolic AI approaches and enabled the invention of the Prolog language.

Answer 3

I can think of two additional examples to the ones mentioned above, although I'm not sure that they were ever considered intractable.

Lovász Local Lemma - The Lovász local lemma (LLL) is a powerful theorem used in combinatorics to show that certain objects exist (non-constructively). Following a line of papers, Moser and Tardos [1] showed that a constructive solution for a general LLL "instance" can be computed\sampled very efficiently. This algorithm has applications in many areas of TCS, including several satisfiability and graph problems, and in many cases it yields near-linear solutions for these problems.

Expander decomposition (clustering) - A problem of splitting the graph into clusters such that each cluster is strongly connected in a sense (high conductance), and the total number of inter-cluster edges is small. A polynomial algorithm was shown in [2], and was later improved to near-linear in [3]. This too has many uses in a wide variety of areas in TCS.

[1] https://arxiv.org/abs/0903.0544 [2] https://dl.acm.org/doi/10.1145/990308.990313 [3] https://arxiv.org/pdf/0809.3232.pdf

Answer 4

Interior point algorithms for LP. Although they came after Ellipsoid they are a different class of provably polynomial-time algorithms. And despite initial skepticism about their ability to outperform Simplex in practice they do for many large instances and are part of the current best LP solvers in practice such as Gurobi. In terms of theory there has been a revolution in using them to obtain significantly faster theoretical algorithms for graphs and others using various other tools. Whether they will lead to dramatically better algorithms in practice is not yet clear.

Answer 5

Until Francis's QR algorithm was discovered, computing the eigenvalues was often done by first computing the characteristic polynomial, which was often an expensive and inaccurate endeavor, as has been demonstrated by Wilkinson. After the QR algorithm was discovered, research in methods for numerically computing matrix eigenvalues has flourished ever since.

Answer 6

I wanted to say Linear Programming, but although theoretical algorithm that are as fast as matrix multiplication have now been found, in practice people are still mostly using the exponential Simplex Method.

I think training neural networks might be an example from the practical side. It used to be considered I feasible to train more than a few layers. Now people are casually training hundreds of layers. That's not due to a particular algorithm though, but improvements to every part of system, from hardware to architectures and lots of algorithms.

Answer 7

Algorithms that computed the position of planets when they thought the earth was the center of the universe versus when they realized the sun was the center of the solar system. :-)

While that's not the type of answer you're looking for, it does demonstrate the idea that simplicity can sometimes be gained through a change in perspective.

Answer 8

Perhaps a good example is Graph Isomorphism testing, also discussed here:

Fastest known deterministic algorithm for the undirected Graph Isomorphism problem

and here:

https://people.cs.uchicago.edu/~laci/update.html

Answer 9

The ideal membership problem: if $f_1, \ldots, f_s$ are polynomials of degree at most $d$ with variables in $x_1, \ldots, x_n$, then are there $g_1, \ldots, g_n$ such that $f_1g_1 + \cdots + f_ng_n = 1$? Bounds can be obtained on the maximum degree $g_i$ that we need to check. The earliest discovered bound was doubly-exponential in $n$, but later bounds were found that are simply exponential in $n$. (So, parametrising by $2^n$, we've gone from exponential to linear time).

Answer 10

Travelling salesman may not theoretically be solvable in polynomial time, but given that there are probabilistic approximations, TSP is now realtime and polynomial. In the 80s a German problem involving 38 cities took 4 weeks to compute. Every delivery company now does hundreds in realtime

Answer 11

Like the TSP (Travelling Salesman Problem) @Dov mentions, efficient lossless video storage and transmission (as @Mark noted) isn't a solved problem but the lossy analogue is. VP9 and h.265 aren't state-of-the-art, but I would guess their ability to compress 4k video or images (from, say, the Voyager spacecraft) would be seen as magic to the developers of the original image processing software on Voyager (which was modified in transit, years later - great story - and I wonder if it's been done again!) Achieving what Voyager has achieved would be seen as hopelessly intractable when it was launched. So arguably an answer to the question as defined in the title, but not as asked in the body?

Answer 12

Counting perfect matches in plannar graphs is a good example for exponential speed up but I think it doesn't meet the first condition.