Complexity of reasoning with cardinality minimality conditions
Article No.: 438, Pages 3932 - 3940
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.
References
[1]
Böhler, E.; Reith, S.; Schnoor, H.; and Vollmer, H. 2005. Bases for Boolean co-clones. Inf. Process. Lett., 96(2): 59-66.
[2]
Creignou, N.; Egly, U.; and Schmidt, J. 2014. Complexity Classifications for Logic-Based Argumentation. ACM Trans. Comput. Log., 15(3): 19:1-19:20.
[3]
Creignou, N.; Ktari, R.; and Papini, O. 2017. Complexity of Model Checking for Cardinality-Based Belief Revision Operators. In In Proc. ECSQARU 2017, volume 10369 of LNCS, 387-397. Springer.
[4]
Creignou, N.; Olive, F.; and Schmidt, J. 2023. Complexity of Reasoning with Cardinality Minimality Conditions. CoRR, abs/2303.01571.
[5]
Creignou, N.; Pichler, R.; and Woltran, S. 2018. Do Hard SAT-Related Reasoning Tasks Become Easier in the Krom Fragment? Log. Methods Comput. Sci., 14(4).
[6]
Creignou, N.; and Vollmer, H. 2008. Boolean Constraint Satisfaction Problems: When Does Post's Lattice Help? In Creignou, N.; Kolaitis, P. G.; and Vollmer, H., eds., Complexity of Constraints - An Overview of Current Research Themes [Result of a Dagstuhl Seminar], volume 5250 of Lecture Notes in Computer Science, 3-37. Springer.
[7]
Creignou, N.; and Zanuttini, B. 2006. A Complete Classification of the Complexity of Propositional Abduction. SIAM J. Comput., 36(1): 207-229.
[8]
Dalal, M. 1988. Investigations into Theory of Knowledge Base Revision. In Proc. AAAI, 475-479. AAAI Press / The MIT Press.
[9]
Eiter, T.; and Gottlob, G. 1992. On the Complexity of Propositional Knowledge Base Revision, Updates, and Counter-factuals. Artif. Intell., 57(2-3): 227-270.
[10]
Eiter, T.; and Gottlob, G. 1995. The Complexity of Logic-Based Abduction. J. ACM, 42(1): 3-42.
[11]
Gasarch, W. I.; Krentel, M. W.; and Rappoport, K. J. 1995. OptP as the Normal Behavior of NP-Complete Problems. Mathematical Systems Theory, 28(6): 487-514.
[12]
Jeavons, P. G. 1998. On the algebraic structure of combinatorial problems. Theor. Comput. Sci., 200: 185-204.
[13]
Krentel, M. W. 1988. The Complexity of Optimization Problems. J. Comput. Syst. Sci., 36(3): 490-509.
[14]
Lagerkvist, V. 2014. Weak bases of Boolean co-clones. Inf. Process. Lett., 114(9): 462-468.
[15]
Liberatore, P.; and Schaerf, M. 2001. Belief Revision and Update: Complexity of Model Checking. J. Comput. Syst. Sci., 62(1): 43-72.
[16]
Mahmood, Y.; Meier, A.; and Schmidt, J. 2021. Parameterized complexity of abduction in Schaefer's framework. J. Log. Comput., 31(1): 266-296.
[17]
Nordh, G. 2004. A Trichotomy in the Complexity of Propositional Circumscription. In Baader, F.; and Voronkov, A., eds., Logic for Programming, Artificial Intelligence, and Reasoning, 11th International Conference, LPAR 2004, Montevideo, Uruguay, March 14-18, 2005, Proceedings, volume 3452 of Lecture Notes in Computer Science, 257269. Springer.
[18]
Nordh, G.; and Zanuttini, B. 2008. What makes propositional abduction tractable. Artif. Intell., 172(10): 1245-1284.
[19]
Nordh, G.; and Zanuttini, B. 2009. Frozen boolean partial co-clones. In Proc. ISMVL, 120-125.
[20]
Papadimitriou, C. H. 1994. Computational Complexity. Addison-Wesley.
[21]
Post, E. L. 1941. The two-valued iterative systems of mathematical logic. Annals of Mathematical Studies, 5: 1-122.
[22]
Schaefer, T. J. 1978. The Complexity of Satisfiability Problems. In Proc. STOC, 216-226. ACM.
[23]
Schnoor, H.; and Schnoor, I. 2008. Partial polymorphisms and constraint satisfaction problems. In Creignou, N.; Kolaitis, P. G.; and Vollmer, H., eds., Complexity of Constraints, volume 5250, 229-254. Berlin Heidelberg: Springer Verlag.
[24]
Wagner, K. 1988. On Restricting the Access to an NP-Oracle. In Proc. ICALP, volume 317 of LNCS, 682-696. Springer.
Recommendations
Primitivity, Uniform Minimality, and State Complexity of Boolean Operations
A minimal deterministic finite automaton (DFA) is uniformly minimal if it always remains minimal when the final state set is replaced by a non-empty proper subset of the state set. We prove that a permutation DFA is uniformly minimal if and only if its ...
Extremal minimality conditions on automata
In this paper we investigate the minimality problem of DFAs by varying the set of final states. In other words, we are interested on how the choice of the final states can affect the minimality of the automata. The state-pair graph is a useful tool to ...
The complexity of reasoning with cardinality restrictions and nominals in expressive description logics
We study the complexity of the combination of the Description Logics ALCQ and ALCQI with a terminological formalism based on cardinality restrictions on concepts. These combinations can naturally be embedded into C2, the two variable fragment of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2023 Association for the Advancement of Artificial Intelligence.
Sponsors
- Association for the Advancement of Artificial Intelligence
Publisher
AAAI Press
Publication History
Published: 07 February 2023
Qualifiers
- Research-article
- Research
- Refereed limited
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Nov 2024