Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________
Per-problem assessment: • 5 (Perfect): Correct solution • 4 (Good effort): Good effort, solution may or may not be correct. • 2 (Poor effort): Some basic misunderstandings demonstrated that could have been cleared up by reading the notes or giving a serious try. • 0 (No effort): No progress towards a solution.

Problem 0 (assessment: self_______ final_______)

Convert the following circuit into a 3CNF formula following our polynomial time recuction of CIRCUIT-SAT to 3CNF-SAT, as given in the notes.

Problem 1 (assessment: self_______ final_______)

Consider the following instance of 3CNF-SAT: $ F = (c \vee a) \wedge (c \vee b) \wedge (\neg a \vee \neg b \vee \neg c) \wedge (\neg c) $

  1. Follow the reduction algorithm that reduces 3CNF-SAT to INDEPENDENT-SET, and draw the resulting graph (and k value).
  2. Clearly show which vertices form the independent set of size $k$.
  3. Clearly state the associated satisfying assignment for the variables in formula $F$.