# m-CNF formulas satisfiability approximation

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).