CMSC 28100-1: Introduction to Complexity Theory (Spring 2024)

Term: Spring 2024 at the University of Chicago

Instructor: William Hoza (

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.

    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.
    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.
    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.
    Monday 4/1: The self-rejection problem; the halting problem; the physical Church-Turing thesis; variants of the halting problem.
    [pptx] [pdf]. Also, here's the example self-rejecting Python script:
    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.
    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.
    [pptx] [pdf]. Also, here are the files for the Python script that (slowly) searches for decompositions into squares: example1.txt example2.txt example3.txt example4.txt
    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.
    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.
    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.
    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.
    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.
    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.
    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.
    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.

    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.

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