# Is 3SAT problem APX-hard or not?

Could you point me a reference, an answer or it is an open question?

• en.wikipedia.org/wiki/Maximum_satisfiability_problem Sep 20, 2012 at 14:34
• To elaborate on Sasho's comment above: APX-hardness corresponds to the solution of optimization problems, which are function or relation problems rather than decision problems. If you want to describe a sense in which SAT-like problems may or may not be in APX, you must describe which optimization problem you're considering, e.g. MAX-SAT. As Sasho demonstrates, it is easy to find at least secondary references indicating the status of MAX-SAT with respect to APX. Sep 20, 2012 at 14:43

If the optimization problem you have in mind is MAX-3SAT, it's not only APX-hard but also approximation resistant, in the sense that whenever all clauses have exactly 3 literals, it is hard to satisfy much more than 7/8 of the clauses (even if the instance is satisfiable), something that is trivially achieved by a random assignment. When some clauses may have less than 3 literals, there is still an algorithm that satisfies a 7/8 fraction of the optimum and that is the best you can do assuming P $\neq$ NP.