MAX SAT Optimization problem

Question

search problem: find the assignment that maximize the number of satisfied clauses

For decision problem: determine whether there is an assignment that satisfies k of clauses.

optimization problem : determine the number of clauses that maximize the number of satisfied clauses ( is this correct?)

If I want to reduce search to optimization, how would I do it? Or how do I use the number of clauses (the answer from optimization problem) to determine the assignment (the search problem)?

Answer 1

For MAX-SAT:

• The optimization problem is, given a CNF, to find the maximal number of clauses that can be satisfied at once.
• The search problem is, given a CNF, to find an assignment satisfying the maximal number of clauses.
• The decision problem is, given a CNF and a threshold $k$, whether there is an assignment that satisfies at least $k$ clauses.

To reduce from search to optimization, use the self-reducibility of SAT: pick a variable $x$, and try substituting $x=0$ and $x=1$, using your optimization oracle to determine which of these partial assignments leads to an assignment satisfying the maximum number of clauses.