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

Term: Winter 2024 at the University of Chicago

Instructor: William Hoza (williamhoza@uchicago.edu)

TAs: Tapan Srivastava and Chris Zhu

Graders: Nico Marin Gamboa and Rohan Soni

Meetings: Mondays, Wednesdays, and Fridays; 9:30am - 10:20am; RY 276

Office Hours

• Mondays, 10:30am - 11:30am, JCL 205 (Chris)
• Tuesdays, 1pm - 2pm, JCL 205 (Tapan)
• Wednesdays, 10:30am - 12:30pm, JCL 311 (William)
• Wednesdays, 3:30pm - 4:30pm, JCL Common Area 2A (Nico and Rohan) [canceled]

Textbook Introduction to the Theory of Computing, 3rd Edition by Michael Sipser. ISBN-13: 9780357670583.

Course Timeline (The information below will be updated throughout the quarter.) [Edit 2024-05-17: I removed the slides, because some of them are buggy.]

1. Wednesday 1/3: Logistics; alphabets; strings; encodings; languages.
   Chapter 0.
2. Friday 1/5: Turing machines; state diagrams; configurations.
   Sections 3.0-3.1.
3. Monday 1/8: Deciding languages; the Church-Turing thesis.
   Sections 3.2 (you can skip the part on nondeterminism) and 3.3.
4. Wednesday 1/10: Start-of-tape indicators; multi-head Turing machines.
   None.
5. Friday 1/12: Multi-tape Turing machines; a toy programming language; universal Turing machines.
   None.
   (No class on Monday 1/15 because of MLK day)
6. Wednesday 1/17: The halting problem; the physical Church-Turing thesis; reductions.
   Sections 4.0 and 4.2.
7. Friday 1/19: More examples of using reductions to prove undecidability.
   Sections 5.0-5.1. (You can skip Theorem 5.3 and Theorem 5.13.)
8. Monday 1/22: Post's correspondence problem.
   Sections 5.2-5.3.
9. Wednesday 1/24: Post's correspondence problem (wrapping up); time complexity; asymptotic notation.
   Pages 275-281. (I.e., from the beginning of Chapter 7 to partway through Section 7.1.)
10. Friday 1/26: More asymptotic notation; polynomial vs. exponential; the complexity class P; revisiting multi-tape Turing machines; longest increasing subsequence; the time hierarchy theorem.
    Page 282, the top of page 283, and Section 7.2, skipping Theorem 7.16. (I.e., the remainder of Chapter 7, skipping nondeterministic TMs and context-free languages.)
11. Monday 1/29: The time hierarchy theorem (wrapping up); Boolean circuits; Lupanov's circuit complexity upper bound; Shannon's circuit complexity lower bound.
    (Optional) Page 364 to the middle of page 371. (I.e., the first part of Section 9.1.)
12. Wednesday 1/31: Circuit evaluation in polynomial time; P is contained in PSIZE.
    The bottom of page 379 to the middle of page 386. (I.e., the first part of Section 9.3.)
13. Friday 2/2: Midterm exam.
    None.
14. Monday 2/5: Polynomial-time reductions; the time-bounded halting problem; EXP-hardness.
    Pages 300-301. (I.e., the portion of Section 7.4 that discusses polynomial time reducibility.)
15. Wednesday 2/7: EXP-completeness; circuit satisfiability; NP; the P vs. NP problem.
    Section 7.3.
16. Friday 2/9: NP is contained in EXP; nondeterministic Turing machines; NP-hardness and NP-completeness; uniform circuit families.
    Pages 299-304. (I.e., the first part of Section 7.4, including the statement but not the proof of Theorem 7.37.)
17. Monday 2/12: Uniform circuit families (wrapping up); CIRCUIT-SAT is NP-complete; CNF formulas; the Cook-Levin theorem.
    The middle of page 386 to page 388. (I.e., the second part of Section 9.3.)
18. Wednesday 2/14: The Cook-Levin theorem (wrapping up); CLIQUE is NP-complete; Eulerian and Hamiltonian graphs.
    Section 7.5.
19. Friday 2/16: Directed Hamiltonian path is NP-complete; undirected Hamiltonian path is NP-complete; undirected Hamiltonian cycle is NP-complete.
    None.
20. Monday 2/19: Public-key encryption; integer factorization; coNP.
    (Optional) Section 10.6.
21. Wednesday 2/21: NP intersect coNP; coping with intractability; approximation algorithms.
    (Optional) Section 10.1.
22. Friday 2/23: The extended Church-Turing thesis; randomized Turing machines; BPP; the amplification 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.
23. Monday 2/26: Randomized communication complexity; quantum computing; space complexity; PSPACE.
    Section 8.0 (you can skip Example 8.4).
24. Wednesday 2/28: PSPACE is contained in EXP; sublinear-space computation; L is contained in P; NL; Savitch's theorem; s-t connectivity is NL-complete.
    Section 8.2 and 8.4, or (optionally) all of Chapter 8.
25. Friday 3/1: Course summary and review.
    None.
    (Final exam on Tuesday 3/5 at 7:30am)

Problem Sets There will be seven problem sets throughout the quarter. Submit your solutions through Gradescope.

1. Problem set 1, due January 11 at 5pm
2. Problem set 2, due January 18 at 5pm
3. Problem set 3, due January 25 at 5pm
   (In-class midterm exam on February 2)
4. Problem set 4, due February 8 at 5pm
5. Problem set 5, due February 15 at 5pm
6. Problem set 6, due February 22 at 5pm
7. Problem set 7, due February 29 at 5pm
   (Final exam on March 5 from 7:30am to 9:30am)

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

Late Submissions. 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 receive partial credit based on the following principles.

• If you submit your solution to a problem \(x\) days late, where \(0 < x < 5\), then your score will be multiplied by \(\sqrt{1 - (x/5)^2}\), with some rounding. The value \(x\) can be fractional. Work turned in five or more days late will ordinarily not receive any credit.
• Saturdays, Sundays, and university holidays are all excluded from the lateness calculation. If you give me sufficiently early notice that you will be observing a religious holiday, then that day will also be 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 a particular problem set on time and you submit your solution to problem 2 of that same problem set one day 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 the solutions to all parts simultaneously.
• The calculation described above might be ambiguous in some cases. Ultimately, I will decide how much credit to grant for late work. In special circumstances, I might grant more credit for late work than what the calculation described above stipulates. Please get in touch with me if you are having trouble keeping up with the course schedule for any reason.

Grading 35% problem sets, 25% midterm, 40% final exam.

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 ten 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 write a note explaining what happened and include it with your submission.

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.

Accessibility and Accommodations 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 one example, I am happy to work with students who are pregnant/parenting to figure out the best way to make the course work for you.

Inclusion and Atmosphere 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.

To highlight one facet of this topic, 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.

To highlight another facet, computer scientists can come from many diverse backgrounds, and nobody should experience prejudice or discrimination in this course.