About the 22C:131 Midterm

• The midterm for 22C:131 will be on Tuesday, Oct 9th in the evening; time and place to be announced. This is an open notes (book) exam, so feel free to bring books, handwritten notes, printouts of online notes and webpages, etc., to the exam. The exam is worth 20% of your grade and will be graded out of 200 points. It will be over the material in Chapters 1, 2, and 3 (Sections 3.1-3.3 only).

• There will be 4 problems on the exam. Here are more details about each problem.
  1. (50 points) I will give you 10 complexity-theoretic claims and for each claim, you will have to say whether the claim is known to be true, known to be false, or not known to be either. If your answer is true or false, you will have to provide a 1-sentence justification for your answer.
  2. (50 points) You will be asked to show that a certain (given) language is uncomputable. This will be similar to Problems 4-5 in HW1.
  3. (50 points) You will be asked questions that will help you "show off" your understanding of the proof of the Cook-Levin Theorem (Theorem 2.10).
  4. (50 points) You will be asked questions that will help you "show off" your understanding of diagonalization as it is used to obtain the time hierarchy theorems and Ladner's Theorem.