But complexity theory aims at describing the performance of A over the space of all problem instances and it does so by abstracting away from individual problem instances. I appreciate the effort to extend the story into CS, but I wonder if you have to be familiar with the particular work he's alluding to. The charge (as leveled against theoretical physics) is not that some people do pure mathematical work for the sa…
Think of "problems" as abstract primitives: sorting, search, graph operations, optimization, etc. To give a concrete example, let's take a particular search problem: boolean satisfiability (SAT). The input is boolean formulas, and the output is "an assignment to the variables of this formula that make it TRUE."
Some problems are "NP-complete". The definition of NP isn't important for our discussion here. What is important is that NP-completeness or lack thereof is indeed a "beautiful" way to classify problems. Further, we expect NP-complete problems to be impossible to solve efficiently on every input. This is what the article means by "worst-case" or "overly pessimistic" theories.
SAT is NP-complete, so "classical complexity" would predict that SAT cannot be efficiently solved with computers. But often, SAT can be solved efficiently "in practice" using simple heuristics. So Moshe would say that classical complexity is simply wrong; it doesn't describe the "real-world" behavior of actually trying to solve SAT. While difficult-to-process formulas may exist, we "just happen" to only encounter easy-to-process formulas.
So, to summarize: the article criticizes researchers who focus only on worst-case complexity. While the theory is beautiful, we can point to many problems for which it does not accurately predict performance.
I think this criticism is a little strange, because most complexity theorists also work on "average-case" complexity; the study of when "typical" inputs are difficult vs easy to solve. This is mentioned at the very end of the article. Any working complexity theorist would immediately list these problems with worst-case complexity, and explain that it is an imperfect and primitive theory compared to how we would really want to understand when and how these problems are difficult. There is a great deal of work trying to understand what about each formula makes it difficult or easy to process, and why.
The issue is, we are nowhere near understanding even worst-case complexity. So theoretical research often toggles back and forth between the two settings, trying to make progress overall.
Computational complexity theory is a fundamental mathematical field that will only occasionally produce enough understanding to impact practice. For an example, see:
https://www.youtube.com/watch?v=FGtsqEwANWY&feature=youtu.be...