There is an interesting result in complexity theory that shows that the obvious greedy algorithm for the minimum set cover problem (add the element that increas

There is an interesting result in complexity theory that shows that the obvious greedy algorithm for the minimum set cover problem (add the element that increases your coverage the most, repeat) is essentially the best-possible polynomial time approximation. This sometimes causes people to use the greedy algorithm and think they can't do better. But this result is about the worst case approximation quality-- the quality on pathological inputs. On ordinary inputs the greedy algorithm by itself is not that great and can easily be outperformed by algorithms with heuristics that anyone can come up with after thinking about the problem for a bit. Heuristics with polynomial complexity just don't improve the worst case performance. I think this is just a more narrow case of the same underlying error: Taking an interesting yet often rather narrow and academic result and assuming it applies more generally. I suspect it's exacerbated by researchers talking up the significance of their work. I suspect it's also partially a result of the fact that an answer can be surprising and worth study yet still not very useful. The fact that we can say much at all about the space of all possible polynomial time algorithms is very surprising, but it's much more surprising than it is practically useful. The main points I tell people: Results from complexity theory are usually about best and worst cases, practice usually cares much more about typical cases (which might be application constrained to never be pathological). Results from complexity theory are usually about exact solutions, usually a good approximation is all that we need or it's fine to solve the problem exactly most of the time buy give a bad result in a rare case. Many problems are actually small enough they can be exhaustively checked. Many problems are large enough that only a very rough approximation will ever meet the timing requirements (so just because you have a polytime algorithm it might not help). All these factors mean that while it can be useful to know the limits, they often don't matter.