EdusalsaDiscover Your Stanford

- autumn
- 2019-2020

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.

GER:DB-EngrAppSci

autumn

## LEC

Tuesday Thursday 10:30:00 AM - 11:50:00 AM @ Gates B3 with Omer Reingold

Graduate students may take for 3 units.

Already Have An Account? Log In

**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.

## Discussion

## To ask a question about a course and to share your perspective, signup or login