Is MAX-SAT NP-hard?

5

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?

John Threepwood

Posted 2012-07-30T15:10:19.573

Reputation: 239

2

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 (http://en.wikipedia.org/wiki/Optimization_problem#NP_optimization_problem)

– Luke Mathieson – 2012-07-31T01:13:09.703

1

Regarding the relationship of NP and NPO, see also here and here.

– Raphael – 2012-07-31T07:13:13.177

Answers

9

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.

Yuval Filmus

Posted 2012-07-30T15:10:19.573

Reputation: 245 786

1What is the complexity of Weighted-MAXSAT? – Omar Shehab – 2015-02-08T04:59:08.063

1Regarding question two, $f$ copies the formula and adds the number of clauses (as $k$). – Raphael – 2012-07-31T15:01:29.403

1I 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 – Sasho Nikolov – 2012-07-31T18:31:49.807

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$. – Sasho Nikolov – 2012-08-01T00:05:42.773

Asked: 2012-07-30T15:10:19.573

Viewed: 4 532 times

Active: 2012-07-31T17:37:12.083