1
$\begingroup$

In question How to reduce MaxUNSAT to MaxSAT? I was asking, how to reduce the MaxUNSAT problem to MaxSAT. With help of the given answer I could give a polynomial reduction : $MaxUNSAT \leq decisionProblemMaxUNSAT \leq SAT \leq MaxSAT$.

Question: Is there a more direct reduction without much overhead from MaxUNSAT to MaxSAT (or to minUNSAT)?

Because the two problems are very similiar, it seems there is a more direct reduction, but I could not figure out one.

Something like $MaxUNSAT(\phi) = MaxSAT(\neg\phi)$ (which does not work).

Improve this question
$\endgroup$

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.