Integrating Boolean Satisfiability Algorithms into Bayesian Networks for Accelerated Deterministic Inference
Algorithms · 08.07.2026 · 19 (7) · 558
DOI: 10.3390/a19070558 ↗Kurz gefasst
Fachartikel in der Zeitschrift Algorithms, online erschienen am 08.07.2026. Verfasst von Efraín Evaristo Díaz Macías und 2 weiteren Autor:innen. Die Arbeit nennt 28 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Universidad Técnica Estatal de Quevedo.
Abstract (Originalsprache)
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.
Förderung
- Universidad Técnica Estatal de Quevedo
Zitieren
APA
Macías, E. E. D., Bazurto, J. S. C., & Bayas, B. W. O. (2026). Integrating Boolean Satisfiability Algorithms into Bayesian Networks for Accelerated Deterministic Inference. Algorithms, 19(7), 558. https://doi.org/10.3390/a19070558
Vancouver
Macías EED, Bazurto JSC, Bayas BWO. Integrating Boolean Satisfiability Algorithms into Bayesian Networks for Accelerated Deterministic Inference. Algorithms. 2026;19(7):558. doi:10.3390/a19070558
BibTeX
@article{Macas2026,
author = {Macías, Efraín Evaristo Díaz and Bazurto, José Steven Cordero and Bayas, Byron Wladimir Oviedo},
title = {Integrating Boolean Satisfiability Algorithms into Bayesian Networks for Accelerated Deterministic Inference},
journal = {Algorithms},
year = {2026},
volume = {19},
number = {7},
pages = {558},
doi = {10.3390/a19070558}
}
EUVIMED