Abstract
We classify the computational complexity of the satisfiability, validity and model-checking problems for propositional independence, inclusion, and team logic. Our main result shows that the satisfiability and validity problems for propositional team logic are complete for alternating exponential-time with polynomially many alternations.
Introduction
In standard propositional logic, a formula is evaluated against a single truth assignment (e.g., $x=true, y=false$). However, many modern scientific and database applications require reasoning about dependencies, independencies, and inclusions between variables across sets of data. To formalize this, researchers use team semantics, where formulas are evaluated against a "team"—a set of assignments.
While first-order dependence logic and its variants are well-studied, their purely propositional counterparts have received surprisingly little attention. This paper fills that gap by systematically classifying the computational complexity of three core decision problems—Satisfiability (SAT), Validity (VAL), and Model Checking (MC)—for three specific propositional logics: Propositional Independence Logic (PL[$\perp_c$]), Propositional Inclusion Logic (PL[$\subseteq$]), and Propositional Team Logic (PL[$\sim$]).
Methodology
As a theoretical computer science paper, the authors rely on complexity-theoretic reductions and algorithm design to establish tight bounds for the targeted logics.
- Upper Bounds: The authors design alternating Turing machine algorithms to establish upper bounds. For example, they provide an APTIME (Alternating Polynomial Time) algorithm for model checking, which directly translates to a PSPACE upper bound.
- Lower Bounds: They use reductions from known hard problems, such as Quantified Boolean Formulas (TQBF) for PSPACE-completeness.
- Novel Reductions: To prove the AEXPTIME(poly) completeness of Propositional Team Logic, the authors generalize a known theorem by Orponen. They relate AEXPTIME(poly) to polynomial-time alternating Turing machines that query oracles obtained from a polynomial-length quantifier prefix, and then show how to simulate these complex computations entirely within the logic.
Key Insights
Team semantics drastically alters the complexity landscape. Evaluating formulas over sets of assignments allows propositional logic to express highly complex properties, pushing standard decision problems far beyond their traditional NP/coNP boundaries.
- Classical Negation as a Multiplier: In team semantics, standard negation ($\neg$) is a "dual" negation that doesn't satisfy the law of excluded middle. When true classical negation ($\sim$) is introduced, the logic becomes incredibly expressive. The complexity of SAT and VAL jumps all the way to AEXPTIME(poly).
- Inclusion vs. Independence: Inclusion logic and independence logic behave fundamentally differently. Inclusion logic is "closed under unions" (if two teams satisfy a formula, their union does too), which simplifies its validity problem to coNP. However, its satisfiability is EXPTIME-complete.
- Singletons in Independence SAT: A formula in propositional independence logic is satisfiable if and only if it is satisfied by a singleton team (a team with only one assignment). Because of this, its SAT problem remains NP-complete, identical to standard propositional logic.
Results
The authors successfully classified the complexity of almost all targeted problems, providing a comprehensive map of the landscape for propositional team-based logics.
As shown in the results, Propositional Team Logic (PL[$\sim$]) and logics combining classical negation with inclusion or independence reach AEXPTIME(poly)-completeness for SAT and VAL, and PSPACE-completeness for MC.
Conclusion and Future Work
While most problems are now classified, the exact complexity of the validity problem for Propositional Independence Logic (VAL(PL[$\perp_c$])) remains an open question. The authors proved it is NEXPTIME-hard and sits inside coNEXPTIME$^{NP}$, but could not pin down the exact completeness class. Future directions include extending this study to logics incorporating the intuitionistic implication operator ($\multimap$), which has strong ties to the emerging field of inquisitive semantics.
Summary updated