3
$\begingroup$

I have ~4000 variables that are used in ~5000 logical formulas, where each formula consists only of conjunctions of the (non-negated) variables. I want to find the maximum number of satisfied formulas, given the number of variables that I can set to 1.

Does this problem have a name? Is it equivalent to the MAX-SAT problem? Which algorithm would be applicable to solve it exactly or using heuristics?

$\endgroup$
3
$\begingroup$

You are addressing a problem of the same type. if you use De Morgan law your problem will become MIN-SAT which is NP-HARD

checkout THE MINIMUM SATISFIABILITY PROBLEM

$\endgroup$
  • $\begingroup$ But how can I restrict the number of variables that can be set to 1? $\endgroup$ – box Nov 25 '17 at 16:25
  • $\begingroup$ I'm not sure what exactly you are asking for, but if you mean: Given a set of formlas on the set of variables V (where you have |V| = n variables). and you want to select k variables and check how many formulas you can satisfy based on those k variables. Then you can pick the k variables, and set the rest to 0 so only the k variables can force a formula to be satisfied :) $\endgroup$ – Khazam Alhamdan Dec 24 '17 at 16:55

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.