On Quantified Propositional Logics and the Exponential Time Hierarchy

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

This paper, presented at GandALF 2016, explores the frontiers of propositional logic complexity. It provides a unified framework for understanding how different ways of quantifying variables—and the dependencies between them—map to the most challenging rungs of the exponential time hierarchy.

TL;DR

The authors introduce Alternating Dependency Quantified Boolean Formulae (ADQBF), a new logic that captures the complexity class AEXPTIME(poly). By bridging the gap between traditional quantified logics and "team semantics," they show that these seemingly different formalisms are actually two sides of the same coin, both capable of expressing problems at the highest levels of the exponential hierarchy.

What Problem Does This Paper Address?

In classical logic, Quantified Boolean Formulae (qBf) are used to determine if a formula is true for all or some truth values of its variables. This problem is famously PSPACE-complete. However, when we introduce "dependencies"—where an existential variable depends only on a specific subset of universal variables—we get Dependency Quantified Boolean Formulae (dqBf), which jumps in complexity to NEXPTIME.

The "jump" happens because dqBf implicitly allows us to quantify over Boolean functions (second-order logic) rather than just individual values. This paper seeks to:

  1. Create a logic (ADQBF) that generalizes this behavior to allow alternating universal and existential quantification of functions.
  2. Connect these findings to Team Semantics, a modern framework where truth is defined over sets of assignments ("teams") rather than single assignments, often used to model dependence and independence in data.

Methods

The researchers employ several theoretical techniques to map out this complexity landscape:

  • Logic Synthesis: They define ADQBF by adding a new quantifier ($U$) that represents the universal quantification of Skolem functions.
  • Complexity Mapping: Using Alternating Turing Machines (ATMs), they prove completeness results for various logic fragments. They specifically target the exponential hierarchy ($\Sigma^E_k, \Pi^E_k$) and the class AEXPTIME(poly) (problems decidable in exponential time with a polynomial number of alternations).
  • Translation Algorithms: The authors provide polynomial-time translations between Second-Order Propositional Logic ($SO_2$), ADQBF, and various team-based logics like Quantified Propositional Dependence Logic ($QPD$) and Inclusion Logic ($QPLInc$).
  • Recursive Quantifier Elimination: To prove upper bounds for team logics, they develop a recursive method to translate team-based quantifiers into standard second-order functional quantifiers.

Datasets

As a theoretical paper in mathematical logic and computational complexity, no empirical datasets were used. The "data" consists of formal logical languages and the "experiments" are mathematical proofs of their properties.

Key Insights and Ideas

  • Functions are the Key: The transition from PSPACE to the exponential hierarchy is fundamentally about moving from quantifying values to quantifying functions. ADQBF makes this explicit by allowing users to quantify over the "strategies" (Skolem functions) used in the logic.
  • The Power of the Tilde ($\sim$): In team semantics, the "not" operator ($\sim$) is non-classical. The authors show that nesting these negations corresponds directly to the number of alternations between existential and universal function quantifiers in the exponential hierarchy.
  • DQBF $\equiv$ Dependence Logic: A major "aha" moment is the formal proof that DQBF (a staple of formal verification) corresponds naturally to Quantified Propositional Dependence Logic. This links two previously separate research communities.
  • Inclusion Logic is "Easier": Surprisingly, while dependence logic hits NEXPTIME, Quantified Propositional Inclusion Logic ($QPLInc$) is "only" EXPTIME-complete. This highlights how different types of data dependencies (functional vs. inclusion) drastically change the computational cost of reasoning.

Key Results

  • ADQBF Completeness: The truth evaluation for the full ADQBF logic is proven to be AEXPTIME(poly)-complete.
  • Hierarchy Mapping: The authors identified specific fragments ($\Sigma_k$-ADQBF) that are complete for the $k$-th level of the exponential hierarchy ($\Sigma^E_k$).
  • Team Logic Bounds: They established that extending propositional team logic with "generalized dependence atoms" (a very broad class of dependencies) remains within AEXPTIME(poly).
  • Quantified Dependence Logic: Confirmed that $TRUE(QPD)$ is NEXPTIME-complete, providing a solid complexity foundation for researchers using team semantics.

Limitations and Future Work

  • Lax vs. Strict Semantics: The results in this paper primarily use "lax" team semantics. The authors note that "strict" semantics (where certain choices must be unique) might lead to different complexity results, which remains an open area for exploration.
  • Practical Fragments: While the paper defines the upper limits of these logics, identifying smaller, more "tractable" fragments that are still useful for software verification or database dependency analysis is a suggested next step.
  • Expressivity vs. Complexity: The paper focuses on how hard it is to solve these logics, but less on what specific properties are easier to write in one formalism versus another. Future work could look at the descriptive complexity of these languages.

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},
}

Loading related content...

Figure