About the CS:5340 Midterm

• The midterm for CS:5340 will be on Fri, Oct 6th from 6:30 pm to 8:30 pm in 203 Becker Communication Studies Building (BCSB). 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. During the exam you will not have access to any electronic devices and you will not be able share any material with classmates. The exam is worth 25% of your grade and will be graded out of 250 points. It will be over the material in Chapters 1 (skip Section 1.7), 2, 3 (Sections 3.1-3.3 only), and 4 (Section 4.1 only).

• There will be 4 problems on the exam. Here are more details about each problem.

  1. (100 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 2-3 in HW2.

  3. (50 points) You will be asked questions that will help you show your understanding of the proof of the Cook-Levin Theorem (Theorem 2.10, Lemma 2.11).

  4. (50 points) You will be asked questions that will help you show your understanding of the use of diagonalization in the proofs of the time hierarchy theorems (Theorem 3.1 and the proof of the non-deterministic hierarchy theorem due to Fortnow and Santhanam) and the proof of Ladner's Theorem on the existence of "NP-intermediate" languages.