CS 5315 Homework #11

Date Assigned: Thursday, March 17, 2005

Due Date: Tuesday, March 29, 2005

1. Pick a propositional formula and use the general algorithm, to transform it into DNF and CNF forms.

2. Similarly to what we did in the class, trace how another example of an NP problem can be reduced to propositional satisfiability. Advise: pick a problem R(x,y) with x, y of 1 bit length, and with a different predicate R.