An Adaptation of Path Consistency for Boolean Satisfiability: a Theoretical View of the Concept

Abstract

The task of enforcing certain level of consistency in Boolean satisfiability problem (SAT problem) is addressed in this paper. The concept of path-consistency known from the constraint programming paradigm is revisited in this context.

Augmentations how to make path-consistency more suitable for SAT are specifically studied.

Keywords

• Path-Consistency
• Boolean Satisfiability