Complexity of Reasoning with Cardinality Minimality Conditions
DOI:
https://doi.org/10.1609/aaai.v37i4.25507Keywords:
CSO: Constraint Satisfaction, CSO: Satisfiability, KRR: Belief Change, KRR: Nonmonotonic ReasoningAbstract
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.Downloads
Published
2023-06-26
How to Cite
Creignou, N., Olive, F., & Schmidt, J. (2023). Complexity of Reasoning with Cardinality Minimality Conditions. Proceedings of the AAAI Conference on Artificial Intelligence, 37(4), 3932-3940. https://doi.org/10.1609/aaai.v37i4.25507
Issue
Section
AAAI Technical Track on Constraint Satisfaction and Optimization