Next: About this document
Up: No Title
Previous: No Title
Determine whether the following propositional formulas are satisfiable:
In formula (b), the indexing is over all triples (i, j, k) such
that and , , .
Suppose that SAT P. Show that there then exists a polynomial
time algorithm that for each formula either
states that the formula is not satisfiable, or actually finds a
satisfying truth assignment to the variables .
(Hint: It is easy to see that
formula is satisfiable, if and only if
either formula or formula
Prove the following Lemmas (p. 115 of the lecture notes):
- If L is an NP-complete set and P, then P = NP.
- If L is an NP-complete set, NP and
, then also L' is NP-complete.
Construct a polynomial time reduction from the Clique problem
to the Vertex Cover (VC) problem. (Hint: Look at the
reductions presented on pp. 111-112 of the lecture notes.)
Prove that the following Set Packing problem is NP-complete:
Given a collection of subsets of a finite set U,
and a natural number k, is it possible to choose a subcollection
of at least k disjoint 's (i.e.
(Hint: Reduction from the Independent Set (IS) problem.)
Reminder: This is the last problem set. The last lecture of the
course is on Monday, 7 Dec, and the course exam takes place on Tuesday,
15 Dec (8-12).
Thu Dec 3 15:17:23 EET 1998