Complexity Results in Team Semantics: Nonemptiness Is Not So Complex
arXiv:2510.08122h-index: 20
AI Analysis
Establishes complexity bounds for a logic in team semantics, providing foundational results for researchers in team semantics and logic.
The paper studies convex logics in team semantics, focusing on propositional logic with the nonemptiness atom NE. It proves that satisfiability is NP-complete, validity is coNP-complete, and model-checking is in P.
We initiate the study of the complexity-theoretic properties of convex logics in team semantics. We focus on the extension of classical propositional logic with the nonemptiness atom NE, a logic known to be both convex and union closed. We show that the satisfiability problem for this logic is NP-complete, that its validity problem is coNP-complete, and that its model-checking problem is in P.