Solving Higher-Order Quantified Boolean Satisfiability via Higher-Order Model Checking

Hiroshi Unno, Takeshi Tsukada, Jie-Hong Roland JiangAAAI 2025 · DOI

Introduction

While Boolean Satisfiability (SAT) and Quantified Boolean Formulas (QBF) are well-studied, Higher-Order Quantified Boolean Satisfiability (HOSAT) has remained largely theoretical due to its extreme complexity. HOSAT allows quantification over functions and higher-order functions, making it "TOWER-complete" and capable of succinctly encoding problems far beyond the reach of standard SAT solvers. This paper introduces HOMCSAT, the first practical solver for HOSAT, achieved by reducing the problem to Higher-Order Model Checking (HOMC).

Methodology

The core innovation lies in bridging the gap between logic and formal verification. The authors propose a multi-step reduction process:

  1. Reduction to Functional Programs: HOSAT formulas are transformed into higher-order functional programs. The satisfiability of the original formula is equivalent to the program evaluating to true.
  2. Enumeration Structures: To handle finite but massive domains of higher-order functions, the authors introduced "enumeration structures." These structures allow the program to inductively iterate through all possible functions of a specific type using a linear-time reduction, preventing the exponential blow-up typically associated with naive translations.
  3. Skolem Function Synthesis: Beyond simple satisfiability checks, the method allows for the extraction of Skolem functions (witnesses) from the internal proof state of the model checker, specifically utilizing intersection types.
  4. Implementation: HOMCSAT utilizes the state-of-the-art HORSAT2 as its backend model-checking engine.

Experimental Evaluation

To evaluate HOMCSAT, a new benchmark set of 21 HOSAT instances was curated. These instances range from theoretical logic puzzles and relational properties (e.g., symmetry, transitivity) to complex set theory theorems like the Schröder-Bernstein theorem. The benchmarks also include "order-3" and "order-4" problems to test the limits of quantifier nesting and function arity.

Experimental results of HOMCSAT on various HOSAT benchmark instances.

Results and Insights

The evaluation demonstrated that HOMCSAT is a viable tool for solving previously inaccessible logic problems. Key findings include:

  • Performance: Many complex instances were solved rapidly. For example, the Schröder-Bernstein theorem was verified in approximately 0.152 seconds.
  • Scalability: The solver successfully handled higher-order problems (up to order-4), proving the robustness of the reduction method.
  • Correctness: HOMCSAT consistently provided correct SAT/UNSAT results for all instances that did not time out or exceed memory limits.

The "aha moment" of this research is the realization of a natural correspondence: higher-order variables in logic map directly to higher-order variables in functional programming. By leveraging this connection, the research demonstrates that tools designed for software verification can be repurposed to solve high-complexity logic problems.

Limitations and Future Directions

Despite its success, HOMCSAT faces challenges with "extensive branching" caused by numerous quantifiers, which can lead to timeouts (T/O) or memory exhaustion (M/O) in larger benchmarks. Future work will focus on:

  • Symbolic Optimizations: Integrating Binary Decision Diagrams (BDDs) or Zero-suppressed BDDs (ZDDs) to represent internal states more compactly.
  • Algorithmic Cross-Pollination: Incorporating classic SAT/QBF techniques—such as abstraction, pruning, and propagation—directly into higher-order model checkers to enhance performance on logic-heavy workloads.

Summary updated

BibTeX
@inproceedings{unno2025solving,
  author = {Hiroshi Unno and Takeshi Tsukada and Jie-Hong Roland Jiang},
  title = {{Solving Higher-Order Quantified Boolean Satisfiability via Higher-Order Model Checking}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i11.33237},
}

Loading related content...

Figure