EXERCISE 13 Consider the following decision problem: Monotone 3SAT Instance: a formula in 3-CNF with the property that in each clause, either all literals are positive or all are negative. Question: is there some assignment of values to the variables that makes the formula true? For example, (a v b v ^ (-a v- bv ?s a monotone formula, a legal instance of Monotone 3SAT. By contrast, ( a v ?? v d) is a 3SAT formula but not a monotone one Prove that Monotone 3SATis NP-complete. (Hint: To prove Nr-hardness, use a reduction from 3SAT. Your reduction will need to convert any 3-CNF formula ? into a monotone 3-CNF formula ?, such that ? is satisfiable if and only ifd' is. This will require the introduction of new variables.) EXERCISE 13 Consider the following decision problem: Monotone 3SAT Instance: a formula in 3-CNF with the property that in each clause, either all literals are positive or all are negative. Question: is there some assignment of values to the variables that makes the formula true? For example, (a v b v ^ (-a v- bv ?s a monotone formula, a legal instance of Monotone 3SAT. By contrast, ( a v ?? v d) is a 3SAT formula but not a monotone one Prove that Monotone 3SATis NP-complete. (Hint: To prove Nr-hardness, use a reduction from 3SAT. Your reduction will need to convert any 3-CNF formula ? into a monotone 3-CNF formula ?, such that ? is satisfiable if and only ifd' is. This will require the introduction of new variables.)