CMSC 28100: Introduction to Complexity Theory (Spring 2025)

Term: Spring 2025 at the University of Chicago

Instructor: William Hoza (williamhoza@uchicago.edu)

TAs: Zelin Lv and Yakov Shalunov

Meetings: Mondays, Wednesdays, and Fridays | 2:30pm - 3:20pm | STU 105

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

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. If all goes well, at the end of the course, you will be able to:

• Reason about computation using mathematical models such as the Turing machine model.
• Use reductions to identify undecidable and intractable problems.
• Correctly interpret theorems and questions regarding the ultimate limits of computation.

Office Hours

By default, the office hours are as follows.

• William: Mondays from 9am to 11am in JCL 205, starting on 3/31.
• Zelin: Fridays from 10am to 11am in JCL 207.
• Yakov: Thursdays from 5pm to 6pm in JCL 205.

Some weeks will have modified hours, which will be posted on Ed.

Course Timeline

(The information below will be updated throughout the quarter.)

Homework Policies

I will assign 28 exercises throughout the quarter. Submit your solutions through Gradescope.

Collaboration

You are encouraged to collaborate with your classmates on exercises, but you must adhere to the following rules.

• Work on each exercise on your own for at least five minutes before discussing it with classmates.
• Feel free to explain your ideas to your classmates in person, and feel free to use whiteboards/chalkboards/etc. However, do not share any written/typeset solutions with your classmates for them to study on their own time. For example, if you include a solution to a homework exercise in an Ed post, or even a partial solution, then you should make the thread private, so it is only visible to the course staff. (You are encouraged to use public Ed threads to ask clarification questions and to discuss general concepts.)
• Write your solutions on your own. While you are writing your solutions, 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.

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, any slides or notes posted in the "Course Timeline" section of this webpage, and Wikipedia. You may not use any other resources. Some examples of prohibited resources are ChatGPT and Stack Exchange.

Grading Policies

Numeric Grades

Your overall numeric 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, and $A$ is the weighted average of the midterm exam (35%), exercises 1-4 (5%), and exercises 5-28 (60%). The values $A$ and $B$ are both normalized so be between 0 and 1.

Here are a few hypothetical examples.

• Student 1 earns scores of 85% on the exercises, 50% on the midterm exam, and 50% on the final exam, leading to an overall numeric grade of 65%.
• Student 2 earns scores of 85% on the exercises, 90% on the midterm exam, and 50% on the final exam, leading to an overall numeric grade of 74%.
• Student 3 earns scores of 85% on the exercises, 50% on the midterm exam, and 95% on the final exam, leading to an overall numeric grade of 86%.

To a significant extent, a good performance on the midterm exam safeguards your grade against any challenges you might face later in the quarter. Doing well on the midterm exam means that even if the final exam goes poorly, you will still come out okay. (Compare Students 1 and 2.) I hope that this motivates you to study for the midterm exam. I also hope it helps you to relax and not feel too nervous going into the final exam.

At the same time, even if you do poorly on the midterm exam, you can still succeed in this course. (Consider Student 3.) I hope that this helps you to relax and not feel too nervous going into the midterm exam. I also hope it motivates you to redouble your efforts if the midterm exam goes poorly.

Letter Grades

The letter grade thresholds will be determined at the end of the quarter. To get a rough sense, you can click here to see the thresholds from previous iterations of this course.

Late Work

You are strongly encouraged to complete each exercise within the allotted time. If you don't master the subject matter of a particular exercise by the deadline, 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 an exercise $x$ days late, where $0 < x < 4$, then your score will be multiplied by $1.0063 - 0.0311x - (0.3523x - 0.43)^6$. 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.
• Even if two exercises have the same deadline, you do not have to submit your solutions simultaneously. You can submit one solution on time for full credit and submit the other solution late for partial credit. On the other hand, if an exercise 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 solution for an exercise, then from that point onward, you are not permitted to submit your own solution for that exercise. Submitting a solution after looking at the official solution 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.

The score you see in Gradescope represents your score before applying the lateness penalty, i.e., it is the score that you would have received if you had submitted your solution on time. Lateness penalties will only be recorded in Canvas, possibly after a significant delay.

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 sufficient notice that you will be observing that holiday.

Regrade Requests

If you think something was graded incorrectly, please submit a regrade request through Gradescope. Regrade requests for homework exercises will ordinarily be handled by a TA; you may contact me if you wish to "appeal" their decision. All regrade requests for exams will be handled by me.

Academic Honesty

If you ever find yourself in any kind of irregular / problematic / questionable situation related to academic honesty in this course, send me an email and explain what happened.

For example, you should send me an email if you realize that you accidentally used a prohibited resource while you were working on the homework. As another example, you should send me an email if you cheated on an exam and now you regret it.

I encourage you to follow this simple protocol in every course you take. Depending on the circumstances, you might possibly face some consequences such as a lowered 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.