6.045 - Automata, Computability, and Complexity Theory - Spring 2020

ryan's classy diagram

[General Info]   [Lectures]   [Homeworks]   [Exams]

Announcements on Piazza

MathJax check: If you see a fancy equation here $$NP = \bigcup_k NTIME[n^k]$$ then the math on this page is working. If you don't, then you probably disabled JavaScript or your browser is wack. Sorry.


What is computation? Given a definition of 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? This course provides a mathematical introduction to these questions. In many cases we can give completely rigorous answers; in other cases, these questions have become major open problems in both pure and applied mathematics!

By the end of this course, students will be able to classify computational problems given to them, in terms of their computational complexity (Is the problem regular? Not regular? Decidable? Recognizable? Neither? Solvable in P? NP-complete? PSPACE-complete?, etc.) They will also 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: 6.042 or equivalent mathematical maturity.

General Information



Class: Tuesday and Thursday 2:30-4:00, 32-155

Office hours:

Rather than emailing questions directly to the teaching staff, please post your questions on Piazza. If you have any problems or feedback for the developers, email team@piazza.com (and feel free to cc rrw).

Sign up with Piazza to stay updated on the course!


Note: the 2nd edition of Sipser is also fine for this course, if you can find it cheaper!

Grading: Midterm exam: 25%, Final exam: 35%, Homework: 40%.

Problem Sets:


[Jump to What's Ahead]

Slides are posted here, shortly after lectures.


  1. 02/04 Introduction and course summary; DFAs
    Readings: Sipser, Chapter 0, 1.1
    Slides: [color pdf] [grayscale pdf]

  2. 02/06 DFAs and NFAs, equivalence of DFAs and NFAs
    Readings: Sipser 1.1, 1.2
    Slides: [color pdf] [grayscale pdf]

  3. 02/11 Regular expressions; Equivalence of automata and regular expressions
    Readings: Sipser 1.3
    Slides: [before class, color pdf] [color pdf] [grayscale pdf]

  4. 02/13 Finish up regexps; Proving languages are not regular
    Readings: Sipser 1.4, Sipser Problem 7.40 in 2nd ed (7.25 in 3rd ed) and its solution
    Slides: [before class, color pdf] [color pdf] [grayscale pdf]


  6. 02/20 DFA Minimization
    Readings: Sipser Problem 1.52 in 2nd ed (1.48 in 3rd ed) and its solution
    Slides: [before class, color pdf] [color pdf]

  7. 02/25 The Myhill Nerode Theorem; Streaming Algorithms: Small Algorithms for Big Data
    Readings: Our lecture notes, some lecture notes on streaming algorithms
    Slides: [before class, color pdf] [color pdf]

  8. 02/27 More on Streaming Algorithms
    Readings: Some lecture notes on streaming algorithms
    [Optional reading] A Communications of the ACM and an Encyclopedia of Algorithms article on finding frequent elements
    Slides: [before class, color pdf] [color pdf]

  9. 03/03 Communication Complexity; Turing Machines
    Readings: Some lecture notes on communication complexity
    Sipser Chapter 3, and Turing's amazing paper (also here)
    [Optional reading] A survey on communication complexity
    Slides: [before class, color pdf] [color pdf]

  10. 03/05 Church-Turing Thesis, Decidability and Recognizability
    Readings: Sipser 4, 5.1, 5.2
    Slides: [before class, color pdf] [color pdf]

  11. 03/10 Diagonalization, Undecidability, and Reductions
    Readings: Sipser 5.3, 6.3
    Video: see piazza for a link
    Slides: [before class, color pdf] [color pdf]

  12. 03/12 Fun With Undecidability: Oracles and Busy Beavers
    Readings: Sipser 6.1, another take on Rice's theorem
    Video: see piazza for a link
    Slides: [before class, color pdf] [color pdf]

  13. 03/17, 03/19, 03/24, 03/26 YOUR "VERY LONG SPRING BREAK" -- NO CLASS

  14. 03/31 "Deep Computability": The Recursion Theorem and the Foundations of Mathematics
    Readings: Sipser 6.2, Luca Trevisan's notes on computability and logic
    Slides: [color pdf]

  15. 04/02 MIDTERM

  16. 04/07 Time Complexity and the Time Hierarchy Theorem
    Readings: Sipser 7.1, 7.2, 9.1
    Slides: [color pdf]

  17. 04/09 $P$ and $NP$
    Readings: Sipser 9.1, 7.3, 7.4
    Slides: [color pdf]

  18. 04/14 Polynomial-Time Reductions, the Cook-Levin Theorem, and $NP$-completeness
    Readings: Sipser 7.4, 7.5, an alternate proof of the Cook-Levin Theorem
    Slides: [color pdf]

  19. 04/16 $NP$-completeness of Clique, Vertex Cover, Independent Set, Subset Sum, Knapsack
    Readings: Sipser 7.5, Luca Trevisan's notes
    Slides: [color pdf]

  20. 04/21 NP-completeness of Partition and Bin Packing, $coNP$ and Friends
    Readings: Sipser 7.5, 9.2
    Slides: [color pdf]

  21. 04/23 Oracles in Complexity Theory, $P^{NP}$, $NP^{NP}$, $coNP^{NP}$
    Readings: Sipser 9.2
    Slides: [color pdf]


  23. 04/28 Space Complexity, $PSPACE$ and $EXPTIME$, $PSPACE = NPSPACE$
    Readings: Sipser 8.1, 8.2, 8.3
    Slides: [color pdf]

  24. 04/30 $PSPACE$-complete problems and Complexity of Games
    Readings: Sipser 8.1, 8.2, 8.3
    Slides: [color pdf]

  25. 05/05 Finish PSPACE, start Randomized Algorithms and Complexity
    Readings: Sipser 10.2
    Slides: [color pdf]

  26. 05/07 More on Randomized Complexity, Review of 6.045
    Readings: Sipser 10.2
    Slides: [color pdf]

  27. 05/12 Ask Me Anything, Zoom Style
    Readings: None. Just come with questions!

  28. Study for the final exam!


Homework comes out on Wednesdays and will be due on the following Wednesday at 11:59pm. You are required to compose your homeworks in some word processor (LaTeX is preferred); we will provide source code to help you get started. For more details, read the information on Problem Sets.

Homeworks (and directions on how to submit them) will be posted on piazza.


Midterm: The midterm will be online (???), tentatively scheduled for Thursday, April 2 during normal class time. For this exam, we allow one single-sided sheet of notes (on the usual 8.5x11 letter paper); otherwise, the exam is closed-book.

IMPORTANT: If you have a conflict with the midterm time, please email the entire course staff (Ryan, Brynmor, Dylan) with the subject line "Midterm Conflict". We'll schedule a conflict midterm as needed.

Final Exam: Room 50-340, Fri 05/15/2020, 1:30 PM–4:30 PM. For this exam, we will allow one double-sided sheet of notes; otherwise, the exam is closed-book.
Please contact us if you can't make this time and you are in a significantly different time zone (more than 3 hours different from Eastern time). We will work with you to find another time for your final exam.