1. A boolean formula is in disjunctive normal form (or DNF) if it consists of a...

 

Transcribed Image Text:

1. A boolean formula is in disjunctive normal form (or DNF) if it consists of a disjunction (OR) or several terms, each of which is the conjunction (AND) of one or more literals. For example, the formula (a^b^c) V (b^c) V (-a^c) is in disjunctive normal form. DNF-SAT asks, given a boolean formula in disjunctive normal form, whether that formula is satisfiable. (a) Show that DNF-SAT is in P. (b) What is wrong with the following argument showing P = NP? 3 pts 7 pts Suppose we are given a boolean formula in conjunctive normal form with at most three literals per clause, and we want to know if it is satisfiable. We can use the distributive law to construct an equivalent formula in disjunctive normal form. For example, (avbv c) (a vb) av bv (a^b) v (b^a) V (c^a) V (c^b) Now we can use the algorithms from part (a) to determine, in polynomial time, whether the resulting DNF formula is satisfiable. We have just solved 3-SAT in polynomial time! 1. A boolean formula is in disjunctive normal form (or DNF) if it consists of a disjunction (OR) or several terms, each of which is the conjunction (AND) of one or more literals. For example, the formula (a^b^c) V (b^c) V (-a^c) is in disjunctive normal form. DNF-SAT asks, given a boolean formula in disjunctive normal form, whether that formula is satisfiable. (a) Show that DNF-SAT is in P. (b) What is wrong with the following argument showing P = NP? 3 pts 7 pts Suppose we are given a boolean formula in conjunctive normal form with at most three literals per clause, and we want to know if it is satisfiable. We can use the distributive law to construct an equivalent formula in disjunctive normal form. For example, (avbv c) (a vb) av bv (a^b) v (b^a) V (c^a) V (c^b) Now we can use the algorithms from part (a) to determine, in polynomial time, whether the resulting DNF formula is satisfiable. We have just solved 3-SAT in polynomial time!