A simple test improves checking satisfiability

AbstractIn many practical cases satisfiability of a set of clauses can be decided before an interpretation is found that satisfies all clauses of the set. We present a test for such an early discovery of satisfiability, EDS, and develop an algorithm, IDP, incorporating EDS and a branching heuristics related to this test. IDP was implemented and tested on a wide variety of instances and showed a high performance and stability with respect to changing the proportion of non-Horn clauses