5
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 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, 2012 at 1:13
  • 1
    $\begingroup$ Regarding the relationship of NP and NPO, see also here and here. $\endgroup$
    – Raphael ♦
    Jul 31, 2012 at 7:13
  • $\begingroup$ Somehow I feel that wikipedia article is not correct. $\endgroup$
    – hola
    Aug 18, 2021 at 0:27
  • $\begingroup$ I don't know, but here it says, MAX-SAT is NP-complete. $\endgroup$
    – hola
    Aug 18, 2021 at 0:28

1 Answer 1

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Regarding question two, $f$ copies the formula and adds the number of clauses (as $k$). $\endgroup$
    – Raphael ♦
    Jul 31, 2012 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, 2012 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, 2012 at 0:05
  • 1
    $\begingroup$ What is the complexity of Weighted-MAXSAT? $\endgroup$
    – Omar Shehab
    Feb 8, 2015 at 4:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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