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?