Home

Homework   Index   Syllabus   URM Simulator


Extra Homework Problems

Models of Computation - Mathematics 450 - Spring 2005


For HW #27

  1. Here I will use v for OR, ^ for AND, and ~ for NOT. Thus, {x1 v ~x2} means  {x1, x2} (in Wilf's notation).
    1. Explain why {x1 v x2 v ... v xk}  is equivalent to {x1 v z} ^ {~z v x2 v ... v xk}. "Equivalent" means one is true iff the other is.
    2. Is {x1 v x2 v ... v xk} equivalent to {x1 v x2 v z} ^ {~z v x3 v ... v xk}? Why?
    3. Explain how, by repeatedly applying part b. above, we can arrive at expression (5.4) at the top of page 187 in Wilf.
    4. It may seem that by repeatedly applying part a. above, we might actually be able to reduce SAT to 2SAT (instead of just to 3SAT, as in Wilf). Explain why this will not work.
  2. Wilf, page 187, line -8 says: "We remark, in passing, that the problem '2SAT' is in P."
    Can you prove this?

Updated: 31 August, 2009 17:44:19