Tag Info

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

18

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.

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

10

Cobham's thesis is essentially the Extended Church-Turing thesis. Historians of computer science have gone back and figured out who first proposed it, and attached his name to it. What Cobham was actually talking about in his paper "The Intrinsic Computational Difficulty of Functions" [Proc. 1964 Congress for Logic, Methodology, and the Philosophy ...

10

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.

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

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

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.

5

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

4

Development of ML began circa 1973, but I can't find a published description of it earlier than POPL'78. As far as I can tell, it didn't have modules at that time. It did have abstype, which it likens to "SIMULA classes, CLU clusters, and ALPHARD forms", which "are by now well-known". CLU wasn't the first language to have any form of data ...

4

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

2

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

2

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

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.

Only top voted, non community-wiki answers of a minimum length are eligible