Abstract
This paper presents a practical decision procedure for the Counting Quantifiers over Unary predicates (CQU) fragment of first-order logic. Although CQU is NP-complete, existing algorithms often lack the efficiency required for practical applications. We propose a hybrid approach combining Integer Linear Programming (ILP) with a novel SAT-based column generation technique. Our evaluation on synthetic benchmarks demonstrates the effectiveness of this method and identifies a distinct phase transition where computational difficulty peaks.
Introduction
Automated reasoning systems frequently encounter the need to process cardinality constraints—statements regarding the number of objects satisfying specific properties. While general first-order logic with counting is often computationally intractable, the unary fragment (CQU) remains NP-complete. This paper addresses the lack of practical solvers for CQU by introducing a formal framework and an implementation that leverages the strengths of both SAT solvers and ILP.
Methodology
The decision procedure involves transforming CQU satisfiability into a numerical optimization problem through several key stages:
- Normalization: Formulas are converted into a standard form where counting is restricted to atomic predicates in polynomial time.
- Algebraic Representation: The problem is modeled as a system of linear inequalities $Ax \bowtie b$. Each column in $A$ represents a "coherent elementary term," a logically consistent combination of properties.
- SAT-Based Column Generation: To manage the potentially exponential number of columns ($2^k$), we use a SAT solver as an oracle. It identifies new columns that could lead to a feasible solution without requiring the full matrix to be pre-computed.
- Integer Constraints: A branch-and-bound search ensures that the resulting object counts are integers, preventing fractional solutions.
Experimental Results
We evaluated the solver using synthetic random CQU-SAT instances, focusing on the ratio of constraints to variables ($m/n$).
Phase Transitions
Our results confirm a sharp phase transition in satisfiability. As the $m/n$ ratio increases, instances move from being almost certainly satisfiable to almost certainly unsatisfiable. This transition occurs at a ratio of approximately 4.1, slightly lower than the standard 3-SAT transition of 4.3.
Computational Complexity
The most challenging instances occur at the phase transition point. At this threshold, the average solving time peaks significantly, reflecting the inherent difficulty of problems on the "edge" of satisfiability where the solver must navigate the most constrained search space.
The SAT-based column generation approach proved far more robust than direct SAT reductions, which failed even on small-scale problems (e.g., 6 inequalities and 40 variables).
Conclusion
We have demonstrated a viable, efficient algorithm for deciding CQU satisfiability. By combining SAT-based column generation with ILP, we can handle the exponential search space of logical combinations. Future work will explore extending these techniques to more expressive logics, such as Description Logics, and refining branching heuristics to further improve performance.
Summary updated