Complexity of Reasoning with Cardinality Minimality Conditions


  • Nadia Creignou Aix-Marseille Université
  • Frédéric Olive Aix-Marseille Université
  • Johannes Schmidt Jönköping University



CSO: Constraint Satisfaction, CSO: Satisfiability, KRR: Belief Change, KRR: Nonmonotonic Reasoning


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.




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.



AAAI Technical Track on Constraint Satisfaction and Optimization