Problem Set 3 

Q1 You should only resolve on two clauses if they contain a
complementary literal (one contains l and the other contains -l).
This is the definition of the resolvent.  Hint: you may have to go
through several stages; you may not get the empty clause in the first
stage when you resolve on the original clauses only.

Q2 In part (b) please provide a proof of correctness of your
reduction.  

Q3 This is an important question, and the final exam is going to
contain a question like this one.  The idea is the following: for each
of the 5 decision problems, you have to give a polytime algorithm if
one exists, and show that the problem is NP-complete to justify your
claim that one does not exist.  Thus, for each problem, state whether
it is "in P" or it is "NP-complete", and justify this.  In the first
case, the justification is a polytime algorithm, in the second case,
it is a reduction from some NP-complete problem in the notes.