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

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?

• I think factoring integers is a very good candidate for such a problem if quantum computing turns out to be practically feasible. I think there are not many other problems that 1) have not been proved NP-hard and 2) have been considered intractable in practice despite serious effort. Jan 26, 2021 at 13:08
• I think with slightly looser definition of TCS and it's history, Fourier Transform will fit your criterions. When it was invented anything not analytical was beyond it's reach and now it's everywhere with a provably more efficient algorithm. Jan 26, 2021 at 15:57
• I'm not familiar enough with the specific details, but a coding theorist could probably write up a good answer about how we went from randomized capacity achieving codes in the 50's (which are still thought to be difficult to decode) to computationally efficient capacity achieving codes (buzzwords I know are turbo codes and polar codes, but I am not answering as they are only buzzwords to me).
– Mark
Jan 26, 2021 at 18:26
• @SagarM: I assume you are referring to the development of the FFT? A naive implementation of DFT would be quadratic (already close to "extremely efficient" by my condition in 2). Or is there something more subtle wrt complexity you are referencing? Jan 26, 2021 at 19:10
• Also, perhaps the current state of the art isn't exactly efficient, but deterministic primality testing is heading in the right direction. For a while it was an open problem if a polynomial time algorithm existed, but such algorithms have been known since 2002. Still pretty far from being practical and so probabilistic tests are still preferred. Jan 27, 2021 at 17:23

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)}$$.

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.

• This is an interesting example! Can you say more about Robinson's 1965 algorithm? It is not clear that this was considered a breakthrough at the time. Did the community originally feel that the exponential barrier couldn't be broken? Jan 27, 2021 at 16:25
• @TedThomson, This paper has a nice section on the historical context: sciencedirect.com/science/article/pii/S0747717189800124/… Jan 27, 2021 at 16:35

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.

• Good one re LLL! I hope to see some practical implementations/applications of Moser-Tardos sampling type algorithms. Jan 27, 2021 at 15:45

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.

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.

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.

• I'm not sure NNs count: Improvements in NN training are largely due to compute power and clever tricks. I am not aware of any guarantees for training NNs in sub-quadratic time. (Although this field is moving so fast, so by tomorrow this comment may be incorrect.) LPs are an interesting candidate, though. I am less familiar with developments there. Jan 26, 2021 at 13:12
• @TedThomson can you provide a link for complexity of nn learning such as reference for quadratic complexity? Jan 27, 2021 at 18:28

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.

• The geocentric model was given around the 2nd century and the heliocentric model was given around the 15th century. The computers came in the 19th century? :/ Jan 28, 2021 at 16:31
• What algorithms are you talking about? It is just a change in the mathematical formula, which has now become more complex than before. Jan 28, 2021 at 16:32
• Algorithm: a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer. Especially but not exclusively. The rules (formulas) that were used to calculate the positions of heavenly bodies were simplified with a heliocentric model. It doesn't satisfy condition 1 above because the TCS community didn't exist then, It's not a serious post, just a light hearted example. :-) Jan 28, 2021 at 21:17

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

• If I am not mistaken, Babai's breakthrough is still at best quasipolynomial, no? This would be a perfect candidate if one day we have a linear time algorithm for graph isomorphism! Jan 26, 2021 at 13:13
• While great theoretical progress has been made, not so much on the practical side. nauty has been highly practical and nearly state of the art (on the practical side) since the early 80s. I don't think anyone has ever implemented Babai-Luks '83 (iirc there was a question on here abt that but I can't find it rn), let alone Babai '16. Jan 26, 2021 at 16:35

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).

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

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?

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