EdusalsaDiscover Your Stanford

CS 154

Introduction to Automata and Complexity Theory

  • autumn
  • 2018-2019

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

Course Prequisites

CS 154 is useful for


  • LEC

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

      Graduate students may take for 3 units.

Grade Distribution

Sign Up

To save CS 154 to your course bucketlist

Already Have An Account? Log In