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

  • 2
    $\begingroup$ en.wikipedia.org/wiki/Maximum_satisfiability_problem $\endgroup$ Sep 20, 2012 at 14:34
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 20, 2012 at 14:43

1 Answer 1


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.

See the paper "Some optimal inapproximability results" by Johan Håstad.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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