I consider myself a computer science (CS) theoretician, but Wikipedia describes me as a “mathematician and computer scientist.”a So, what am I? To answer that question, we must consider theoretical computer science (TCS), which Wikipedia defines as “a subfield of computer science and mathematics that focuses on the abstract mathematical foundations of computation.”b I’d like to take issue with this definition.
In his lovely 2019 book, Mathematics and Computation,c 2023 ACM A.M. Turing Award recipient Avi Wigderson defines the theory of computation as “the study of the formal foundations of computer science and technology.” This is a very broad definition, but the scope of the book does not match that definition. It offers a very U.S.-centric view of TCS. As I have written elsewhere,d U.S. TCS has a quite narrower scope than European TCS, which I find unfortunate.
I believe that Avi has the right and broad definition for theoretical computer science; it is “the study of the formal foundations of computer science and technology.” In fact, if one browses 1970s proceedings of the ACM Symposium on the Theory of Computing (STOC) and the IEEE Symposium on Foundations of Computer Science (FOCS), one sees indeed a very broad conception of TCS. Only in the 1980s, with the proliferation of the so-called “satellite conferences,” dedicated to topics such as databases, program verification, and the like, did the scope of STOC and FOCS narrow, which led to a narrowing of how TCS is viewed in the U.S.
Regardless of the breadth of TCS, the question remained as to whether it is a subfield of mathematics. Undoubtedly, TCS is abstract and mathematical, but is it mathematics? For that matter, what is mathematics? Mathematics is notoriously hard to define, so I prefer the sociological definition: Mathematics is what mathematicians do. In 1993, as a young computer science theoretician, I was offered a faculty position in the CS department at Rice University. I doubt I would have received such an offer from the math department at Rice. Avi is one of a handful of computer science theoreticians worldwide with a primary position in a department of mathematics. I must conclude that TCS is not a branch of mathematics, at least sociologically.
But my objection to “TCS is a branch of mathematics” is deeper than the sociological argument. I believe that thinking of TCS as a branch of mathematics is harmful to the discipline. The centrality of computing stems from the fact that it is a technology that has been changing the world for the past 80 years, ever since the British used early computing to change the tide of war in World War II. As computer scientists, we should look for inspiration from physics rather than from mathematics. Theoretical physics is highly mathematical, but it aims to explain and predict the real world. Theories that fail at this “explain/predict” task would ultimately be discarded. Analogously, I’d argue that the role of TCS is to explain/predict real-life computing. I am not saying that every TCS paper should be held to this standard, but the standard should be applied to branches of TCS. We should remember the warning of John von Neuman,e one of the greatest mathematicians and computer scientists of the 20th century, regarding the danger of mathematics driven solely by internal esthetics: “There is a grave danger that the subject will develop along the line of least resistance.”
Consider, for example, computational-complexity theory—the main focus of Avi’s book—which I find to be the most elegant theory in CS. The theory focuses on classifying computational problems according to their resource usage, usually time and space. One of the crown jewels of that theory is the concept of NP-completeness, which crystalizes the difference between checking solutions and finding solutions. The paradigmatic NP-complete problem is the Boolean Satisfiability Problem (SAT), which asks whether a given Boolean formula, with Boolean gates such as AND and NOT, has some assignment of 0s and 1s to its input variables such that the formula yields the value 1. When Cook proved in 1971 that SAT is NP-complete, the problem was considered computationally hard.
Over the past 30 years, however, we have madef tremendous progress in SAT solving, which is today an industrial reality. NP-completeness theory, however, does not explain or predict the unreasonable effectiveness of SAT solvers. In spite of recent effortsg to go beyond worst-case complexity, this approach is still the prevalent approach to computational-complexity analysis, but it shed little light on “real-word complexity.”
So, I do not consider myself a mathematician. I am squarely in the computer science camp.
Join the Discussion (0)
Become a Member or Sign In to Post a Comment