Introduction
Modern Boolean Satisfiability (SAT) solvers are critical components in fields ranging from hardware verification to artificial intelligence planning. These solvers often process formulas containing millions of clauses—logical constraints that must be satisfied. To maintain efficiency, solvers employ preprocessing techniques to identify and remove redundant clauses. A clause is redundant if its removal does not change the satisfiability of the overall formula.
The primary challenge lies in the cost of detection. Determining if a clause is globally redundant is typically as computationally expensive as solving the SAT problem itself. Consequently, researchers focus on "local redundancy," which can be determined by examining only a clause’s resolution neighborhood—the set of clauses it interacts with directly. While "blocked clauses" have long served as a standard for local redundancy, this research explores whether more general definitions of "bad neighbors" can be identified to further simplify formulas.
A Hierarchy of Redundancy
The authors propose a hierarchy of redundancy properties by generalizing the established concept of blocked clauses. This hierarchy moves from simple, easily detectable redundancies to more complex, broader categories:
- Blocked Clauses: The baseline. A clause is blocked if it contains a literal that, when resolved with its neighbors, always produces a tautology (e.g., $x \lor \neg x$).
- Set-Blocked Clauses: This generalizes the concept by looking for a set of literals rather than a single one. A clause is set-blocked if flipping the truth values of this entire set simultaneously ensures that all neighboring clauses remain satisfied.
- Super-Blocked Clauses: This is the most sophisticated tier. It accounts for "external variables"—those appearing in the neighborhood but not in the clause itself. A clause is super-blocked if it becomes set-blocked for every possible assignment of these external variables.
The paper establishes a clear nesting of these techniques: Tautologies $\subset$ Pure Literals $\subset$ Blocked $\subset$ Set-Blocked $\subset$ Super-Blocked. Each successive level allows for the removal of more clauses but increases the computational effort required for detection.
Theoretical Generality and Locality
A significant theoretical contribution of this work is the proof that super-blocking represents the most general form of local redundancy possible. The authors demonstrate that any redundancy property relying solely on the resolution neighborhood is either a subset of super-blocking or is not a valid redundancy property. This reinforces the power of local analysis; one does not need a global view of a massive formula to identify and prune "locally useless" constraints.
Computational Complexity
The practical utility of these properties depends on the time required to detect them. The authors mapped the computational complexity for both set-blocking and super-blocking under different conditions, ranging from unrestricted set sizes to bounded sets.
As shown in the table above, set-blocking is generally NP-complete. However, if the number of literals allowed to be flipped ($k$) is bounded, the problem becomes solvable in polynomial time (P). Super-blocking is significantly more complex, reaching $\Pi^P_2$-completeness in the unrestricted case and remaining co-NP-complete even when the set size is bounded. This high complexity reflects the "for all... there exists..." logical structure inherent in the super-blocking definition.
Conclusion and Future Directions
While super-blocked clauses offer the most general theoretical framework for local redundancy, their high computational overhead presents a challenge for immediate integration into SAT solvers. The $\Pi^P_2$-completeness suggests that the time spent finding these clauses might outweigh the benefits of their removal.
Future research will likely focus on two areas:
- Heuristic Development: Creating efficient algorithms to find "easy" instances of set-blocked or super-blocked clauses to test their impact on real-world SAT solver performance.
- Extension to QBF: Investigating the application of these local redundancy notions to Quantified Boolean Formulas (QBF), which are more expressive and computationally demanding than standard propositional logic.
Summary updated