15-455: Undergraduate Complexity Theory, Spring 2017 (original) (raw)
Meeting time and place: Tuesday and Thursday, 9am-10:20am, GHC 4307
Course bulletin board: Piazza. This will be used for all course-related communications.
Instructor: Ryan O'Donnell (OH: Mondays 3:30-4:30pm in GHC 7213)
TAs: Laxman Dhulipala (OH: Tuesdays 5-7pm in GHC 9215), Ellis Hershkowitz (OH: Tuesdays 3-5pm in GHC 9219), Patrick Lin (Wednesdays 5-7pm in GHC 4211)
Textbook: Introduction to the Theory of Computation, 2nd or 3rd edition, by Michael Sipser. We will mostly use "Part 3: Complexity". 2nd edition errata, 3rd edition errata
Lectures
| 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. |
Homework assignments
- Homework 01
- Homework 02
- Homework 03
- Homework 04
- Homework 05
- Homework 06
- Homework 07
- Homework 08
- Homework 09
- Homework 10
- Homework 11
Course description and homework expectations
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.
Evaluation
30%: 11 Homeworks, lowest homework score dropped. Late-day policy described below.
30%: In-class Midterm, Thursday March 9
40%: Final Exam
Well-being and happiness
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.
Homework policies
You must complete all homework problems by yourself.
You may:
- Discuss the problems with the course instructors at office hours to whatever extent they allow.
- Ask thoughtful questions or for clarifications on Piazza. (Do not reveal aspects of the solution in public posts, though!)
- Discuss high-level concepts with other students in the course.
- Look at written sources (textbooks, Wikipedia, etc.) for general/high-level concepts (e.g., "nondeterminism", "universal Turing machine"). You may not:
- Communicate with any person outside the class about the problems.
- Share solution details with any other student.
- Search on the internet for specific homework problems. We assume that by now you are fully familiar with the university policies on academic integrity, which of course are in effect. Please contact us directly if you need any clarifications.
Homework mechanics
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.
Optional reading you might like
- Turing's 1937 paper defining Turing Machines, among many other things.
- A 35-year old article about the previous 20 years of computational complexity, by Steve Cook.
- A 30-year old article giving stories about the history of complexity, by Juris Hartmanis.
- A 2017 survey of P vs. NP by Scott Aaronson. He writes in a very lively style, though he packs a lot into little space.
- Chapters 2,4,5,6,7,8,10,11 of The Nature of Computation by Moore and Mertens, an overview of CS Theory that I like a lot.
- Computational Complexity: A Modern Approach by Arora and Barak, a (very) advanced but modern textbook.
- Computational Complexity by Papdimitriou. The textbook I learned from, so I include it for sentimental reasons. 25 years old, but still reasonable (albeit somewhat advanced).
- Google phrases like "complexity theory lecture notes" and see what you turn up. There are dozens of sets of notes out there!