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)

Get Unlimited 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?)

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.

 

Add to cart


Study Tools You Might Need

Not The Solution You Need? Search for Your Answer Here:

×

Login

Login or Sign up for access to all of our study tools and educational content!

Forgot password?
Register Now

×

Register

Sign up for access to all content on our site!

Or login if you already have an account

×

Reset password

If you have an active account we’ll send you an e-mail for password recovery

Or login if you have your password back