On Quantified Propositional Logics and the Exponential Time Hierarchy

Miika Hannula, Juha Kontinen, Martin Lück, Jonni Virtema

Abstract

This paper explores the computational complexity of propositional logics involving dependencies and alternating quantifiers. By introducing Alternating Dependency Quantified Boolean Formulae (ADQBF), the research establishes a unified framework that maps various logical formalisms to the exponential time hierarchy. The study bridges the gap between traditional quantified logics and team semantics, proving that the transition from quantifying values to quantifying functions is the fundamental driver of complexity jumps from PSPACE to AEXPTIME(poly).

Introduction

In the landscape of computational complexity, Quantified Boolean Formulae (QBF) serve as the standard for PSPACE-completeness. However, when the independence of variables is introduced—where an existential variable depends only on a specific subset of universal variables—the complexity shifts dramatically. This phenomenon is observed in Dependency Quantified Boolean Formulae (DQBF), which is NEXPTIME-complete.

Presented at GandALF 2016, this research investigates the frontiers of this complexity by introducing a new logic: Alternating Dependency Quantified Boolean Formulae (ADQBF). This framework allows for the alternating universal and existential quantification of functions, providing a tool to characterize the highest rungs of the exponential time hierarchy.

The Shift to Function Quantification

The primary reason for the complexity jump from PSPACE to the exponential hierarchy is the implicit move from first-order to second-order logic. While standard QBF quantifies over individual truth values, DQBF and ADQBF quantify over Boolean functions (or Skolem functions).

ADQBF makes this explicit by introducing a new quantifier ($U$) representing the universal quantification of functions. This allows the logic to model complex "strategies" in a game-theoretic sense, where players choose functions rather than single assignments. The authors demonstrate that the number of alternations between these functional quantifiers corresponds directly to specific levels within the exponential hierarchy ($\Sigma^E_k, \Pi^E_k$).

Bridging to Team Semantics

A significant contribution of this work is the formal connection established between ADQBF and Team Semantics. In team semantics, truth is defined over sets of assignments ("teams") rather than single assignments. This framework is increasingly used to model dependence and independence in database theory and software verification.

Through polynomial-time translations, the authors show that:

  • Quantified Propositional Dependence Logic (QPD) is equivalent to DQBF, confirming its NEXPTIME-completeness.
  • Quantified Propositional Inclusion Logic (QPLInc) is EXPTIME-complete, revealing that inclusion dependencies are computationally "easier" than functional dependencies.
  • The non-classical negation operator ($\sim$) in team semantics acts as a mechanism for quantifier alternation, mapping nested negations to the alternating layers of the exponential hierarchy.

Complexity Mapping and Results

The researchers utilized Alternating Turing Machines (ATMs) and recursive quantifier elimination to map the complexity landscape. Their key findings include:

  1. ADQBF Completeness: The truth evaluation for the full ADQBF logic is AEXPTIME(poly)-complete, meaning it covers problems decidable in exponential time with a polynomial number of alternations.
  2. Hierarchy Fragments: Specific fragments, denoted as $\Sigma_k$-ADQBF, were proven to be complete for the $k$-th level of the exponential hierarchy ($\Sigma^E_k$).
  3. Generalized Dependencies: The study established that extending propositional team logic with a broad class of "generalized dependence atoms" remains within the bounds of AEXPTIME(poly).

Conclusion and Future Directions

By unifying ADQBF, second-order propositional logic ($SO_2$), and team-based logics, this paper provides a definitive map of the exponential time hierarchy in the context of propositional reasoning. The results highlight that the power of a logic is fundamentally tied to its ability to quantify over functions and the nature of the dependencies it allows.

Future research directions include exploring "strict" versus "lax" semantics, which may yield different complexity results for certain fragments. Additionally, identifying more tractable fragments of these high-complexity logics could lead to practical applications in automated reasoning and the analysis of complex data dependencies.

Summary updated

BibTeX
@inproceedings{hannula2016quantified,
  author = {Miika Hannula and Juha Kontinen and Martin Lück and Jonni Virtema},
  title = {{On Quantified Propositional Logics and the Exponential Time Hierarchy}},
  booktitle = {GandALF},
  year = {2016},
  url = {https://openreview.net/forum?id=eHWVKvSsKKRG},
}
Figure