A Simplifier for Propositional Formulas with Many Binary Clauses

Abstract

Deciding whether a propositional formula in conjunctive normal form is satisfiable (SAT) is an NPcomplete problem. The problem becomes linear when the formula contains binary clauses only. Interestingly, the reduction to SAT of a number of well-known and important problems – such as classical AI planning and automatic test pattern generation for circuits – yields formulas containing many binary clauses. In this paper we introduce and experiment with 2- SIMPLIFY , a formula simplifier targeted at such problems. 2- SIMPLIFY constructs the implication graph corresponding to the binary clauses in the formula and uses this graph to deduce new unit literals. The deduced literals are used to simplify the formula and update the graph, and so on, until stabilization. Finally, we use the graph to construct an equivalent, simpler set of binary clauses. Experimental evaluation of this simplifier on a number of bench-mark formulas produced by encoding AI planning problems prove 2- SIMPLIFY to be fast and effective.