I am reviewing for a test, and i am stuck on this question.

the problem is to show it is hard to approximate (for any constant) the following problem:

given m CNF formulas f1,..,fm over variables x1,..,xn find the assignment which maximizes the number of satisfied formulas.

I believe I need to reduce this problem to some kind of graph problem (CSG,IS,CLIQUE), which I know cannot be approximated for any constant. I can't find a way to do this. To what problem do I reduce this to?

thank you.


If such a constant-factor approximation algorithm would exist, and it would run in polynomial-time, you could use it to solve CNF-SAT in polynomial time. Since CNF-SAT is NP-hard, this may give you the desired result.

Sketch: Given a CNF-formula f, feed sufficiently many copies of the formula to your approximation algorithm. If f is not satisfiable, the algorithm must always output 0. If f is satisfiable, it should output a number > 0 (at least, if the other numbers are chosen correctly).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.