Solving satisfiability problems through search

摘要

One embodiment of a method for solving an input satisfiability instance includes searching a database for a stored satisfiability instance that matches the input satisfiability instance and outputting a solution to the input satisfiability instance. One embodiment of method for converting an input satisfiability instance into a standardized representation includes applying a plurality of syntactical simplification rules to the input satisfiability instance until no conditions of any of the plurality of syntactical simplification rules can be met, thereby producing a simplified instance, uniformly replacing each variable in the simplified instance with a unique, consecutively chosen even number, annotating each literal in the simplified instance to indicate whether the each literal is positive or negative, ordering all literals in the simplified instance, and ordering all clauses in the simplified instance to produce the standardized representation.