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 traditional propositional logic, a formula is evaluated against a single truth assignment. Team semantics generalizes this framework by evaluating formulas against sets of assignments, known as "teams." This paradigm is essential for formalizing concepts such as dependence, independence, and inclusion, which find applications in fields ranging from database theory to quantum physics.
While first-order and modal variants of these logics have been extensively studied, their purely propositional counterparts—Propositional Independence Logic ($PL[\perp_c]$), Propositional Inclusion Logic ($PL[\subseteq]$), and Propositional Team Logic ($PL[\sim]$)—have lacked a comprehensive complexity classification. This paper fills that gap by analyzing three fundamental decision problems:
- Satisfiability (SAT): Does there exist a non-empty team that satisfies the formula?
- Validity (VAL): Is the formula satisfied by all non-empty teams?
- Model Checking (MC): Given a specific team and a formula, is the formula satisfied?
As a baseline, standard Propositional Logic (PL) and Propositional Dependence Logic (PD) exhibit relatively lower complexities for these problems, as shown in the table below.
Methodology
The authors utilize complexity theory and polynomial-time reductions to establish upper and lower bounds. Key methodological innovations include:
- Singleton Team Reductions: For independence logic, the authors demonstrate that a formula is satisfiable if and only if it is satisfied by a team of size one. This structural property allows for a direct reduction to standard propositional SAT.
- Turing Machine Simulations: To establish the AEXPTIME(poly) lower bound for team logic, the authors generalize Orponen’s characterization of the exponential-time hierarchy. They construct a polynomial-time reduction simulating an Alternating Turing Machine with polynomially many oracle queries using the constructs of $PL[\sim]$.
- Alternating Algorithms: For model-checking in team logic, they design an APTIME (Alternating Polynomial Time) algorithm, which corresponds to the PSPACE complexity class.
Complexity Classification Results
The core contribution of this work is the systematic classification of Independence, Inclusion, and Team logics. The results are summarized in the following table:
Key Insights
- The Impact of Classical Negation: In team semantics, standard negation is typically a "dual negation" that fails the law of excluded middle. Introducing classical negation ($~$) causes a complexity explosion; the SAT problem jumps from NP or EXPTIME to AEXPTIME(poly)-complete, highlighting the immense expressive power classical negation provides.
- Independence SAT Simplicity: Despite the complexity of evaluating independence across a team, checking if an independence logic formula is satisfiable is only NP-complete. This is due to the "singleton property," where any satisfiable formula must be satisfiable by a team of size one.
- Inclusion VAL Efficiency: Validity for inclusion logic ($PL[\subseteq]$) is coNP-complete, matching standard propositional logic. This occurs because an inclusion formula is valid if and only if it is satisfied by all singleton teams.
Conclusion and Future Work
This research provides a near-complete map of the complexity landscape for propositional team logics. One remaining open question is the exact complexity of Validity for Propositional Independence Logic ($VAL(PL[\perp_c])$), which is currently bounded between NEXPTIME-hard and coNEXPTIME^NP. Future research may extend these findings to other connectives, such as the intuitionistic implication operator ($⊸$) used in inquisitive semantics.
Summary updated