TL;DR
This paper investigates the computational complexity of various predicate logics that use "team semantics," a framework for modeling information and dependencies. The authors prove that the satisfiability of two-variable fragments of independence and inclusion logics are NEXPTIME-complete, and crucially, that the validity problem for two-variable dependence logic is undecidable, resolving a long-standing open question.
What Problem Does This Paper Address?
Team semantics offers a powerful way to express notions of dependency and independence between variables in logical formulas, going beyond traditional first-order logic. While the expressive power of these logics (like dependence logic, independence logic, and inclusion logic) has been well-studied, their computational complexity, particularly for satisfiability and validity problems, has remained a significant open area. Specifically, the decidability of the validity problem for two-variable dependence logic was a known challenge. This paper aims to fill these gaps by providing precise complexity bounds for various fragments of these team-semantic logics.
Methods
The core of the paper involves establishing translations between different logics and analyzing their computational complexity. A key technique is the use of "generalized atoms," which are a flexible way to represent various dependency and independence relations within a unified framework. The authors prove a general theorem showing that for many team-semantic logics extended with such generalized atoms, their two-variable fragments have NEXPTIME-complete satisfiability problems. This is achieved by translating formulas of these logics into a known decidable logic (specifically, fragments of second-order logic with counting quantifiers, $\Sigma_1(\text{FOC}^2)$) and leveraging existing complexity results.
For the undecidability result concerning two-variable dependence logic, the authors employ a reduction from the "non-tiling problem," a known undecidable problem, to the validity problem of dependence logic. This reduction involves constructing specific formulas that capture the properties of gridlike structures and their tilability.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Unified Framework for Dependencies: The concept of "generalized atoms" provides a powerful and flexible way to capture diverse dependency and independence relations, allowing for a more uniform analysis of different team-semantic logics.
- Decidability of Two-Variable Fragments: The paper establishes that for a broad class of team-semantic logics, their two-variable fragments are decidable and, more precisely, NEXPTIME-complete for satisfiability. This is a significant step towards understanding the computational landscape of these logics.
- Undecidability of Dependence Logic Validity: The most striking result is the proof that the validity problem for two-variable dependence logic is undecidable. This resolves a long-standing open problem and highlights a fundamental limitation in the decidability of even restricted forms of dependence logic.
- Non-Tiling as a Tool for Undecidability: The paper demonstrates the utility of the "non-tiling problem" (a variant of the tiling problem) as a source for proving undecidability results in logic, offering an alternative to more traditional reductions.
Key Results
- The satisfiability problems for the two-variable fragments of independence logic and inclusion logic are NEXPTIME-complete.
- The satisfiability and finite satisfiability problems for the two-variable fragments of dependence logic, inclusion logic, exclusion logic, inclusion/exclusion logic, and independence logic are all NEXPTIME-complete.
- The validity problem of two-variable dependence logic is undecidable.
- The satisfiability and finite satisfiability problems for $\exists^*\forall^*$ sentences of dependence logic are NEXPTIME-complete for bounded arity vocabularies and 2NEXPTIME in the general case.
Limitations and Future Work
The paper acknowledges that its approach provides a general framework for analyzing team-semantic logics and implies results for other related systems. Future work could involve identifying further interesting systems with decidable satisfiability problems. The authors also mention that their undecidability proof for dependence logic uses a reduction from the non-tiling problem, and that attempts to use the standard tiling problem were unsuccessful, suggesting that the choice of reduction problem can be crucial. Further exploration of the relationship between different reduction techniques and the complexity of team-semantic logics would be valuable.
Summary updated