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:
- 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. - 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.
- 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.
- 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.
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