Complexity Results in Team Semantics: Nonemptiness Is Not So Complex
arXiv:2510.08122 · doi:10.1007/978-3-032-21540-6_1
Abstract
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.
14 pages