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

  • 2
    $\begingroup$ en.wikipedia.org/wiki/Maximum_satisfiability_problem $\endgroup$ – Sasho Nikolov Sep 20 '12 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$ – Niel de Beaudrap Sep 20 '12 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.

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, privacy policy and cookie policy

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