CMSC 28100-1: Introduction to Complexity Theory (Spring 2024)
Term: Spring 2024 at the University of Chicago
Instructor: William Hoza (williamhoza@uchicago.edu)
TAs: Zelin Lv and Rohan Soni
Graders: Nico Marin Gamboa and Loren Troan
Meetings: Mondays, Wednesdays, and Fridays | 9:30am - 10:20am | STU 105
Textbook: Introduction to the Theory of Computing, 3rd Edition by Michael Sipser. ISBN-13: 9780357670583.
Jump to: (loading...)
Course Description In this course, we will study the mathematical and philosophical foundations of computer science. Our central mission will be to understand which problems can be solved through computation, focusing especially on impossibility proofs. In the first part of the course, we will develop techniques for proving that certain problems, such as the "halting problem," cannot be solved by any algorithm whatsoever. In the second part of the course, we will study computation in a world where resources, such as time and space (memory), are limited. We will prove that certain problems are "intractable," meaning that they cannot be solved by polynomial-time algorithms, and we will develop the theory of "NP-completeness," which enables us to identify many important problems that are likely to be intractable.
Office Hours Some weeks will have modified office hours, which will be posted on Ed. By default, the office hours are as follows.
- Mondays, 10:30am - 12:30pm, JCL 205 (William)
- Thursdays, 2:30pm - 3:30pm, JCL 205 (Rohan)
- Fridays, 1pm - 2pm, JCL 205 (Zelin)
Course Timeline (The information below will be updated throughout the quarter.)
|
Monday 3/18: Logistics; Turing machines; alphabets; strings; halting; looping.
Chapter 0 and Sections 3.0-3.1.
|
|
Wednesday 3/20: The rigorous definition of a Turing machine; configurations; computation histories; time; space.
None.
|
|
Friday 3/22: Deciding languages; encoding objects as strings; the Church-Turing thesis.
Sections 3.2 (you can skip the part about nondeterminism) and 3.3.
|
|
Monday 3/25: Left-right-stationary Turing machines; multi-tape Turing machines.
None.
Problem set 1 is due on Tuesday 3/26
|
|
Wednesday 3/27: Multi-tape Turing machines (continued); comparing Turing machines to Python.
Sections 4.0 and 4.2.
|
|
Friday 3/29: Code as data; universal Turing machines.
None.
|
|
Monday 4/1: The self-rejection problem; the halting problem; the physical Church-Turing thesis; variants of the halting problem.
Sections 5.0-5.1. (You can skip Theorems 5.3 and 5.13.)
Problem set 2 is due on Tuesday 4/2
|
|
Wednesday 4/3: Reductions.
Sections 5.2-5.3.
|
|
Friday 4/5: Post's correspondence problem.
None.
|
|
Monday 4/8: Post's correspondence problem (continued).
Pages 275-281, i.e., the beginning of Chapter 7, ending partway through Section 7.1.
Problem set 3 is due on Tuesday 4/9
|
|
Wednesday 4/10: Time complexity; asymptotic notation.
Page 202, the top of page 283, and Section 7.2, skipping Theorem 7.16. (I.e., the remainder of Sections 7.1 and 7.2, skipping nondeterministic TMs and context-free languages.)
|
|
Friday 4/12: Asymptotics (continued); the complexity class P; dynamic programming; revisiting multi-tape Turing machines.
None.
|
|
Monday 4/15: The extended Church-Turing thesis; communication protocols; the rectangle lemma; the deterministic communication complexity of the equality function.
Pages 396-398 and the second half of page 403, or (optionally) all of Section 10.2.
(No problem set is due this week)
|
|
Wednesday 4/17: Midterm exam.
None.
|
|
Friday 4/19: Randomized communication complexity; randomized Turing machines; the complexity class BPP.
From the bottom of page 379 to page 381 (i.e., the beginning of Section 9.3).
|
|
Monday 4/22: The amplification lemma; the P vs. BPP question; BPP is contained in PSPACE; PSPACE is contained in EXP.
None.
Problem set 4 is due on Tuesday 4/23
|
|
Wednesday 4/24: Circuit complexity; conjunctive normal form; the complexity class PSIZE.
Page 382 to the middle of page 386 (i.e., through the proof of Theorem 9.30).
|
|
Friday 4/26: Simulating Turing machines using circuits; Adleman's theorem.
None.
|
|
Monday 4/29: Adleman's theorem (continued); the time hierarchy theorem.
Pages 300-301, skipping the very beginning (the statement of Theorem 7.27) and the very end (the discussion of 3SAT). Optional additional reading: Pages 364 to the middle of page 371, i.e., the first part of Section 9.2.
Problem set 5 is due on Tuesday 4/30
|
|
Wednesday 5/1: The time hierarchy theorem (continued); polynomial-time mapping reductions; the time-bounded halting problem; EXP-hardness; EXP-completeness.
None.
|
|
Friday 5/3: (Class held remotely via Zoom) EXP-completeness (continued); the clique problem; the complexity class NP; NP is contained in PSPACE.
Section 7.3.
|
|
Monday 5/6: NP is contained in PSPACE (continued); NP-hardness; NP-completeness; code as data (revisited); efficiently constructing circuits that simulate Turing machines; circuit satisfiability.
Pages 299-304 (i.e., the first part of Section 7.4); the middle of page 386 to page 388 (i.e., the second part of Section 9.3).
Problem set 6 is due on Tuesday 5/7
|
|
Wednesday 5/8: Circuit satisfiability is NP-complete; the Cook-Levin theorem.
Section 7.5.
|
|
Friday 5/10: The Cook-Levin theorem (continued); the clique problem is NP-complete.
None.
|
|
Monday 5/13: Public-key encryption; approximation algorithms; quantum computing.
(Optional) Section 10.6.
Problem set 7 is due on Tuesday 5/14
|
|
Wednesday 5/15: Quantum computing (continued); integer factorization; the complexity class NP intersect coNP; sublinear-space computation.
(Optional) Section 10.1.
|
|
Friday 5/17: Course summary and review.
None.
|
| Wednesday 5/22 (10am to noon): Final exam. |
Homework Policies
There will be six or seven problem sets (exact number TBD). Submit your solutions through Gradescope.
Collaboration. You are encouraged to collaborate with your classmates on problem sets, but you must adhere to the following rules.
- Work on each problem on your own for at least five minutes before discussing it with classmates.
- Write your solution on your own. While you are writing your solution, do not consult any notes that you might have taken during discussions with classmates.
- In your write-up, list any classmates who helped you figure out the solution. The fact that student A contributed to student B's solution does not necessarily mean that student B contributed to student A's solution.
- Do not post solutions or partial solutions anywhere that your classmates are likely to find them, such as Ed. (You are welcome to use Ed to ask clarification questions and to discuss general concepts.)
Permitted Resources. In addition to discussions with me, discussions with TAs, and discussions with classmates as discussed above, you may also use the course textbook and any slides or notes posted in the "Course Timeline" section of this webpage. You may not use any other resources. Some examples of prohibited resources are Wikipedia, ChatGPT, and Stack Exchange.
Grading Policies Your overall grade in this course will be calculated using the formula $$ G = 0.65 \cdot A + 0.35 \cdot B + 0.3 \cdot B^6 \cdot \max(B - A, 0). $$ In this formula, $B$ is your score on the final exam (normalized to be between 0 and 1), and $A$ is the weighted average of your scores on everything prior to the final exam (again, normalized to be between 0 and 1). The weights for calculating $A$ are as follows.
- 5%: Problem set 1.
- 62%: The remaining problem sets.
- 33%: The midterm exam.
Late work. You are strongly encouraged to complete each problem set within the allotted time. If you don't master the subject matter of a particular problem set by the time the problem set is due, then you might have trouble understanding the topics we discuss in the following classes. Furthermore, if you submit your solutions late, then it might not be possible to give you timely feedback. That being said, I understand that occasionally missing a deadline is inevitable. Late work will ordinarily receive partial credit based on the following principles.
- If you submit your solution to a problem $x$ days late, where $0 < x < 4$, then your score will be multiplied by $(1 - (x/4)^3)^{1/3}$. The value $x$ can be fractional; some rounding will occur in the calculation. Work turned in four or more days late will ordinarily not receive any credit. Saturdays, Sundays, and university holidays are all excluded from the lateness calculation.
- This late work policy is applied on a problem-by-problem basis. For example, if you submit your solution to problem 1 of problem set 1 on time and you submit your solution to problem 2 of that same problem set late, then you will receive full credit for problem 1 and partial credit for problem 2. (However, if a problem is divided into parts, then you must submit your solutions to all parts simultaneously.)
- Eventually, I will post official solutions. If you look at the official solutions, then from that point onward, you are not permitted to submit your own solutions for that problem set. Submitting solutions after looking at the official solutions would be an academic honesty violation.
- The principles described above might be ambiguous or problematic in some edge cases. Ultimately, I will decide how much credit to grant for late work.
If you are submitting work more than twelve hours late, you should submit your solutions to each problem individually, using the special "LATE" assignments in Gradescope. The score recorded in Gradescope for the "LATE" assignment represents your score before applying the late penalty, i.e., it is the score that you would have received if you had turned your solution in on time. Your actual score (incorporating the late penalty) will be recorded in the main Gradescope assignment associated with that problem set.
Extensions. Please get in touch with me if you are having trouble keeping up with the course schedule for any reason. I may be willing to give you an extension, or I may be willing to give you partial credit for late work in excess of what the principles above stipulate. To highlight one example, I am happy to grant an extension for a religious holiday if you give me sufficiently early notice that you will be observing that holiday.
Regrade requests. If you think something was graded incorrectly, please submit a regrade request through Gradescope. For problem sets, these regrade requests will ordinarily be handled by a TA or grader; you may contact me if you wish to "appeal" their decision. For exams, all regrade requests will be handled by me.
Academic Honesty Catch-All Policy Even if you have no intention of being dishonest, you might nevertheless find yourself in an "ethically problematic" situation at some point. For example, maybe you and a classmate work together to solve a homework problem, and then afterward you remember that you were supposed to work on the problem on your own for at least five minutes before collaborating. Or maybe you accidentally stumble upon the solution to a homework problem while reading the textbook for a different course.
In such circumstances, you should simply send me an email explaining what happened.
I encourage you to follow this simple protocol in every course you take. It is a surefire way to avoid getting in trouble for academic dishonesty. Depending on the circumstances, I might have to take some points off your score, but don't let this deter you. A clean conscience is worth more than any grade.
Inclusion and Accessibility This course, like every course you take, ought to be an enjoyable and enriching experience. You have a right to be treated with respect and a responsibility to treat others with respect. I want all students to be able to fully participate in this course. Let me know if you need an accommodation for any reason, so we can explore possible solutions together. If applicable, please follow the protocols established by UChicago Student Disability Services.
To highlight a few facets of these topics:
- You are encouraged to ask questions in class, and you should make your classmates feel comfortable asking questions in class. There is no shame in not knowing something or not understanding something. Questions make the course better for everyone.
- I am happy to work with any students who are pregnant/parenting to figure out the best way to make the course work for you.
- Computer scientists and mathematicians can come from many diverse backgrounds, and nobody should experience prejudice or discrimination in this course.