Homework 1: Due Sep. 21
- Send me a photo (jpg or gif) of yourself and tell me how to
pronounce your name. Do this ASAP.
- Give a linear-time algorithm for 2SAT. If the formula is
satisfiable, your algorithm should return a satisfying
assignment (in linear time).
- Prove that HORNSAT can be solved in polynomial time. Come up
with as efficient an algorithm as you can and prove its
- Consider the following restriction to SAT: each clause either
has at most 2 literals or is a horn clause. Is this problem in
P? Is it NPC? Provide a proof.
- Show that the problem of recognizing =3CNF formulas for
which there is a satisfying assignment such that at most 2
literals per clause are true, is NPC.
- Consider the problem of recognizing satisfiable =3CNF formulas
in which each variable appears exactly 3 times. Is this
problem in P? Is it NPC? Provide a proof.
Last modified: Tue Sep 11 20:36:18 EDT 2007