The Complexity of Model Checking Knowledge and Time

Laura Bozzelli, Bastien Maubert, Aniello MuranoIJCAI 2019 · DOI

TL;DR

This paper precisely characterizes the complexity of model checking for epistemic temporal logics with perfect recall, a problem that has remained open for two decades. The authors establish that for formulas with a maximum of $k$ alternations between knowledge operators, the model checking problem is $(k-1)$-EXPSPACE-complete for both synchronous and asynchronous perfect recall semantics. This result tightens existing upper bounds and provides matching lower bounds, settling the complexity for a significant family of multi-agent system verification problems.

What Problem Does This Paper Address?

Reasoning about multi-agent systems often requires understanding not only their behavior over time but also what individual agents know about the system and each other's knowledge. Epistemic temporal logics, which combine temporal logic (like LTL, CTL, CTL) with epistemic logic (knowledge operators), provide a formal framework for this. A crucial task in verifying such systems is model checking*: determining if a given system model satisfies a property expressed in an epistemic temporal logic.

While the satisfiability (whether any system satisfies a formula) and axiomatization of these logics are well-understood, the model checking problem for agents with perfect recall (meaning agents remember all past observations) has been a persistent challenge. For formulas with a high degree of nesting of knowledge operators (measured by "alternation depth"), the problem was known to be non-elementary, meaning its complexity grows faster than any fixed number of exponentials. However, for a fixed maximum alternation depth $k$, the precise complexity remained an open question for twenty years. This paper aims to close this gap by providing tight complexity bounds for this important class of problems.

Methods

The paper employs a combination of established and novel techniques:

  • Powerset Construction: A key technique is the construction of a "powerset model." This new model's states encode not just the current state of the system but also the information sets (what each agent considers possible) for all agents. This construction allows for evaluating certain types of formulas (specifically, those with alternation depth one) positionally, meaning their truth can be determined by examining individual states in the powerset model rather than entire paths. This is crucial for reducing the complexity.
  • On-the-fly Automata Construction: For formulas with alternation depth one, the authors leverage on-the-fly construction of Büchi automata for LTL, combined with the powerset model. This avoids explicitly building the potentially huge powerset model and automata, keeping the complexity manageable.
  • Alternation Reduction: The core of the paper's contribution lies in a method to reduce the alternation depth of formulas. By using the powerset construction and carefully marking states with new atomic propositions, they show how to transform a formula of alternation depth $k+1$ into an equivalent formula of alternation depth $k$ on a larger, but still manageable, model. This inductive step is key to establishing the upper bounds.
  • Domino Tiling Reduction: To establish the lower bounds (proving that the problem is at least as hard as indicated), the authors use a standard technique in complexity theory: reduction from a known hard problem. They reduce a $k$-EXPSPACE-complete domino tiling problem to the model checking problem for epistemic temporal logics. This demonstrates that the proposed logics are indeed as complex as claimed.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity and does not evaluate its methods on specific datasets.

Key Insights and Ideas

  • Tight Complexity for Fixed Alternation Depth: The most significant insight is the precise characterization of model checking complexity as $(k-1)$-EXPSPACE-complete for formulas with alternation depth at most $k$. This resolves a long-standing open problem and provides a clear understanding of how complexity scales with the nesting of knowledge operators.
  • Unified Complexity for Synchronous and Asynchronous Semantics: The paper shows that the complexity is the same for both synchronous (SPR) and asynchronous (APR) perfect recall semantics. This is notable because these semantics can differ significantly in other contexts.
  • The Power of Powerset Construction for Epistemic Temporal Logics: The paper demonstrates the effectiveness of the powerset construction, a technique previously used for other epistemic logic problems, in tackling the model checking of complex epistemic temporal logics. It allows for a more structured approach to evaluating formulas.
  • Inductive Alternation Reduction: The method for reducing alternation depth by transforming formulas and models is a powerful technique. It allows for a systematic way to handle increasingly complex formulas by breaking them down into simpler, manageable steps.

Key Results

  • Theorem 1: For every $k \in \mathbb{N}$, the model-checking problem for LTLK$_{k+1}$, CTLK$_{k+1}$, and CTLK$^*_{k+1}$ is $(k-1)$-EXPSPACE-complete, for both SPR and APR semantics. This means that for formulas with at most $k$ alternations of knowledge operators, the problem is solvable in $(k-1)$-EXPSPACE, and no faster algorithm exists.
  • Table 1: Summarizes known and new results, showing that the paper's findings provide tight bounds for several epistemic temporal logic fragments.

Limitations and Future Work

  • "No Learning" Assumption: The paper notes that their work, like much of the existing literature, assumes agents have "perfect recall" but does not explicitly address the "no learning" assumption (where agents cannot update their knowledge based on new observations). They suggest that this is an area for future investigation, though they suspect it might reduce to known bounded memory cases.
  • Bounded Memory: The paper focuses on perfect recall and mentions that the situation for agents with bounded memory is already well-understood. However, they point out a specific gap for synchronous bounded memory for CTLK, which they plan to investigate.
  • Succinct Representations: The paper's complexity results are for models given by explicit state descriptions. The authors briefly mention that complexity for succinct representations of multi-agent systems is a more recent area of study, implying that extending their results to such representations would be a valuable future direction.

Summary updated

BibTeX
@inproceedings{bozzelli2019complexity,
  author = {Laura Bozzelli and Bastien Maubert and Aniello Murano},
  title = {{The Complexity of Model Checking Knowledge and Time}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/221},
}
Figure