Could you point me a reference, an answer or it is an open question?
$\begingroup$
$\endgroup$
2
-
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
Add a comment
|
$\begingroup$
$\endgroup$
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.
