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.

14

Albert R. Meyer and Larry J. Stockmeyer introduced the polynomial hierarchy in 1972 with their paper "the equivalence problem for regular expressions with squaring requires exponential space". The class $\Pi_1^P$ in there is of course coNP. Stockmeyer wrote a full paper on the polynomial hierarchy (TCS 1977) which also uses the notation coNP.

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

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.

9

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

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.

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

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

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

This result is included in Ore's book The Four-Colour Problem (see Theorem 7.4.3). I saw a paper that states this as a folklore result and cites Ore. Interestingly, the book gives a different proof for (ii)$\implies$(i). It seems that at that time, it wasn't known that the mapping $f\longmapsto f^*$ is a bijection. Sorry to disappoint; but that's the best I ...

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