3
$\begingroup$

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. ☻)

$\endgroup$
7
  • 1
    $\begingroup$ Why study anything that is not of immediate value for practical needs? $\endgroup$ – Watercrystal Sep 8 '20 at 22:23
  • $\begingroup$ @Watercrystal Good point. Better phrased, why is complexity theory the primary tool for studying algorithms, when it clearly doesn’t do the best job of determining an algorithm’s performance? Why has it become so ubiquitous? $\endgroup$ – Raiyan Chowdhury Sep 8 '20 at 22:52
  • $\begingroup$ Also fields like mathematics or theoretical physics are interesting in their own right (even without considering applications), however, complexity theory has a particular goal in mind; improving algorithm performance. Why are computer scientists obsessed over improving complexity? Its complexity may say absolutely nothing about its actual performance. $\endgroup$ – Raiyan Chowdhury Sep 8 '20 at 22:59
  • 1
    $\begingroup$ Complexity theory is not about examining or improving algorithms; that field is called algorithmics (and a sizable number of people working in algorithmics work on practically efficient algorithms). CT is about proving lower bounds for the running time (or space usage, etc.) for any algorithm solving a specific problem (while algorithmics, if you will, provides upper bounds). Further, complexity theorists help understanding why certain problems are, in general, hard. $\endgroup$ – Watercrystal Sep 8 '20 at 23:13
  • 1
    $\begingroup$ The answer is hidden in the example given by you. How do we know that chess takes ages to optimize? It is the exactly the complexity theory that tells you. First complexity theory, algorithms, everything was part of one system. Later on, "whether it is possible or not possible" questions became deeper and deeper, and thus complexity theory was born. $\endgroup$ – Shreesh Sep 9 '20 at 3:47
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.