Integrating Boolean Satisfiability Algorithms into Bayesian Networks for Accelerated Deterministic Inference

Exact probabilistic inference in Bayesian Networks (BNs) becomes increasingly expensive as network size and structural complexity grow, limiting its applicability in time-sensitive decision-support systems. This study presents a hybrid inference framework that accelerates the deterministic component of Bayesian reasoning by integrating Boolean Satisfiability (SAT) techniques with Bayesian Networks. The proposed approach transforms deterministic conditional probability table (CPT) entries into conjunctive normal form (CNF), enabling SAT-based logical inference over deterministic constraints while preserving the original Bayesian model for probabilistic reasoning. The framework was evaluated on 25 benchmark Bayesian networks using five independent executions per dataset under identical experimental conditions. Performance was assessed through execution time, instrumented operation counts, and inference coverage, with results reported as mean values, standard deviations, and 95% confidence intervals. Experimental results demonstrate substantial reductions in deterministic inference time while maintaining high coverage of deterministic variable assignments across the evaluated benchmarks. Throughout this paper, the reported performance gains refer exclusively to empirical reductions in execution time and instrumented operation counts. They should not be interpreted as evidence of a reduction in the asymptotic computational complexity of exact Bayesian inference, which remains #P-complete in the general case. Rather, the proposed framework provides an efficient mechanism for accelerating deterministic logical inference within Bayesian Networks under the evaluated benchmark conditions.