next up previous
Next: About this document Up: No Title Previous: No Title

Data Structures and Algorithms 2, Fall 1998
Problem Set 5 (7 - 9 Dec)

  1. Determine whether the following propositional formulas are satisfiable:
    1. tex2html_wrap_inline39 ;
    2. tex2html_wrap_inline41 .
    In formula (b), the indexing is over all triples (i, j, k) such that tex2html_wrap_inline45 and tex2html_wrap_inline47 , tex2html_wrap_inline49 , tex2html_wrap_inline51 .
  2. Suppose that SAT tex2html_wrap_inline53 P. Show that there then exists a polynomial time algorithm that for each formula tex2html_wrap_inline55 either states that the formula is not satisfiable, or actually finds a satisfying truth assignment to the variables tex2html_wrap_inline57 . (Hint: It is easy to see that formula tex2html_wrap_inline55 is satisfiable, if and only if either formula tex2html_wrap_inline61 or formula tex2html_wrap_inline63 is satisfiable.)
  3. Prove the following Lemmas (p. 115 of the lecture notes):
    1. If L is an NP-complete set and tex2html_wrap_inline67 P, then P = NP.
    2. If L is an NP-complete set, tex2html_wrap_inline71 NP and tex2html_wrap_inline73 , then also L' is NP-complete.
  4. 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.)
  5. Prove that the following Set Packing problem is NP-complete:
    Given a collection of subsets tex2html_wrap_inline77 of a finite set U, and a natural number k, is it possible to choose a subcollection of at least k disjoint tex2html_wrap_inline85 's (i.e. tex2html_wrap_inline87 for tex2html_wrap_inline47 )?
    (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).

Pekka Orponen
Thu Dec 3 15:17:23 EET 1998