1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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