2023/03/02 by Nadia Creignou, Creignou, Nadia, Frédéric Olive +3
Computer Science · #Advanced Algebra and Logic #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Semantic Web and Ontologies
paper · pdf · doi:10.48550/arxiv.2303.01571
openalex publication_date 2023/03/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (STOC 1978) this is not the case when such minimality condition is added. We consider the CardMinSat problem, which asks, given a formula F and an atom x, whether x is true in some cardinality-minimal model of F. 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 developed by (Schnoor & Schnoor 2008) and (Lagerkvist 2014).