| Lecture 01: | Course overview; beginning the formal definitions of computation. | Reading: Sipser Ch. 0.2. |
| Lecture 02: | Turing Machines. | Reading: Sipser Ch. 3.1, 3.3. |
| Lecture 03: | Simulations. | Reading: Sipser Ch. 3.2, 7.1 (ignore nondeterminism). |
| Lecture 04: | Time complexity and universal TMs. | Reading: Sipser Ch. 7.2 (up to "examples of problems in P"), 4.2 (ignore "Turing unrecognizability"). |
| Lecture 05: | Time Hierarchy Theorem. | Reading: Sipser Ch. 9.1. |
| Lecture 06: | Problems in P. | Reading: Sipser Ch. 7.2 (about PATH, and RELPRIME if you like). |
| Lecture 07: | SAT. | |
| Lecture 08: | NP. | Reading: Sipser Ch. 7.3 (ignore nondeterminism). |
| Lecture 09: | Nondeterminism. | Reading: Sipser Ch. 1.2; and, 3.2, 3.3 on nondeterminism. |
| Lecture 10: | Reductions. | Reading: Sipser first half of Ch. 7.4 (and also Ch. 5.3 if it helps). |
| Lecture 11: | NP-completeness and the Cook-Levin Theorem. (Guest lecturer Yu Zhao.) |
Reading: Sipser Ch. 9.3 and rest of Ch. 7.4. |
| Lecture 12: | NP-completeness reductions. (Guest lecturer David Witmer.) |
Reading: Sipser Ch. 7.5. |
| Lecture 13: | Search-to-decision, padding, dichotomy theorems. | |
| Lecture 14: | Ladner's Theorem and Mahaney's Theorem. | |
| Lecture 15: | coNP. | |
| In-class midterm. | Instructions and practice. | |
| Lecture 16: | Space complexity. | Reading: Sipser Ch. 8.0, 8.1 (just about L), 8.2. |
| Lecture 17: | Savitch's Theorem and NL. | Reading: Sipser Ch. 8.1 (remainder), 8.4. |
| Lecture 18: | NL-completeness and log-space reductions. | Reading: Sipser Ch. 8.5. |
| Lecture 19: | From P-completeness to PSPACE-completeness. | Reading: Sipser Ch. 8.3, through PSPACE-completeness of TQBF. |
| Lecture 20: | The Immerman--Szelepcsényi Theorem. | Reading: Sipser Ch. 8.6. |
| Lecture 21: | Randomized complexity: RP, coRP, and ZPP. | Reading: Sipser Ch. 10.2 is relevant (skip Read-Once Branching Programs). |
| Lecture 22: | BPP. (Guest lecturer Venkatesan Guruswami.) |
Reading: Sipser Ch. 10.2 again. |
| Lecture 23: | The Polynomial Hierarchy. (Guest lecturer Anıl Ada.) |
Reading: You can look at Sipser Ch. 10.3, but we are covering it differently. |
| Lecture 24: | Oracle Turing Machines and PNP. | Reading: Sipser Ch. 6.3, first section of Ch. 9.2. |
| Lecture 25: | Interactive proofs: IP = PSPACE. | Reading: Sipser Ch. 10.4. |
| Lecture 26: | Beyond worst-case analysis. | Reading: Sipser Ch. 10.1 is slightly relevant. |
| Lecture 27: | Hardness within P. | |
| Lecture 28: | Why is P vs. NP difficult? | Reading: Sipser Ch. 9.2. |
| Final exam. | Instructions and practice. |
The course will overlap significantly with "Part 3: Complexity" of Sipser's textbook. Topics will include models of computation (Turing Machines, circuits, ...), time and space complexity; hierarchy theorems by diagonalization; P vs. NP; theorems of Ladner, Mahaney, Savitch, Immerman-Szelepcsényi; randomized computation; and, the polynomial-time hierarchy. We will also cover some non-traditional topics of current research interest, such as the Exponential Time Hypothesis, Feige's Hypothesis, and fine-grained complexity.
As in theoretical courses such as 15-251, this class emphasizes writing clear and correct mathematical proofs. Sipser's book uses a nice "2-part format" for proofs: It begins with a 1-paragraph "high-level idea" of the proof; then the second part gives the full proof details. I highly recommend you follow the same strategy for your homework proofs! Please note that sometimes in class, I may only present some of the full details ("second part") of a proof. However it is expected that your homework solutions will contain full proof details.
30%: 11 Homeworks, lowest homework score dropped. Late-day policy described below.
30%: In-class Midterm, Thursday March 9
40%: Final Exam
Your well-being and happiness is very important to us at CMU, and there are many resources to help you with it. Please contact me directly if you need assistance or would like to talk about any such issues.
You must complete all homework problems by yourself.
You may:
All homework will be submitted using Gradescope. Please your andrew id as your identifier. If you have not been enrolled into the course on Gradescope, please contact us on Piazza. Your homework must be submitted as a pdf (each problem on a separate page or pages). You can use LaTeX or another math-document-editor to produce your homework pdf, or you can photograph/scan handwritten solutions. Here are instructions for submitting to Gradescope. Here's a video, if that helps. Please be sure to mark which pages correspond to which questions in Gradescope after uploading your pdf.
Each student will be allotted 6 late days for the entire semester. At most 2 late days may be used on any one homework. Please use late days when you really need them, as we cannot accept late homework for any other reason.
How to use late days: Gradescope doesn't have the greatest system for late days. Here's how it will work. Homework is typically due on Thursdays at 5pm. However the Gradescope "due date" will be set to Saturday at 5pm, to facilitate use of late days. To submit "on time", you must electronically submit by Thursday 5pm, and must not re-submit any time after that. Gradescope records the last date/time at which you submitted. (You can also see your submission time on Gradescope by going to "Submission History".) Homework submitted past the "real" due date (typically Thursday 5pm) will incur either 1 or 2 late days. Anything from Thursday 5:01pm to Friday 5:00pm incurs 1 late day; anything from Friday 5:01pm to Saturday 5:00pm incurs 2 late days. After Saturday 5:00pm it will be impossible for you to submit, and you will get a 0 for the homework. If you are using late days you do not need to do anything special beyond submitting. The TAs have access to the time of your submission and will deduct late days accordingly. Nevertheless, you are responsible for knowing how many late days you've used. Gradescope does not know about late days, so it will allow you to submit late even if you've used up all your late days. If this happens, the TAs will detect this and simply give your homework a grade of 0.