Dependence logic with a majority quantifier

Arnaud Durand, Johannes Ebbing, Juha Kontinen, Heribert Vollmer

Introduction

In the field of descriptive complexity, researchers seek to characterize computational complexity classes through the lens of formal logic. A landmark result in this area is Fagin's Theorem, which establishes that existential second-order logic ($\Sigma^1_1$) captures the complexity class NP. Within this context, dependence logic ($D$), introduced by Väänänen, provides an alternative framework for expressing dependencies between variables. While standard dependence logic is also equivalent to NP, it has historically struggled to reach higher rungs of the complexity ladder, such as the counting hierarchy (CH).

The counting hierarchy consists of complexity classes like PP (Probabilistic Polynomial time) and its oracles, which are essential for problems involving counting and majority-based decision-making. This paper introduces a novel extension of dependence logic, denoted as $D(M)$, by incorporating a majority quantifier ($M$). The authors demonstrate that $D(M)$ is exactly as expressive as second-order logic with majority quantifiers ($SO(Most)$), thereby providing a logical characterization of the counting hierarchy.

Team Semantics and the Majority Quantifier

The fundamental shift in dependence logic is the move from Tarski's semantics (evaluating formulas against single assignments) to team semantics. In this framework, a formula is evaluated against a team—a set of assignments that assign values to a fixed set of variables.

The authors define the majority quantifier $M$ in a way that aligns with the existential and universal quantifiers in dependence logic. For a team $X$, the formula $Mx\phi(x)$ is satisfied if there exists a "majority" of functions $F$ that extend the team. Specifically, it is true if for at least half of all possible functions $F$ mapping each assignment in $X$ to an element in the domain, the resulting extended team $X[F/x]$ satisfies $\phi(x)$. This "global" approach to quantification is what allows the logic to reason about the proportions of satisfying assignments across the entire team structure, moving beyond the "conservative" versions of the quantifier that failed to increase the logic's power beyond NP.

Logical Properties of $D(M)$

The introduction of the majority quantifier leads to several interesting logical consequences that distinguish $D(M)$ from standard first-order or dependence logics:

Downward Closure

Despite its increased expressive power, $D(M)$ retains the downward closure property. This means that if a formula is satisfied by a team $X$, it is also satisfied by any subteam $Y \subseteq X$. This property is a hallmark of many dependence-style logics and remains intact even with the addition of the powerful majority operator.

The Free Variable Property

One of the most surprising findings is that $D(M)$ violates the standard free variable property. In most logical systems, the truth of a formula depends only on the variables that appear free within it. However, in $D(M)$, the truth of a formula can be influenced by variables in the team's domain that do not appear in the formula itself. This occurs because the "majority" is calculated relative to the total number of possible functions over the team's domain; adding an extra variable to the domain changes the total number of possible functions, potentially altering the majority threshold.

Non-Coherence

The authors also prove that $D(M)$ is not $k$-coherent for any $k$. In simpler logics, the truth of a formula on a large team can often be determined by checking its truth on all subteams of a certain size $k$. The failure of $k$-coherence in $D(M)$ underscores the inherent complexity of the majority quantifier, as it requires evaluating the team as a whole rather than its small constituent parts.

Descriptive Complexity: Capturing the Counting Hierarchy

The primary contribution of the paper is the characterization of $D(M)$'s expressive power. The authors establish a two-way equivalence between $D(M)$ and second-order logic with majority quantifiers ($SO(Most)$):

  1. $D(M) \to SO(Most)$: Any sentence in $D(M)$ can be translated into an equivalent $SO(Most)$ sentence using majority quantifiers over relations.
  2. $SO(Most) \to D(M)$: Conversely, any $SO(Most)$ sentence can be expressed within $D(M)$.

Since $SO(Most)$ is known to capture the counting hierarchy (CH) over finite structures, this equivalence proves that $D(M)$ is a natural logical language for describing CH. This result bridges the gap between dependence-style logics and high-level counting complexity classes, providing a new tool for researchers in descriptive complexity.

Conclusion and Future Directions

By successfully integrating a majority quantifier into dependence logic, the authors have expanded the reach of team semantics into the counting hierarchy. While the behavior of sentences is now well-understood, the authors note that open formulas in $D(M)$ present significant challenges due to the loss of the free variable property and the lack of "flatness" or "locality" found in standard dependence logic.

Future research may explore the expressive power of fragments of $D(M)$, such as those excluding dependence atoms, or investigate whether other Lindström quantifiers can be adapted into the dependence logic framework to capture other complexity classes. This work opens a new chapter in the study of how collective quantification can describe the limits of computation.

Summary updated

BibTeX
@article{durand2015dependence,
  author = {Arnaud Durand and Johannes Ebbing and Juha Kontinen and Heribert Vollmer},
  title = {{Dependence logic with a majority quantifier}},
  journal = {J. Log. Lang. Inf.},
  year = {2015},
  url = {https://openreview.net/forum?id=DmN0d1BF2m},
}
Figure