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

ryan's classy diagram

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


Announcements on Piazza

Introduction

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

Instructor:

TAs:

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!

Textbook:

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:


Lectures

[Jump to What's Ahead]

Slides are posted here, shortly after lectures.

SO FAR:

  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]

  5. 02/18 YOUR MONDAY CLASS GOES HERE -- NO 6.045 TODAY


    WHAT'S AHEAD

  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] [grayscale 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: [color pdf] [grayscale pdf]

  8. 02/27 More on Streaming Algorithms; start Communication Complexity
    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: [color pdf] [grayscale pdf]

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

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

  11. 03/10 Diagonalization, Undecidability, and Reductions
    Readings: Sipser 5.3, 6.3
    Slides: [color pdf] [grayscale pdf]

  12. 03/12 More on Undecidability via Reductions, Rice's Theorem
    Readings: Sipser 6.1, another take on Rice's theorem
    Slides: [color pdf] [grayscale pdf]

  13. 03/17 Oracles, Self-Reference, and the Recursion Theorem
    Readings: Sipser 6.2
    Slides: [color pdf] [grayscale pdf]

  14. 03/19 Midterm (During class time! --- Room TBD)

    03/24 and 03/26 SPRING BREAK -- NO CLASS

  15. 03/31 Computability and the Foundations of Mathematics
    Readings: Luca Trevisan's notes on computability and logic
    Slides: [color pdf] [grayscale pdf]

  16. 04/02 Kolomogorov Complexity
    Readings: Sipser 6.4
    Slides: [color pdf] [grayscale pdf]

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

  18. 04/09 $P$ and $NP$; Polynomial-Time Reductions
    Readings: Sipser 9.1, 7.3, 7.4
    Slides: [color pdf] [grayscale pdf]

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

  20. 04/16 $NP$-completeness of clique, vertex cover, independent set, subset sum, knapsack
    Readings: Sipser 7.5, Luca Trevisan's notes
    Slides: [color pdf] [grayscale pdf]

  21. 04/21 NP-completeness of partition and bin packing, $coNP$ and Friends
    Readings: Sipser 7.5, 9.2
    Slides: [color pdf] [grayscale pdf]

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

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

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

  25. 05/05 Randomized Algorithms and Complexity ($RP$ and $BPP$)
    Readings: Sipser 10.2
    Slides: [color pdf] [grayscale pdf]

  26. 05/07 More on Randomized Complexity, Summary
    Readings: Sipser 10.2
    Slides: [color pdf] [grayscale pdf]

  27. 05/12 TBD (Ask Me Anything? Quantum Computing? Learning Theory?)
    Readings: TBD
    Slides: [color pdf] [grayscale pdf]

  28. Study for the final exam!


Homework

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.


Exams

Midterm: The midterm will be in-class, tentatively scheduled for Thursday, March 19 during class time (room TBD). 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: TBD. For this exam, we will allow one double-sided sheet of notes; otherwise, the exam is closed-book.