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:
- The original algorithms, despite being hopelessly intractable (e.g. exponential or high-degree polynomial), were considered breakthroughs at the time by the TCS community;
- 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?