| "the particular work" he is referencing is computational complexity theory; a long-running attempt to mathematically characterize which problems can be efficiently solved with computers and which cannot. I work in complexity theory, and this does make the objects of his criticism obvious to me. I'll try to explain below. 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... |
I still don't get it, because it's okay for some people to be working on purely theoretical problems, motivated by mathematical curiosity and aesthetics. Is there a lack of people working on more concrete problems, bridging the gap between theory and practice? Are there outstanding problems arising from practice that are ignored because supposed "applied" researchers don't actually care about applications?
I think this criticism is a little strange, because most complexity theorists also work on "average-case" complexity
That sounds almost as theoretical as worst case to me. I would expect "applied" complexity theory to provide a theoretical framework for how a practitioner can add information that they know about how their problem differs from the aesthetically ideal problems that arise in theory. Like, my factory floor is not a frictionless plane, aha, here's how you measure a "coefficient of friction," and here's a new equation where you can see how the coefficient of friction affects the results. Or, my dataset isn't a uniformly random blob of bits, so is there a statistical property I can measure that lets me estimate the probability of the working memory of my algorithm exceeding 2.4 times the size of the input size?