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


Your Answer

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

Browse other questions tagged or ask your own question.