# MAX SAT Optimization problem

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)?

• 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.