# Is MAX-SAT NP-hard?

The MAX-SAT problem is NP-hard, since its solution easily leads to the solution of the boolean satisfiability problem, which is NP-complete

I see that a given SAT problem can be reduced to a MAX-SAT problem: just solve the MAX-SAT problem for the boolean formula to see if all clauses can be satisfied. If yes, the SAT problem has the answer "yes", otherwise "no".

Question 1: What confuses me is that we have an optimization problem here, and no decision problem. So, can also optimization problems be considered as NP-hard? It only needs to be shown that the (optimization) problem can be reduced in polynomial-time to the SAT problem (or another NP-hard problem)?

Question 2: To reduce the SAT problem to MAX-SAT, we have to find a function $f$, which is computable in polynomial time, and with $p \text{ in } \text{SAT} \Leftrightarrow f(p) \text{ in } \text{MAX-SAT}$.

This is the definition I know about reduction. But here, we clearly can not find such a function $f$ since MAX-SAT is not a decision problem. How can a reduction be shown here?

• As Yuval says, the $NP$-hardness of such problems is really a statement about the related decision variant. This relationship between an optimization problem and its decision variant is formalised as $NPO$ ($NP$ optimization). For the problems in $NPO$ the relationship is appropriately bounded (much as you'd expect, with polynomial bounds, PTIME verification etc.) As usual wikipedia is pretty good starting place (en.wikipedia.org/wiki/…) Commented Jul 31, 2012 at 1:13
• Regarding the relationship of NP and NPO, see also here and here. Commented Jul 31, 2012 at 7:13
• Somehow I feel that wikipedia article is not correct.
– hola
Commented Aug 18, 2021 at 0:27
• I don't know, but here it says, MAX-SAT is NP-complete.
– hola
Commented Aug 18, 2021 at 0:28

The decision problem related to MAX-SAT is, given a formula $\phi$ and a number $k$, decide whether there is an assignment satisfying at least $k$ of the clauses. This is clearly NP-hard since it can be used to solve SAT, and on the other hand, also in NP, since it is easy to verify the properties of a good assignment. Hence it is NP-complete.

• Regarding question two, $f$ copies the formula and adds the number of clauses (as $k$). Commented Jul 31, 2012 at 15:01
• I think there is no problem saying that an optimization problem is NP-hard (of course there is a problem saying that it's NP-complete, as the problem cannot be in NP). The hardness in that case will be based on a Levin-style reduction Commented Jul 31, 2012 at 18:31
• I.e., question 2 can be answered by introducing OP to Levin-type reductions: SAT is reducible to Max-SAT if we can find two functions $f$ and $g$ computable in polynomial time s.t. $\phi \in \text{SAT}$ if and only if $g(\text{Max-SAT}(f(\phi)) = 1$. Here $\text{Max-SAT}(\phi)$ as a function is just the number of satisfiable clauses of $\phi$. Commented Aug 1, 2012 at 0:05
• What is the complexity of Weighted-MAXSAT? Commented Feb 8, 2015 at 4:59