Knowledge Compilation for Incremental and Checkable Stochastic Boolean Satisfiability

Knowledge Compilation for Incremental and Checkable Stochastic Boolean Satisfiability

Che Cheng, Yun-Rong Luo, Jie-Hong R. Jiang

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 1862-1872. https://doi.org/10.24963/ijcai.2024/206

Knowledge compilation has proven effective in (weighted) model counting, uniquely supporting incrementality and checkability. For incrementality, compiling an input formula once suffices to answer multiple queries, thus reducing the total solving effort. For checkability, the compiled formula is amenable to producing machine-checkable proofs for verification, thus strengthening the solver’s reliability. In this work, we extend knowledge compilation from model counting to stochastic Boolean satisfiability (SSAT) solving by generalizing the dec-DNNF representation to accommodate the SSAT quantifier structure and integrate it into SharpSSAT, a state-of-the-art SSAT solver. We further study proof generation from the compiled representation and extend CPOG, a certified model-counting toolchain, to generate proofs for certifying the results of SharpSSAT. Experimental results show the benefits of the proposed knowledge compilation approach for SSAT in sharing computation efforts for multiple queries and producing checkable dec-DNNF logs with negligible overhead.
Keywords:
Constraint Satisfaction and Optimization: CSO: Satisfiabilty
Constraint Satisfaction and Optimization: CSO: Constraint satisfaction
Constraint Satisfaction and Optimization: CSO: Solvers and tools
Knowledge Representation and Reasoning: KRR: Knowledge compilation