Course webpage: http://www.cse.ucsd.edu/classes/wi06/cse200/
Instructor: Daniele Micciancio
Due: March 15 in class. (Usual policies, etc., etc.)
Let 2SAT be the set of all boolean formulas in conjunctive normal form (CNF) such that every clause contains at most 2 literals. In other words, 2SAT is a special case of 3SAT where none of the clauses use 3 literals. Prove that 2SAT is NL-complete. (Remember, this means you have to prove both that 2SAT is in NL, and every problem in NL reduces to 2SAT via log-space reductions. When describing how to solve 2SAT in NL, you should give enough details to make it clear that your solution only requires logarithmic space. E.g., just saying "Guess a satisfying assignment and check if it is correct." is not enough to prove that 2SAT is in NL.)
[Hint: you may want to use the fact that NL=coNL, which will be proved in class on March 8.]