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
is satisfiable.)

Prove the following Lemmas (p. 115 of the lecture notes):
 If L is an NPcomplete set and P, then P = NP.
 If L is an NPcomplete set, NP and
, then also L' is NPcomplete.

Construct a polynomial time reduction from the Clique problem
to the Vertex Cover (VC) problem. (Hint: Look at the
reductions presented on pp. 111112 of the lecture notes.)

Prove that the following Set Packing problem is NPcomplete:
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.
for )?
(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 (812).
Pekka Orponen
Thu Dec 3 15:17:23 EET 1998