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

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.

## 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:

• Brynmor Chapman, brynmor (at mit dot edu)
• Dylan McKay, dmmckay (at mit dot edu)

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

Office hours:

• Ryan: Wednesday 10:30am-12pm, 32-G638
• Brynmor: Monday 4pm-6pm, Building 32, G5 lounge (next to 5th floor elevators)
• Dylan: Tuesday 4pm-6pm, Building 32, G5 lounge (next to 5th floor elevators)

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

Textbook:

• Michael Sipser, Introduction to the Theory of Computation (3rd Edition), Thomson
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%.
• Homeworks/psets will come out on Wednesdays (except when an exam falls on the next week) and will be due the following Wednesday at 11.59 pm. Late assignments will not be accepted. To account for this, we will drop the lowest homework grade in computing your final grade. If you are unable to submit your homework because of extenuating circumstances such as a family/medical emergency, please have S^3 contact Ryan or the TAs about it (ASAP).

Most of the work in this course will be mathematical proofs of various cool facts. Your proofs should be as clear as possible. Note, this does not mean your proofs should be long -- in fact, typically, good clear explanations are also short!

• Policy on Collaboration: This is very important; please read carefully. We believe that the best learning often happens when you work with others, and we want to encourage that. But it is equally important that you try to learn on your own! So here are our rules for collaboration on homework:
• You must think about all homework problems on your own and do your very best to find the solutions yourself, before discussing/collaborating with other students. After failing to find the answers yourself, you may discuss homework problems with other students, and work in groups on the remaining questions.
• You must not look for solutions on the web. Instead, ask us questions if/when you get stuck.
• Cite properly! If you work in a group, include the names of the other people in the group in your written solution. In general, if you do receive a significant idea from someone or somewhere, you must acknowledge that person/book/website in your solution.
• You must write up your own solution to every problem; you may not copy answers from another student, or any other source. Also, you may not show your answers to another student. Failing to follow this rule may constitute plagiarism.
Deviating from the above rules may result in violation of MIT policies. If you have any questions about our policy, please don't hesitate to send a private note to the course staff on Piazza.

• How to write/submit homework: Via Gradescope. To be announced.

• For all homework questions (that do not give away solutions!), please post to piazza.com/mit/spring2010/6045/home or come visit us at office hours. You can also send private questions (to TAs and instructors only) using Piazza.

## Lectures

Slides are posted here, shortly after lectures.

SO FAR:

1. 02/04 Introduction and course summary; DFAs
Slides: [color pdf] [grayscale pdf]

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

3. 02/11 Regular expressions; Equivalence of automata and regular expressions
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

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
Slides: [before class, color pdf] [color pdf]

11. 03/10 Diagonalization, Undecidability, and Reductions
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
Slides: [color pdf]

17. 04/09 $P$ and $NP$
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
Slides: [color pdf]

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

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

24. 04/30 $PSPACE$-complete problems and Complexity of Games
Slides: [color pdf]

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

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

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

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