Solution Found!
In the MAX SAT problem, we are given a set of clauses, and we want to find an assignment
Chapter 9, Problem 9.8(choose chapter or problem)
In the MAX SAT problem, we are given a set of clauses, and we want to find an assignment thatsatisfies as many of them as possible.(a) Show that if this problem can be solved in polynomial time, then so can SAT.(b) Heres a very naive algorithm.for each variable:set its value to either 0 or 1 by flipping a coinSuppose the input has m clauses, of which the jth has kj literals. Show that the expectednumber of clauses satisfied by this simple algorithm isXmj=11 12kjm2.In other words, this is a 2-approximation in expectation! And if the clauses all contain kliterals, then this approximation factor improves to 1 + 1/(2k 1).(c) Can you make this algorithm deterministic? (Hint: Instead of flipping a coin for eachvariable, select the value that satisfies the most of the as of yet unsatisfied clauses. Whatfraction of the clauses is satisfied in the end?)
Questions & Answers
QUESTION:
In the MAX SAT problem, we are given a set of clauses, and we want to find an assignment thatsatisfies as many of them as possible.(a) Show that if this problem can be solved in polynomial time, then so can SAT.(b) Heres a very naive algorithm.for each variable:set its value to either 0 or 1 by flipping a coinSuppose the input has m clauses, of which the jth has kj literals. Show that the expectednumber of clauses satisfied by this simple algorithm isXmj=11 12kjm2.In other words, this is a 2-approximation in expectation! And if the clauses all contain kliterals, then this approximation factor improves to 1 + 1/(2k 1).(c) Can you make this algorithm deterministic? (Hint: Instead of flipping a coin for eachvariable, select the value that satisfies the most of the as of yet unsatisfied clauses. Whatfraction of the clauses is satisfied in the end?)
ANSWER:Step 1 of 3
Suppose a CNF Boolean formula has m number of clauses.
Suppose MAX-SAT is solved in polynomial time, and k is the maximum number of clauses which can be made true by assignment of truth values to the variables of CNF formula with total m clauses.
If k=m, then SAT is satisfiable.
If, this means all the clauses of a given CNF formula does not have truth values, then SAT is unsatisfiable.
Hence, it is proved that if MAXSAT is solved in polynomial time, then SAT can also be solved in polynomial time.