Complexity of Reasoning with Cardinality Minimality Conditions
Nadia Creignou, Frédéric Olive, Johannes Schmidt
Abstract
Many AI-related reasoning problems are based on the problem of satisfiability of propositional formulas with some cardinality-minimality condition. While the complexity of the satisfiability problem (SAT) is well understood when considering systematically all fragments of propositional logic within Schaefer’s framework, this is not the case when such minimality condition is added. We consider the CardMinSat problem, which asks, given a formula φ and an atom x, whether x is true in some cardinality-minimal model of φ. We completely classify the computational complexity of the CardMinSat problem within Schaefer’s framework, thus paving the way for a better understanding of the tractability frontier of many AI-related reasoning problems. To this end we use advanced algebraic tools.
BibTeX
@article{Creignou_Olive_Schmidt_2023, title={Complexity of Reasoning with Cardinality Minimality Conditions}, volume={37}, url={https://ojs.aaai.org/index.php/AAAI/article/view/25507}, DOI={10.1609/aaai.v37i4.25507}, abstractNote={Many AI-related reasoning problems are based on the problem of satisfiability of propositional formulas with some cardinality-minimality condition. While the complexity of the satisfiability problem (SAT) is well understood when considering systematically all fragments of propositional logic within Schaefer’s framework, this is not the case when such minimality condition is added. We consider the CardMinSat problem, which asks, given a formula φ and an atom x, whether x is true in some cardinality-minimal model of φ. We completely classify the computational complexity of the CardMinSat problem within Schaefer’s framework, thus paving the way for a better understanding of the tractability frontier of many AI-related reasoning problems. To this end we use advanced algebraic tools.}, number={4}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Creignou, Nadia and Olive, Frédéric and Schmidt, Johannes}, year={2023}, month={Jun.}, pages={3932-3940} }