Algorithm to reduce satisfiability java

Is there any algorithm to reduce sat problem.

Satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE. Equally important is to determine whether no such assignments exist, which would imply that the function expressed by the formula is identically FALSE for all possible variabl开发者_运维问答e assignments. In this latter case, we would say that the function is unsatisfiable; otherwise it is satisfiable. To emphasize the binary nature of this problem, it is frequently referred to as Boolean or propositional satisfiability. The shorthand "SAT" is also commonly used to denote it, with the implicit understanding that the function and its variables are all binary-valued.

I have used genetic algorithms to solve this, but it would be easier if is reduced first?.

Take a look at Reduced Order Binary Decision Diagrams (ROBDD). It provides a way of compressing boolean expressions to a reduced canonical form. There's plenty of software around for performing the BDD reduction, the wikipedia link above for ROBDD contains a nice list of external links to other relevant packages at the bottom of the article.

You could probably do a depth-first path-tree search on the formula to identify "paths" - Ie, for (ICanEat && (IHaveSandwich || IHaveBanana)), if "ICanEat" is false, the values in brackets don't matter and can be ignored. So, right there you can discard some edges and nodes.

And, if while you're generating this depth-first search, the current Node resolves to True, you've found your solution.

What do you mean by "reduced", exactly? I'm going to assume you mean some sort of preprocessing beforehand, to maybe eliminate or simplify some variables or clauses first.

It all depends on how much work you want to do. Certainly you should do unit propagation until it completes. There are other, more expensive things you can do. See the pre-processing section of the march_dl page for some examples.