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.
m-CNF formulas satisfiability approximation
complexity theory