Limited-knowledge propositional announcement synthesis under Dalal revision: tight PH bounds, parameterized tractability and kernelization

We study announcement synthesis under incomplete initial beliefs for multiple agents, instantiated with Dalal’s distance-based AGM revision. We introduce and formalize two semantics for the limited-knowledge propositional announcement problem: an optimistic variant (PAP∃_*D), which requires success under some admissible completion per agent, and a robust variant (PAP∀_*D), which requires success under all admissible completions. This distinction captures a fundamental trade-off in multi-agent coordination: optimism assumes favourable conditions, while robustness hedges against all contingencies. Our first contribution is a tight complexity classification revealing a precise quantifier-complexity correspondence: PAP∃_*D is ₂P-complete, while PAP∀_*D is ₃P-complete under extensional completion sets. The one-level gap confirms that robustness costs exactly one quantifier alternation in the polynomial hierarchy. The upper bounds follow from a small-announcement normal form—showing that effective coordination messages have bounded complexity—and NP-decidability of the distance-threshold predicate Dist≤. Second, we develop a parameterized tractability landscape that identifies when and why announcement synthesis becomes feasible despite worst-case intractability. We establish FPT algorithms parameterized by vocabulary size k and announcement width t; FPT results for bounded completion-set sizes; and FPT in structural parameters (treewidth, backdoor size) via dynamic programming. The bounded-change variant is FPT in the ₁-budget D=∑ ᵢ dᵢ. Five polynomial-time kernelization rules enable effective preprocessing. Conditional lower bounds under ETH and SETH identify unavoidable exponential dependencies. Finally, we discuss how alternative distance aggregations (average, maximum, Hausdorff) affect computational complexity, showing that our minimum-based framework provides the foundational ‘base case’ upon which more complex variants can build.