<p>Computing a generating set of invariants (sometimes called the computational problem of &quot;Noether's Normalization Lemma&quot;) for the action of <span class="math-container">$SL_3$</span> on an <span class="math-container">$n$</span>-dimensional vector space <span class="math-container">$V$</span>. (You can also talk about <span class="math-container">$SL_m$</span>, but it's just a little cleaner to state the results when <span class="math-container">$m=3$</span>.)</p>
<p>Went from non-constructive proof of finiteness, to computable, to EXPSPACE, to nearly-polynomial, over the course of over a century.</p>
<p>As discussed in <a href="https://doi.org/10.1090/jams/864" rel="noreferrer">GCT V</a>: Hilbert originally proved that the invariant ring <span class="math-container">$\mathbb{C}[V]^{SL_3}$</span> was finitely generated <em>non-constructively</em>. After Gordan's criticism, <a href="http://www.ams.org/mathscinet-getitem?mr=1510781" rel="noreferrer">Hilbert [1893]</a> 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 <a href="http://www.ams.org/mathscinet-getitem?mr=637618" rel="noreferrer">Popov</a> and then <a href="http://doi.org/10.1090/S0002-9939-00-05698-7" rel="noreferrer">Derksen</a> combined with Gröbner basis puts it into <span class="math-container">$\mathsf{EXPSPACE}$</span>. In <a href="https://doi.org/10.1090/jams/864" rel="noreferrer">GCT V</a>, Mulmuley put this problem into time <span class="math-container">$n^{O(\log \log n)}$</span>.</p>

CC BY-SA 4.0
2021-01-26T17:42:54.387Z
2021-01-27T22:08:19.277Z
2021-01-27T22:08:19.277Z
Joshua Grochow
<p>The task of <a href="https://en.wikipedia.org/wiki/Unification_(computer_science)#A_unification_algorithm" rel="noreferrer">unification</a> 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.</p>

CC BY-SA 4.0
2021-01-27T16:25:32.897Z
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?
TedThomson
CC BY-SA 4.0
2021-01-27T16:35:03.833Z
@TedThomson, This paper has a nice section on the historical context: https://www.sciencedirect.com/science/article/pii/S0747717189800124/pdf?md5=5b4e45c4f83e593270e34740838f59db&pid=1-s2.0-S0747717189800124-main.pdf
liori
CC BY-SA 4.0
2021-01-27T13:41:06.270Z
2021-01-27T13:41:06.270Z
liori
<p>I can think of two additional examples to the ones mentioned above, although I'm not sure that they were ever considered intractable.</p>
<p>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 &quot;instance&quot; 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.</p>
<p>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.</p>
<p>[1] <a href="https://arxiv.org/abs/0903.0544" rel="noreferrer">https://arxiv.org/abs/0903.0544</a>
[2] <a href="https://dl.acm.org/doi/10.1145/990308.990313" rel="noreferrer">https://dl.acm.org/doi/10.1145/990308.990313</a>
[3] <a href="https://arxiv.org/pdf/0809.3232.pdf" rel="noreferrer">https://arxiv.org/pdf/0809.3232.pdf</a></p>

CC BY-SA 4.0
2021-01-27T15:45:00.257Z
Good one re LLL! I hope to see some practical implementations/applications of Moser-Tardos sampling type algorithms.
Chandra Chekuri
CC BY-SA 4.0
2021-01-27T09:26:20.313Z
2021-01-27T09:26:20.313Z
user3209423940248
<p>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.</p>

CC BY-SA 4.0
2021-01-27T14:39:32.100Z
2021-01-27T14:39:32.100Z
Chandra Chekuri
<p>Until <a href="https://doi.org/10.1093/comjnl/4.3.265" rel="noreferrer">Francis's</a> <a href="https://doi.org/10.1093/imanum/drp012" rel="noreferrer">QR</a> <a href="http://doi.org/10.4169/amer.math.monthly.118.05.387" rel="noreferrer">algorithm</a> 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.</p>

CC BY-SA 4.0
2021-01-28T11:50:15.380Z
2021-01-28T11:50:15.380Z
Joe Boy
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2021-01-26T13:12:49.583Z
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.
TedThomson
CC BY-SA 4.0
2021-01-27T18:28:04.577Z
@TedThomson can you provide a link for complexity of nn learning such as reference for quadratic complexity?
Turbo
CC BY-SA 4.0
2021-01-26T09:11:23.383Z
2021-01-26T09:11:23.383Z
Thomas Ahle
<p>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.  :-)</p>
<p>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.</p>

CC BY-SA 4.0
2021-01-28T16:31:27.443Z
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? :/
Inuyasha Yagami
CC BY-SA 4.0
2021-01-28T16:32:19.100Z
What algorithms are you talking about? It is just a change in the mathematical formula, which has now become more complex than before.
Inuyasha Yagami
CC BY-SA 4.0
2021-01-28T21:17:18.597Z
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.  :-)
Neil Robertson
CC BY-SA 4.0
2021-01-27T17:40:43.313Z
2021-01-27T17:40:43.313Z
Neil Robertson
<p>The <a href="https://en.wikipedia.org/wiki/Hilbert%27s_Nullstellensatz#Effective_Nullstellensatz" rel="nofollow noreferrer">ideal membership problem</a>: if <span class="math-container">$f_1, \ldots, f_s$</span> are polynomials of degree at most <span class="math-container">$d$</span> with variables in <span class="math-container">$x_1, \ldots, x_n$</span>, then are there <span class="math-container">$g_1, \ldots, g_n$</span> such that <span class="math-container">$f_1g_1 + \cdots + f_ng_n = 1$</span>? Bounds can be obtained on the maximum degree <span class="math-container">$g_i$</span> that we need to check. The earliest discovered bound was <em>doubly-exponential</em> in <span class="math-container">$n$</span>, but later bounds were found that are simply exponential in <span class="math-container">$n$</span>. (So, parametrising by <span class="math-container">$2^n$</span>, we've gone from exponential to linear time).</p>

CC BY-SA 4.0
2024-09-19T18:19:20.137Z
For the general ideal membership problem, where the RHS is not 1 but is another polynomial $h$ given as input, doubly-exponential is in fact a tight degree lower bound. The singly-exponential degree bound works more generally than in the problem you defined: it works for the *radical* ideal membership problem. Namely, given $f_1, \dotsc, f_s,h$, is there some power of $h$ that is in $\langle f_1, \dotsc, f_s \rangle$?
Joshua Grochow
CC BY-SA 4.0
2021-01-28T06:44:01.433Z
2021-01-28T06:44:01.433Z
Jordan Barrett
<p>Perhaps a good example is Graph Isomorphism testing, also discussed here:</p>
<p><a href="https://cstheory.stackexchange.com/questions/25667/fastest-known-deterministic-algorithm-for-the-undirected-graph-isomorphism-probl">Fastest known deterministic algorithm for the undirected Graph Isomorphism problem</a></p>
<p>and here:</p>
<p><a href="https://people.cs.uchicago.edu/%7Elaci/update.html" rel="noreferrer">https://people.cs.uchicago.edu/~laci/update.html</a></p>

CC BY-SA 4.0
2021-01-26T13:13:43.520Z
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!
TedThomson
CC BY-SA 4.0
2021-01-26T16:35:23.200Z
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.
Joshua Grochow
CC BY-SA 4.0
2021-01-26T11:44:08.443Z
2021-01-26T11:44:08.443Z
Avi Tal
<p>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</p>

CC BY-SA 4.0
2024-09-19T18:21:16.253Z
Is this really about improved algorithms, or just improved hardware? For the problem you mention from the 1980s, if they were trying to find the *exact* minimum, that is not really a fair comparison to what delivery companies now do (which, presumably, is to just find a "short enough" path, some kind of heuristic approximation).
Joshua Grochow
CC BY-SA 4.0
2024-09-22T12:00:53.867Z
@JoshuaGrochow It is exactly that probabilistic algorithm advance that made the computation so fast, and it turns out you can get arbitrarily close to the ultimate "optimal" answer so there is no practical difference. Computers have probably speeded up by 10^6 since the early TSP experiments, but it's the algorithms that crushed the problem. 38 cities was 38! A faster computer doesn't begin to solve the problem for 200 stops which is 200! brute force.
Dov
CC BY-SA 4.0
2021-01-27T19:41:07.017Z
2021-01-27T19:41:07.017Z
Dov
<p>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 <em>in the title</em>, but not as asked in the body?</p>

CC BY-SA 4.0
2021-01-28T02:15:54.320Z
2021-01-28T02:15:54.320Z
user1521620
<p>Counting perfect matches in plannar graphs is a good example for exponential speed up but I think it doesn't  meet the first condition.</p>

CC BY-SA 4.0
2021-01-27T23:03:33.863Z
2021-01-27T23:03:33.863Z
Mohsen Ghorbani
<p>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:</p>
<ol>
<li>The original algorithms, despite being hopelessly intractable (e.g. exponential or high-degree polynomial), were considered breakthroughs at the time by the TCS community;</li>
<li>Since then, extremely efficient (e.g. provably linear or sublinear, maybe sub-quadratic) algorithms have been developed <em>and</em> are used in practice.</li>
</ol>
<p>So, 1) precludes algorithms which <em>have</em> 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).</p>
<p>In other words, have we gone from problems that were considered theoretical curiosities to practical, usable algorithms that are widely adopted in practice?</p>

CC BY-SA 4.0
2021-01-26T13:08:03.723Z
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.
Laakeri
CC BY-SA 4.0
2021-01-26T15:57:54.600Z
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.
SagarM
CC BY-SA 4.0
2021-01-26T18:26:40.000Z
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 Schultz-Wu
CC BY-SA 4.0
2021-01-26T19:10:28.183Z
@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?
TedThomson
CC BY-SA 4.0
2021-01-27T17:01:21.577Z
I don't know enough of the history for a specific example, but it is likely that the [Robertson-Seymour theorem](https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem) is a source for such examples. This theorem shows that a great many properties of graphs have polynomial-time algorithms, but in many cases of interest (e.g. toroidal graphs) it is of no help in actually finding an efficient algorithm. I don't know if there is any quotable example where the first known algorithm was just ruling out a known list of forbidden minors but then an efficient algorithm was found later.
John Coleman
CC BY-SA 4.0
2021-01-27T17:23:10.197Z
Also, perhaps the current state of the art isn't exactly efficient, but [deterministic primality testing](https://en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests) 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](https://cs.stackexchange.com/q/23260/76877) and so probabilistic tests are still preferred.
John Coleman
CC BY-SA 4.0
2021-01-29T10:53:51.427Z
Does the current state of fully homomorphic encryption count as "extremely efficient"?
Clement C.
CC BY-SA 4.0
2021-02-01T14:51:30.263Z
@ClementC. I am not familiar enough with this topic to opine, but the answers below have taken some liberties regarding my initial definition of "extremely efficient" (for the better, IMO), so feel free to add your thoughts!
TedThomson
<cc.complexity-theory><ho.history-overview><exp-time-algorithms>
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
TedThomson
# Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient

(Asked by: username_0 on 2021-01-26)

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?

**Tags:** cc.complexity-theory, ho.history-overview, exp-time-algorithms

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_3**: 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).  
> **username_0**: @username_2: 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?  
> **username_4**: I don't know enough of the history for a specific example, but it is likely that the [Robertson-Seymour theorem](https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem) is a source for such examples. This theorem shows that a great many properties of graphs have polynomial-time algorithms, but in many cases of interest (e.g. toroidal graphs) it is of no help in actually finding an efficient algorithm. I don't know if there is any quotable example where the first known algorithm was just ruling out a known list of forbidden minors but then an efficient algorithm was found later.  
> **username_4**: Also, perhaps the current state of the art isn't exactly efficient, but [deterministic primality testing](https://en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests) 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](https://cs.stackexchange.com/q/23260/76877) and so probabilistic tests are still preferred.  
> **username_5**: Does the current state of fully homomorphic encryption count as "extremely efficient"?  
> **username_0**: @ClementC. I am not familiar enough with this topic to opine, but the answers below have taken some liberties regarding my initial definition of "extremely efficient" (for the better, IMO), so feel free to add your thoughts!  

---

## 12 answers

### Answer by username_6 on 2021-01-26. Score: 22

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](https://doi.org/10.1090/jams/864): Hilbert originally proved that the invariant ring $\mathbb{C}[V]^{SL\_3}$ was finitely generated *non-constructively*. After Gordan's criticism, [Hilbert [1893]](http://www.ams.org/mathscinet-getitem?mr=1510781) 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](http://www.ams.org/mathscinet-getitem?mr=637618) and then [Derksen](http://doi.org/10.1090/S0002-9939-00-05698-7) combined with Gröbner basis puts it into $\mathsf{EXPSPACE}$. In [GCT V](https://doi.org/10.1090/jams/864), Mulmuley put this problem into time $n^{O(\log \log n)}$.


---

### Answer by username_7 on 2021-01-27. Score: 17

The task of [unification](https://en.wikipedia.org/wiki/Unification_(computer_science)#A_unification_algorithm) 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.

> **Comments:**
> **username_0**: 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?  
> **username_7**: @username_0, This paper has a nice section on the historical context: https://www.sciencedirect.com/science/article/pii/S0747717189800124/pdf?md5=5b4e45c4f83e593270e34740838f59db&pid=1-s2.0-S0747717189800124-main.pdf  

---

### Answer by username_8 on 2021-01-27. Score: 12

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>

> **Comments:**
> **username_9**: Good one re LLL! I hope to see some practical implementations/applications of Moser-Tardos sampling type algorithms.  

---

### Answer by username_9 on 2021-01-27. Score: 10

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 by username_10 on 2021-01-28. Score: 10

Until [Francis's](https://doi.org/10.1093/comjnl/4.3.265) [QR](https://doi.org/10.1093/imanum/drp012) [algorithm](http://doi.org/10.4169/amer.math.monthly.118.05.387) 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 by username_11 on 2021-01-26. Score: 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.

> **Comments:**
> **username_0**: 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.  
> **username_12**: @username_0 can you provide a link for complexity of nn learning such as reference for quadratic complexity?  

---

### Answer by username_13 on 2021-01-27. Score: 6

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.

> **Comments:**
> **username_14**: 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? :/  
> **username_14**: What algorithms are you talking about? It is just a change in the mathematical formula, which has now become more complex than before.  
> **username_13**: 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.  :-)  

---

### Answer by username_16 on 2021-01-26. Score: 5

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

[Fastest known deterministic algorithm for the undirected Graph Isomorphism problem](https://cstheory.stackexchange.com/questions/25667/fastest-known-deterministic-algorithm-for-the-undirected-graph-isomorphism-probl)

and here:

[https://people.cs.uchicago.edu/~laci/update.html](https://people.cs.uchicago.edu/%7Elaci/update.html)

> **Comments:**
> **username_0**: 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!  
> **username_6**: 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.  

---

### Answer by username_15 on 2021-01-28. Score: 4

The [ideal membership problem](https://en.wikipedia.org/wiki/Hilbert%27s_Nullstellensatz#Effective_Nullstellensatz): 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).

> **Comments:**
> **username_6**: For the general ideal membership problem, where the RHS is not 1 but is another polynomial $h$ given as input, doubly-exponential is in fact a tight degree lower bound. The singly-exponential degree bound works more generally than in the problem you defined: it works for the *radical* ideal membership problem. Namely, given $f_1, \dotsc, f_s,h$, is there some power of $h$ that is in $\langle f_1, \dotsc, f_s \rangle$?  

---

### Answer by username_17 on 2021-01-27. Score: 3

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

> **Comments:**
> **username_6**: Is this really about improved algorithms, or just improved hardware? For the problem you mention from the 1980s, if they were trying to find the *exact* minimum, that is not really a fair comparison to what delivery companies now do (which, presumably, is to just find a "short enough" path, some kind of heuristic approximation).  
> **username_17**: @JoshuaGrochow It is exactly that probabilistic algorithm advance that made the computation so fast, and it turns out you can get arbitrarily close to the ultimate "optimal" answer so there is no practical difference. Computers have probably speeded up by 10^6 since the early TSP experiments, but it's the algorithms that crushed the problem. 38 cities was 38! A faster computer doesn't begin to solve the problem for 200 stops which is 200! brute force.  

---

### Answer by username_18 on 2021-01-28. Score: 2

Like the TSP (Travelling Salesman Problem) @username_17 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 by username_19 on 2021-01-27. Score: 1

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


---

