Only need to do (b)

Problem 3 A DNF formula is an OR of "terms", where a "term" is an AND of literals; for example, (x1x3x4)(x2x3)(x2x4x5x6) is a 3-term DNF. A CNF is an AND of "clauses" where a "clause" is an OR of literals; for example, (x3x4x5)(x2x3) is a 2-clause CNF. (a) Show that there are DNF formulas with O(n) terms such that any logically equivalent CNF formula must have 2(n) clauses. (b) Consider the following decision problem: The input is a pair (,1k) where is a DNF formula and k is an integer. The problem is to determine whether there is a CNF formula that is logically equivalent to that has k or fewer clauses. Show that this problem (or more precisely, the language corresponding to this problem) is in 2p