3 - 4 units
Letter or Credit/No Credit
This course provides a mathematical introduction to the following questions: What is computation? Given a computational model, what problems can we hope to solve in principle with this model? Besides those solvable in principle, what problems can we hope to efficiently solve? In many cases we can give completely rigorous answers; in other cases, these questions have become major open problems in computer science and mathematics. By the end of this course, students will be able to classify computational problems in terms of their computational complexity (Is the problem regular? Not regular? Decidable? Recognizable? Neither? Solvable in P? NP-complete? PSPACE-complete?, etc.). Students will gain a deeper appreciation for some of the fundamental issues in computing that are independent of trends of technology, such as the Church-Turing Thesis and the P versus NP problem. Prerequisites: CS 103 or 103B.
Pranav Rajpurkar is a PhD student in Computer Science at Stanford, working on Artificial Intelligence for Healthcare. He was previously a Stanford undergrad ('16).
Brad Girardeau got his B.S, M.S. degrees in computer science at Stanford ('16, '17). When not thinking about computer security, he can be found playing violin or running across the Golden Gate Bridge.