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 sheds little light on “real-world complexity.”
So, I do not consider myself a mathematician. I am squarely in the computer science camp.
Physics (or any natural sciences) views the world as a “machine” whose laws it seeks to discover. Computing can be viewed as being complementary to Physics in that it imagines “laws” and asks if we can have a machine that behaves accordingly. Both can be seen to use Mathematics to acquire the necessary precision towards their respective goals. With that symmetry between natural sciences and computing, I find it useful to view TCS as the use of formal thinking to conceive mechanical behaviors, express them to some universal machine and run them. And then: Experimental Physics and Software Testing suddenly appear to be identical at the core.
Before asking what is Theoretical Computer Science, maybe we should get clear definition for the “Computer Science” itself? For me, Computer Science is the science to enable humans to control von Neuman computers and make them do what we want them to do. Maybe also other computers, but I still did not see real application of quantum ones.
If we take that definition, then Theoretical Computer Science is indeed much more than the Math, which stand behind it. For example, it includes a lot of things about cognitive load, natural (by humans, not machines) language processing, etc.