On the Structure of the Boolean Satisfiability Problem: A Survey
ACM Computing Surveys · 31.03.2023 · 55 (3) · 1-34
DOI: 10.1145/3491210 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Computing Surveys, online erschienen am 30.03.2022. Verfasst von Tasniem Nasser Alyahya und 2 weiteren Autor:innen. Die Arbeit wurde bisher 29-mal zitiert (Crossref) und nennt 111 Literaturangaben.
Abstract (Originalsprache)
The Boolean satisfiability problem (SAT) is a fundamental NP-complete decision problem in automated reasoning and mathematical logic. As evidenced by the results of SAT competitions, the performance of SAT solvers varies substantially between different SAT categories (random, crafted, and industrial). A suggested explanation is that SAT solvers may exploit the underlying structure inherent to SAT instances. There have been attempts to define the structure of SAT in terms of structural measures such as phase transition, backbones, backdoors, small-world, scale-free, treewidth, centrality, community, self-similarity, and entropy. Still, the empirical evidence of structural measures for SAT has been provided for only some SAT categories. Furthermore, the evidence has not been theoretically proven. Also, the impact of structural measures on the behavior of SAT solvers has not been extensively examined. This work provides a comprehensive study on structural measures for SAT that have been presented in the literature. We provide an overview of the works on structural measures for SAT and their relatedness to the performance of SAT solvers. Accordingly, a taxonomy of structural measures for SAT is presented. We also review in detail important applications of structural measures for SAT, focusing mainly on enhancing SAT solvers, generating SAT instances, and classifying SAT instances.
Zitieren
APA
Alyahya, T. N., Menai, M. E. B., & Mathkour, H. (2023). On the Structure of the Boolean Satisfiability Problem: A Survey. ACM Computing Surveys, 55(3), 1-34. https://doi.org/10.1145/3491210
Vancouver
Alyahya TN, Menai MEB, Mathkour H. On the Structure of the Boolean Satisfiability Problem: A Survey. ACM Computing Surveys. 2023;55(3):1-34. doi:10.1145/3491210
BibTeX
@article{Alyahya2023,
author = {Alyahya, Tasniem Nasser and Menai, Mohamed El Bachir and Mathkour, Hassan},
title = {On the Structure of the Boolean Satisfiability Problem: A Survey},
journal = {ACM Computing Surveys},
year = {2023},
volume = {55},
number = {3},
pages = {1--34},
doi = {10.1145/3491210}
}
EUVIMED