Why Study Complexity Theory?

Question

I’m an amateur in the study of algorithms. For a while I’ve had a burning question, why do we study complexity theory in computer science? The reason I ask is because algorithms with better asymptotic complexity are not always faster for practical purposes, in fact they can be absurdly slower. Why not instead develop a theory that better suits the practical needs of scientific research and industry?

As an example, it is known that developing an algorithm to determine a perfect chess game can be done in $O(1)$, as the number of legal chess games on an 8×8 grid is bounded from above. However, I have heard this algorithm would take longer than the age of the universe to terminate. This begs the question, why complexity theory? It seems to me the field is fundamentally flawed, and computer scientists should be using a better approach for the study of algorithms.

(Note: My sincere apologies to researchers in the field. ☻)

Answer 1

This is not a simple question, and you shouldn't expect a simple answer. There are a range of similar questions in this space: why do we study asymptotic running time? why do we use asymptotic running time analysis to analyze algorithms? why do we study complexity theory? Each of those has multiple answers; there is not just a single reason why we do it, and different people may have different reasons.

Asymptotic running time analysis has advantages and disadvantages. You've accurately identified one of the disadvantages: a good asymptotic running time doesn't guarantee good running time in practice. But if you focus on only a single advantage or disadvantage you're not going to get the full picture of the strengths and weaknesses of that style of analysis. Some of the advantages are that analysis is relatively tractable, it is not specific to a particular architecture, it provides useful information about scalability, and at least some of the time it has useful predictive power at identifying algorithmic bottlenecks. For instance, the difference between a $O(n^2)$ time algorithm and a $O(n \log n)$ time algorithm can often be significant, even if we are ignoring the constant factors. Some of the disadvantages are that constant factors can be important, cache and memory hierarchy effects can be very important yet are ignored by asymptotic running time analysis, and (like any metric) optimizing solely for asymptotic running time can lead to absurd results of little practical utility (see galactic algorithms and Goodhart's law).

I think it's also useful to examine the alternative. I encourage you to explore the alternative to asymptotic running time analysis and work through what you'd propose in its stead. If you don't try to come up with a concrete proposal, it's easy to assume that it can't be that hard to find something better... but when you're forced to commit to something specific, you might discover that it's more challenging than you anticipated. For instance, I encourage you to familiarize yourself with Knuth's analysis of algorithm running time on MIX in his TAOCP series. There he does concrete running time analysis, with no asymptotics, taking into account the constant factors. If you force yourself to work through the details of that, you'll quickly discover the disadvantages of that: it's super-tedious, very specific to a particular computer architecture, and often not much more enlightening.

We could similarly discuss each of the other topics - e.g., why or why not to study complexity theory - and you'd find that they too have nuances.

I also want to highlight for you that the theory and algorithms community is a broad one, with a range of different styles of work. You seem to be lumping it all together into one pile, but there's a spectrum of work: some of it is super-theoretical and far afield from practice, some of it is highly practical and motivated by concrete problems and may have immediate impact, and there is a range of work at various point in between those extremes. I think it's important to understand that there is some work in the theory community that is of great practical relevance or has had major impact, just as there is work that much more theoretical and not motivated by near-term impact.

Since you asked for theoretical frameworks that are focused on meeting industry's needs, you might also be interested in the Word RAM model, cache-oblivious algorithms, and the parallel external memory model.

I strongly encourage you to read the following resources, as they are closely related to your question: Why polynomial time is called "efficient"?, Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms, Justification for neglecting constant factors in Big O.