The Model Checking Problem for Distributed Knowing How is $Δ^p_2$-Complete

We investigate the complexity of the model checking problem for distributed knowing how. We show that the problem is $Δ^p_2$-complete.

Machine Learning and Algorithms Logic, Reasoning, and Knowledge Quantum Computing Algorithms and Architecture

Paper

Similar papers

Distributed Knowing HowBin Liu, Yanjing Wang2025 · Electronic Proceedings in Theoretical Computer Science In Library

Complete Distributed Consequence Finding with Message PassingKatsumi Inoue, Gauvain Bourgne, Takayuki Okamoto2018 · International Conference on Agents and Artificial Intelligence · 3 citations In Library

Model Checking Probabilistic Knowledge: A PSPACE CaseXiaowei Huang, M. Kwiatkowska2016 · AAAI Conference on Artificial Intelligence · 3 citations In Library

Model-Checking for Ability-Based Logics with Constrained PlansStéphane Demri, Raul Fervari2023 · Proceedings of the AAAI Conference on Artificial Intelligence · 7 citations In Library

How Easy it is to Know How: An Upper Bound for the Satisfiability ProblemC. Areces, Valentin Cassano, Pablo F. Castro et al.2023 · European Conference on Logics in Artificial Intelligence · 3 citations In Library

The Complexity of Model Checking Knowledge and TimeL. Bozzelli, Bastien Maubert, A. Murano2019 · International Joint Conference on Artificial Intelligence · 5 citations In Library

On the Complexity of Model Checking Knowledge and TimeLaura Bozzelli, Bastien Maubert, Aniello Murano2023 · ACM Transactions on Computational Logic In Library

Determining Existence of Logical Obstructions to the Distributed Task SolvabilitySou Hoshino2022 · arXiv (Cornell University) In Library

A Meta-Theorem for Distributed CertificationPierre Fraigniaud, Pedro Montealegre, Ivan Rapaport et al.2021 · arXiv (Cornell University) In Library

Visual Model Checking Distributed SystemYiyang Jia, Xinfeng Shu2022 · International Conference on Artificial Intelligence and Pattern Recognition · 0 citations In Library

Source of record

OpenAlex

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal