The Model Checking Problem for Distributed Knowing How is Δ 2 p \Delta_{2}^{p} -Complete

Ziqi Wang, Ronald de Haan · 2026

Read The Model Checking Problem for Distributed Knowing How is Δ 2 p \Delta_{2}^{p} -Complete by Ziqi Wang, Ronald de Haan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-26709.txt.

Introduction

Ziqi Wang and Ronald de Haan pin down the exact difficulty of checking distributed knowing how. Knowing-how logics describe agents' abilities to reach goals by acting. In the distributed version, a group jointly knows how to achieve something. Model checking asks whether a given system and formula fit together. Planners in artificial intelligence rely on such checks.

Wang and de Haan prove the problem is complete for a complexity class built on polynomial time with many calls to an NP oracle. Their algorithm first computes where the inner formula holds. It then runs a fixed-point procedure for the group know-how operator, avoiding explicit construction of the group's huge action set. Completeness means the problem is exactly as hard as that class allows. No substantially faster general algorithm should be expected.

Catalog record

CREATORZiqi Wang, Ronald de Haan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.26709

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Model Checking Problem for Distributed Knowing How is Δ 2 p \Delta_{2}^{p} -Complete Ziqi Wang, Ronald de Haan Abstract We investigate the complexity of the model checking problem for distributed knowing how. We show that the problem is Δ 2 p \Delta_{2}^{p} -complete. 1 Introduction Knowing-how logics study agents’ abilities to achieve goals by suitable actions. This makes them particularly relevant to artificial intelligence, especially to planning, where the main question is whether a desired objective can be guaranteed by some plan. The logic of distributed knowing how [ 3 ] generalizes two existing frameworks of knowing how. The planning-based framework, initiated in [ 6 , 7 ] , treats knowing how as the existence of a multi-step plan that can be executed, always terminates, and guarantees the goal, while the coalition-based framework, initiated in [ 4 , 5 ] , treats group know-how as the existence of a one-step joint action that ensures the goal. In this work, we prove the model checking problem for the logic of distributed knowing how is {\Delta_{2}^{p}} -complete. More precisely, we introduce a model checking algorithm in \Delta_{2}^{p} , the class of problems decidable in polynomial time with polynomially many calls to an \mathsf{NP} oracle. The main difficulty lies in the Kh_{G} -modality. Instead of explicitly constructing the distributed action set A_{G}^{*} , our procedure first computes the satisfaction set of the inner formula and then runs a fixpoint algorithm over the quotient set S/{\sim_{G}} . We show that the problem is {\Delta_{2}^{p}} -hard, by a reduction from SNSAT [ 2 ] . Together both results, we obtain a tight bound for this problem. 2 Preliminaries Let \mathcal{P} be a denumerable set of proposition symbols and let I be a finite set of agents. The language \mathsf{DKH} is defined by the grammar \varphi::=\top\mid p\mid\neg\varphi\mid(\varphi\wedge\varphi)\mid K_{G}\varphi\mid Kh_{G}\varphi where p\in\mathcal{P} and G\subseteq I . A model \mathcal{M} is a tuple \left\langle S,\{\sim_{i}\}_{i\in I},\{A_{G}\}_{G\subseteq I},\left\{\xrightarrow{a}\mid a\in\bigcup_{G\subseteq I}A_{G}\right\},V\right\rangle, where S is a set of states; \sim_{i} is an equivalence relation on S for each i\in I ; A_{G} is a set of atomic group actions for each G\subseteq I such that: G\subsetneq H implies A_{G}\cap A_{H}=\emptyset ; A_{\emptyset}=\emptyset ; \xrightarrow{a} is a binary relation on S for each a\in\bigcup_{G\subseteq I}A_{G} , called the transition relation of a ; V:\mathcal{P}\to 2^{S} is a valuation function. The family \{A_{G}\}_{G\subseteq I} is part of the model, so the input size depends on how this family is represented. We assume an explicit representation in which only non-empty A_{G} ’s are listed. For each group G\subseteq I , the distributed indistinguishability relation is defined by \sim_{G}:=\bigcap_{i\in G}\sim_{i} . We write [s]_{G} for the \sim_{G} -equivalence class of s , and [S]_{G} for the corresponding quotient set. We also write A_{G}^{+}:=\bigcup_{H\subseteq G}A_{H} for the set of atomic actions available to subgroups of G . Fix an enumeration I=\{i_{1},\ldots,i_{n}\} . For every nonempty group G=\{i_{n_{1}},\ldots,i_{n_{k}}\} , let \min G:=\min\{n_{1},\ldots,n_{k}\} . For mutually disjoint nonempty groups G and H , define G\prec H iff \min G<\min H . For each group G , its distributed action set is defined as A_{G}^{*}:=A_{G}^{+}\cup\{\langle d_{1},\ldots,d_{n}\rangle\in A_{G_{1}}^{*}\times\cdots\times A_{G_{n}}^{*}\mid\{G_{1},\ldots,G_{n}\} is a non-trivial partial partition of G and G_{1}\prec\cdots\prec G_{n}\} . Here, a non-trivial partial partition of a set X is a partition of a not necessarily proper subset of X that is not a singleton set. It follows that A_{\emptyset}^{*}=\emptyset and A_{\{i\}}^{*}=A_{\{i\}} for each i\in I . For each distributed action d=\langle d_{1},\dots,d_{n}\rangle\in A_{I}^{*} , the distributed transition relation is defined by \xrightarrow{d}:=\bigcap_{1\leq k\leq n}\xrightarrow{d_{k}} . A distributed action d\in A_{I}^{*} is executable on a nonempty set X\subseteq S if, for every s\in X , there is a state t\in S such that s\xrightarrow{d}t . A strategy for a group G is a partial function \sigma_{G}:[S]_{G}\to A_{G}^{*} such that, whenever [s]_{G}\in\mathrm{dom}(\sigma_{G}) , the action \sigma_{G}([s]_{G}) is executable on [s]_{G} . In particular, the empty function is a strategy. A possible execution of \sigma_{G} starting from [s]_{G} is a nonempty finite or infinite sequence [s_{1}]_{G}[s_{2}]_{G}\cdots with [s_{1}]_{G}=[s]_{G} such that, for every j\geq 1 for which [s_{j+1}]_{G} occurs in the sequence, [s_{j}]_{G}\xrightarrow{\sigma_{G}([s_{j}]_{G})}[s_{j+1}]_{G} . A possible execution is complete if it is infinite, or if it is finite and its last class does not belong to \mathrm{dom}(\sigma_{G}) . If a finite possible execution is of the form [s_{1}]_{G}\cdots[s_{n}]_{G} , then [s_{n}]_{G} is its leaf-node and every [s_{j}]_{G} , with 1\leq j<n , is an inner-node. If it is infinite, then all its nodes are inner-nodes. For all complete executions starting from [s]_{G} , we denote their leaf-nodes and inner-nodes by \mathrm{CELeaf}(\sigma_{G},s) and \mathrm{CEInner}(\sigma_{G},s) , respectively. The semantics is defined as follows. Given a model \mathcal{M} , a state s\in S , and a formula \varphi\in\mathsf{DKH} , we omit the Boolean cases. \mathcal{M},s\models K_{G}\varphi iff \mathcal{M},s^{\prime}\models\varphi for all s^{\prime}\in[s]_{G} \mathcal{M},s\models Kh_{G}\varphi iff there is a strategy \sigma_{G} of G such that: (1) [t]_{G}\subseteq\llbracket\varphi\rrbracket^{\mathcal{M}} for all [t]_{G}\in\mathrm{CELeaf}(\sigma_{G},s) , and (2) all complete executions of \sigma_{G} starting from [s]_{G} are finite. 3 The Upper Bound The model checking procedure \textsc{CheckerDKH}(\mathcal{M},s,\varphi) (Algorithm 1 ) decides whether the input state s satisfies the formula \varphi on a finite model \mathcal{M} . It is defined via an evaluation procedure \textsc{Eval}(\mathcal{M},\varphi) , which computes the satisfaction set of \varphi bottom-up, following the structure of formulas. Thus, \textsc{CheckerDKH}(\mathcal{M},s,\varphi) returns true iff s\in\textsc{Eval}(\mathcal{M},\varphi) . The Boolean cases and the K -modality are treated as usual. The non-trivial case is the evaluation of a Kh_{G} -formula. For such a formula Kh_{G}\psi , Algorithm 3 first computes \textsc{Eval}(\mathcal{M},\psi) and then performs a monotone fixpoint construction over the quotient set S/{\sim_{G}} . Starting from the \sim_{G} -equivalence classes already contained in the set, the algorithm repeatedly adds a class E whenever there exists a distributed action that is executable on E and whose possible successor classes are all contained in the current approximation. The existence of such a witness is checked by an \mathsf{NP} oracle. Algorithm 4 gives the corresponding nondeterministic procedure. Note that an actual distributed action can be nested, but that it can always be flattened via Proposition 14 in [ 3 ] . In particular, IsValidDAction (Algorithm 5 ) checks whether the guessed tuple can be viewed as an element of A_{G}^{*} , by assigning each action to a suitable subgroup and verifying that the chosen subgroups are defined and pairwise disjoint. Once the fixpoint is reached, EvalKh returns the union of all states belonging to the winning equivalence classes. Procedure CheckerDKH (\mathcal{M},s,\varphi) : return s\in\textsc{Eval}(\mathcal{M},\varphi) Procedure Eval (\mathcal{M},\varphi) : switch \varphi do case \varphi\equiv\top do return S ; case \varphi\equiv p do return V(p) ; case \varphi\equiv\neg\psi do return S\setminus\textsc{Eval}(\mathcal{M},\psi) ; case \varphi\equiv\psi\wedge\chi do return \textsc{Eval}(\mathcal{M},\psi)\cap\textsc{Eval}(\mathcal{M},\chi) ; case \varphi\equiv K_{G}\psi do return \textsc{EvalK}(\mathcal{M},G,\psi) ; case \varphi\equiv Kh_{G}\psi do return \textsc{EvalKh}(\mathcal{M},G,\psi) ; Algorithm 1 Model Checking Procedure Procedure EvalK (\mathcal{M},G,\varphi) : X\leftarrow\textsc{Eval}(\mathcal{M},\varphi) ; \sim_{G}\leftarrow\bigcap_{i\in G}\sim_{i} ; \mathcal{C}_{G}\leftarrow S/\sim_{G} ; L\leftarrow\emptyset ; foreach E\in\mathcal{C}_{G} do if E\subseteq X then L\leftarrow L\cup E ; return L ; Algorithm 2 Evaluation of K-modality Function EvalKh (\mathcal{M},G,\varphi) : X\leftarrow\textsc{Eval}(\mathcal{M},\varphi) ; \sim_{G}\leftarrow\bigcap_{i\in G}\sim_{i} ; \mathcal{C}_{G}\leftarrow S/\sim_{G} ; W\leftarrow\{E\in\mathcal{C}_{G}\mid E\subseteq X\} ; changed\leftarrow\textnormal{True} ; while changed do changed\leftarrow\textnormal{False} ; foreach E\in\mathcal{C}_{G}\setminus W do if \textsc{HasWinDistribution}(\mathcal{M},G,E,W) then W\leftarrow W\cup\{E\} ; changed\leftarrow\textnormal{True} ; return \bigcup_{E\in W}E ; Algorithm 3

Read the complete text