patternMinor
Is MAX-SAT NP-hard?
Viewed 0 times
satmaxhard
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#2956, answer score: 9
Revisions (0)
No revisions yet.