Complexity of Propositional Logics in Team Semantics

Miika Hannula, Juha Kontinen, Jonni Virtema, Heribert Vollmer

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:

  1. Satisfiability (SAT): Does there exist a non-empty team that satisfies the formula?
  2. Validity (VAL): Is the formula satisfied by all non-empty teams?
  3. 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.

Baseline complexity results for standard Propositional Logic (PL) and Dependence Logic (PD).

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:

Comprehensive complexity results for SAT, VAL, and MC across Propositional Independence, Inclusion, and Team logics.

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

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.
BibTeX
@inproceedings{hannula2015complexity,
  author = {Miika Hannula and Juha Kontinen and Jonni Virtema and Heribert Vollmer},
  title = {{Complexity of Propositional Logics in Team Semantics}},
  booktitle = {MFCS},
  year = {2015},
  doi = {10.1007/978-3-662-48057-1\_21},
}
Figure