https://cacm.acm.org/opinion/what-is-theoretical-computer-science/ Skip to content Explore Topics * Architecture and Hardware * Artificial Intelligence and Machine Learning * Computer History * Computing Applications * Computing Profession * Data and Information * Education * HCI * Philosophy of Computing * Security and Privacy * Society * Software Engineering and Programming Languages * Systems and Networking * Theory Latest Issue October 2024 CACM cover Latest Issue October 2024, Vol. 67 No. 10 Previous Issue September 2024, Vol. 67 No. 9 Explore the archive Search Open Membership Navigation * Settings * My Topics * Bookmarked Articles * Sign Out Sign In Join ACM [ ] Topics * Architecture and Hardware * Artificial Intelligence and Machine Learning * Computer History * Computing Applications * Computing Profession * Data and Information * Education * HCI * Philosophy of Computing * Security and Privacy * Society * Software Engineering and Programming Languages * Systems and Networking * Theory Sections * Research and Advances * Opinion * Practice * News * Careers Magazine * Latest Issue * Magazine Archive * Editorial Staff and Board * Submit an Article * Alerts & Feeds * Author Guidelines CACM Web Account Membership in ACM includes a subscription to Communications of the ACM (CACM), the computing industry's most trusted source for staying connected to the world of advanced computing. Sign In Sign Up Communications of the ACM * About Us * Frequently Asked Questions * Contact Us Follow Us * CACM on Twitter * CACM on Reddit * CACM on LinkedIn Opinion Theory What Is Theoretical Computer Science? Thinking of theoretical computer science as a branch of mathematics is harmful to the discipline. By Moshe Y. Vardi Posted Oct 7 2024 Moshe Y. Vardi * Share + Twitter + Reddit + Hacker News * Download PDF * Print * Join the Discussion * View in the ACM Digital Library + Footnotes 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 20^th 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 made^f 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 efforts^g 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. Footnotes + a See https://bit.ly/3BlT37S + b See https://bit.ly/3N3bUao + c See https://bit.ly/3XEUkOR + d See https://bit.ly/4dq3lBg + e See https://bit.ly/3XKLe3f + f See https://bit.ly/47FpU3z + g See https://bit.ly/4dw5yv6 About the Authors Moshe Y. Vardi (vardi@rice.edu) is University Professor and the George Distinguished Service Professor at Rice University, Houston, TX, USA, where he is also a Fellow at the Baker Institute for Public Policy. He is a former Editor-in-Chief of Communications. * Share + Twitter + Reddit + Hacker News * Download PDF * Print * Join the Discussion Submit an Article to CACM CACM welcomes unsolicited submissions on topics of relevance and value to the computing community. You Just Read What Is Theoretical Computer Science? View in the ACM Digital Library (c)ACM 0001-0782/24/09 DOI 10.1145/3698060 Related Reading * Opinion Lost in Math? Data and Information * Opinion Theory Without Experiments: Have We Gone Too Far? Computing Applications * Opinion Why Did Computer Science Make a Hero Out of Turing? Computing Applications * Opinion The Natural Science of Computing Computing Profession Advertisement [vc] Advertisement [vc] Join the Discussion (0) Become a Member or Sign In to Post a Comment Sign In Sign Up The Latest from CACM Explore More News Oct 18 2024 Dark Patterned Voices Manipulate Users R. Colin Johnson Artificial Intelligence and Machine Learning laptop computer with megaphone, illustration BLOG@CACM Oct 18 2024 Nobel Prizes and AI: The Promise, the Peril, and the Path Forward Marc Rotenberg Artificial Intelligence and Machine Learning entrance to the Nobel Prize Museum, Stockholm BLOG@CACM Oct 15 2024 The Software Sins of Bloat and Debt Robin K. Hill Computing Profession complex flowchart on a scale with OMG! on the display, illustration Shape the Future of Computing ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved. Get Involved Communications of the ACM (CACM) is now a fully Open Access publication. By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer. Learn More * CACM on Twitter * CACM on Reddit * CACM on LinkedIn Topics * Architecture and Hardware * Artificial Intelligence and Machine Learning * Computer History * Computing Applications * Computing Profession * Data and Information * Education * HCI * Philosophy of Computing * Security and Privacy * Society * Software Engineering and Programming Languages * Systems and Networking * Theory Magazine * Latest Issue * Magazine Archive * Editorial Staff and Board * Submit an Article * Alerts & Feeds * Author Guidelines Communications of the ACM * About Us * Frequently Asked Questions * Contact Us * For Advertisers * Join ACM (c) 2024 Communications of the ACM. All Rights Reserved. * Cookie Notice * Privacy Policy