Polynomial algorithm of limited propositional deduction

For the problem of propositional satisfiability a polynomial algorithm of limited propositional deduction is proposed which can be viewed as a sort of boolean constraint propagation mechanism. It can be embodied in a backtracking search program for propositional satisfiability problems to make search efficient. The efficiency is gained in two ways: One is to use the algorithm to derive literals so as to overcome the ambiguities in search. The other is to exploit the consequence sets of unbound atoms generated during limited deduction as a heuristic measure for possible choices. The experiments have shown remarkable improvement in reducing search space. Project supported by the “863” High-Tech Program of China.