Algorithms for Deciding Counting Quantifiers over Unary Predicates

Marcelo Finger, Glauber De BonaAAAI 2017 · DOI

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:

  1. Normalization: Formulas are converted into a standard form where counting is restricted to atomic predicates in polynomial time.
  2. 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.
  3. 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.
  4. 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.

Figure 1: Satisfiability phase transition for CQU instances across different problem scales.

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.

Figure 2: Average solving time vs. satisfiability percentage, showing the peak in computational effort at the phase transition.

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

BibTeX
@inproceedings{finger2017algorithms,
  author = {Marcelo Finger and Glauber De Bona},
  title = {{Algorithms for Deciding Counting Quantifiers over Unary Predicates}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.11129},
}
Figure