Is the MAX-SAT problem NP-hard? From the Wikipedia page:

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?

  • 2
    $\begingroup$ 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/…) $\endgroup$ – Luke Mathieson Jul 31 '12 at 1:13
  • 1
    $\begingroup$ Regarding the relationship of NP and NPO, see also here and here. $\endgroup$ – Raphael Jul 31 '12 at 7:13

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.

  • 1
    $\begingroup$ Regarding question two, $f$ copies the formula and adds the number of clauses (as $k$). $\endgroup$ – Raphael Jul 31 '12 at 15:01
  • 1
    $\begingroup$ 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 $\endgroup$ – Sasho Nikolov Jul 31 '12 at 18:31
  • $\begingroup$ 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$. $\endgroup$ – Sasho Nikolov Aug 1 '12 at 0:05
  • 1
    $\begingroup$ What is the complexity of Weighted-MAXSAT? $\endgroup$ – Omar Shehab Feb 8 '15 at 4:59

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.