A formula is in disjunctive normal form $(DN{H}^{\text{'}})$ if it consists of a disjunction of terms,

each of which is a conjunction of literals. An example is

$(not{x}^{{?}^{?}}{y}^{{?}^{?}}$notz$)vv(y^{{?}^{?}}z)vv(x^{{?}^{?}}{y}^{{?}^{?}}z).$

Let

DNFSAT $=\{|is$ a satisfiable $DNF$ formula $\}.$

$($a$)$ Show that DNFSAT $in.$

$($b$)$ What is the error in the following proof sketch that $P=NP?$

We show $3$SAT reduces to DNFSAT. Given a $3$CNF formula, we use the

distributive law to construct an equivalent formula in DNF form. For

example,

$(x^{{?}^{?}}{y}^{{?}^{?}}z)vv(u^{{?}^{?}}v)$

is equivalent to

$(x^{{?}^{?}}u)vv(x^{{?}^{?}}v)vv(y^{{?}^{?}}u)vv(y^{{?}^{?}}v)vv(z^{{?}^{?}}u)vv(z^{{?}^{?}}v)$

Then we can use the algorithm from part $($a$)$ to decide whether the

resulting DNF is satisfiable. Therefore $3$SAT inP and $P=NP!$