<p>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.</p>

<p>See the paper "Some optimal inapproximability results" by Johan Håstad.</p>

CC BY-SA 3.0
2012-09-20T15:02:19.250Z
2012-09-20T15:11:02.067Z
2012-09-20T15:11:02.067Z
Mahdi Cheraghchi
<p>Could you point me a reference, an answer or it is an open question?</p>

CC BY-SA 3.0
2012-09-20T14:34:45.373Z
http://en.wikipedia.org/wiki/Maximum_satisfiability_problem
Sasho Nikolov
CC BY-SA 3.0
2012-09-20T14:43:51.433Z
To elaborate on Sasho's comment above: [**APX**](http://en.wikipedia.org/wiki/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**.
Niel de Beaudrap
<cc.complexity-theory><np-hardness><complexity-classes><approximation-hardness>
Is 3SAT problem APX-hard or not?
simco
# Is 3SAT problem APX-hard or not?

(Asked by: username_0 on 2012-09-20)

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

**Tags:** cc.complexity-theory, np-hardness, complexity-classes, approximation-hardness

> **Comments:**
> **username_1**: http://en.wikipedia.org/wiki/Maximum_satisfiability_problem  
> **username_2**: To elaborate on Sasho's comment above: [**APX**](http://en.wikipedia.org/wiki/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**.  

---

## 1 answers

### Answer by username_3 on 2012-09-20. Score: 5

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.


---

