How Hard to Tell? Complexity of Belief Manipulation Through Propositional Announcements

1 Introduction

The beliefs of a group of agents can be manipulated through announcements. For instance, consider politicians that should announce the COVID-19 vaccine campaign organization. In order to prevent the call center to break down, they have to tailor a suitable public announcement to be sure that only people that need the vaccine will call. Such announcement can be difficult to conceive and has to take into account agents with different beliefs and that may have different inconsistent goals, depending on the population backgrounds.

Public announcements have previously been studied in modal logics [Plaza, 2007; Balbiani et al., 2007; Ditmarsch et al., 2008]. However, our focus here is strictly on propositional announcements in the context of formal belief revision operators. The problem is still significant in this context, as there are many natural applications involving announcements that do not involve nested beliefs.

We assume that each agent has an initial belief state as well as a formal mechanism for incorporating new information. When an announcement is made, each agent's beliefs change accordingly. Now suppose that, for each agent i, we have an epistemic goal ψi; that is, we would like the agent i to believe that ψi is true. The propositional announcement problem consists in finding a single formula φ that will ensure that each agent believes their epistemic goal following the announcement of φ. In this paper, we are concerned with the computational complexity of the propositional announcement problem.

In this paper, we present a complete analysis of the computational complexity of the propositional announcement problem (PAP). Specifically, we make the following contributions:

1. We show that PAP as formulated in [Hunter et al., 2017] is Σp2 -hard, thus closing a problem that was left open.
2. We characterize the existence of announcements, both in the general case and for all AGM-style operators.
3. We show that, for all AGM-style operators with complexity in P NP , which include Dalal's, Σp2 is an upper complexity bound.
4. For popular change operators like Ginsberg's [1986] we show that PAP is EXPTIME-complete in general.

In addition to the complexity results, we demonstrate how to construct solutions to announcement finding problems.

Outline. The paper is organized as follows. In Section 2, we recall the basics about belief revision. In Section 3, we recall the propositional announcement problem and provide characterization results. In Section 4, we give the upper bound and lower bound complexity results. Finally, in Section 5 we firt present related work and then we conclude.

2 Preliminaries

2.1 AGMBelief Revision

We assume a finite set P of propositional variables, called a vocabulary. A belief set over P is a deductively closed set K of propositional formulas, also called a knowledge base; we may view K as a single formula given by ∧{φ ∈ K}. The notions of satisfaction and entailment are as usual. Interpretations µ : P → {0, 1} are also viewed as sets of variables assigned true, i.e., {p ∈ P | µ(p) = 1}. We write mod(φ) resp. mod(K) to denote the set of interpretations where φ resp. K is true (i.e., its models).

An AGM revision operator ∗ assigns each belief set K and formula φ a belief set K ∗ φ that satisfies the AGM postulates [Alchourr´on et al., 1985]. Semantically, AGM revision operators have been characterized in terms of model selection as follows [Katsuno and Mendelzon, 1992]. For every K and φ,

i.e., the models of the revision are the minimal (closest) models of φ in some total preorder µ ⪯K µ′ of the interpretations that fulfill further conditions, viz. (i) µ |= K implies for every µ′ that µ ⪯ µ′ and if µ′ ⪯K µ then µ′ |= K and (ii) K ≡ K′ implies ⪯K =⪯K′ . As usual, µ ≺K µ′ denotes the strict version of µ ⪯K µ′ : it means µ ⪯K µ′ and not µ′ ⪯K µ. On the other hand, each such total preorder ⪯K induces an AGM revision operator.

A canonical example is the Dalal operator [Dalal, 1988], denoted by ∗d. Here the ordering µ ⪯DK µ′ is based on the Hamming distance dH(ν, µ) between interpretations ν, µ, which is the cardinality of the set diff (ν, µ) = {p ∈ P | ν |= p ⇔ µ ̸|= p} of variables with different truth values in ν and µ. Then µ ⪯DK µ′ iff dH(µ,K) ≤ dH(µ′ ,K), where dH(µ,K) = minν|=K dH(µ, ν) is this least Hamming distance between µ and any model ν of K. Then, mod(K ∗d φ) are those models µ of φ such that dH(µ, K) is minimal.

2.2 Beyond AGMRevision

Besides AGM revision, many further change operators have been proposed in the literature which do not satisfy the AGM postulates, even in a finite setting cf. [Eiter and Gottlob, 1992; Nebel, 1998]. A prominent such example is Ginsberg's [1986] operator ∗G, which is defined for knowledge bases K and formulas φ by

where W(K, φ) are the models comprising the maximal subsets K′ ⊆ K that are satisfiable with φ. Semantically, K ∗G φ is regarded as the disjunction K1 ∨ · · · ∨ Kn of all Ki in K ∗G φ = {K1, . . . ,Kn}. Notably, this operator is known as the "flock" approach in databases [Fagin et al., 1986], and it underlies in varieties consistent query answering from data and knowledge bases [Bertossi, 2019; Bienvenu and Bourgaux, 2016].

It is possible to capture ∗G by model selection as in (1), if we view ⪯ as a preference relation (and disregard (ii)). For each model µ and knowledge base K let Kµ = {α ∈ K | µ |= α} be the formulas in K that are satisfied by µ.

Proposition 1. For every knowledge base K and formula φ,

That is, we can compare models µ and µ′ as follows: µ ⪯GK µ′ iff Kµ ⊇ Kµ′ . This is in fact a partial ordering, and it leads to the following result:

Proposition 2. For any K and formula φ, mod(K ∗G φ) = min⪯GK (mod (φ)).

This is just one example. In a similar manner, we can consider generic preference-based operators, i.e., that can be defined by minimal model selection (1) in terms of a preorder ⪯K that depends on K (possibly embracing conditions such as variable preference, formula protection, etc.).

3 The Propositional Announcement Problem 3.1 The Basic Problem

We define the announcement problem more formally. Given n agents and n AGM belief revision operators ∗i as input; we are looking for a consistent formula φ such that

where Ki and ψi represent the belief set and the goal of the agent i, respectively. If ∧i ψi is consistent, simply announce it! So the problem is only of interest if ∧i ψi is inconsistent.

Example 1. Consider a pair of "herding" agents R1 and R2 that must collaborate to herd a flock of sheep. Each agent acts independently, influenced by a single controller making announcements. Assume the vocabulary is {corner, retrieve}. Informally, a herder will believe corner if the sheep must be cornered so they can not move. A herder will believe retrieve if there is a stray sheep that must be retrieved.

Let the initial beliefs of R1 and R2 be as follows:

Suppose the controller sees one sheep has left the flock. Is there a formula that can be broadcast to immediately get R1 to retrieve the sheep while R2 corners the rest of the animals? In other words, is there a formula φ such that:

{¬corner ∨ ¬retrieve} ∗ φ |= ¬retrieve ∧ corner

If we assume both agents use the Dalal revision operator, the answer is yes; we can set φ = corner. This instance of the announcement problem has a solution.

The announcement problem was previously considered in [Hunter et al., 2017], where the following basic results are shown.

Proposition 3. For all n > 1, there are instances of (3) with no solution.

Proposition 4. Let P be a vocabulary and let the number of agents n satisfy n < 2|P| . Then there is an instance of (3) over P with inconsistent goals that has a solution.

Hence, there are cases with no solution and there are cases with a solution; the question is how hard it is to tell which is the case. We are therefore concerned with the complexity of the following decision problem.

The Propositional Announcement Problem (PAP(∗i ))

Input: a list K1, . . . ,Kn of formulas (initial beliefs).

a list ψ1, . . . , ψn of formulas (goals).

Ouput: yes, if some φ satisfying (3) exists, no, otherwise.

Note that an instance of the problem is written as PAP(∗i) to emphasize that it depends on given revision operators ∗i.

In [Hunter et al., 2017], it is proved that this decision problem is in Σp2 = NP NP if we restrict attention to the Dalal operator. The hardness of PAP is left open in that paper.

3.2 Characterisation

Recall that all AGM revision operators can be characterised by taking minimal models in some preference ordering. In fact, when we can obtain the revision models as the minimal models of a preorder ⪯ (not necessarily a total one, i.e., models may be incomparable; in short by model preference), then we can characterize solutions φ to a propositional announcement problem (PAP) P = (Ki, ψi)ni=1 as follows.

Proposition 5. Let φ be consistent and let P be a PAP with model-preference definable operators ∗i, 1 ≤ i ≤ n. Then a formula φ is a solution to P iff for all i = 1, . . . , n and µ, if µ |= φ ∧¬ψi then some µ′ ≺Ki µ exists s.t. µ′ |= φ∧ψi.

The characterisation in Proposition 5 says that models µ violating the query ψi must be eliminated by models µ′ which do satisfy the query and are closer to the knowledge base Ki.

In fact, without loss of generality, one can limit the solutions to fulfill mod(φ) ⊆ ⋃i mod(ψi) i.e., replace φ by φ ∧ ∨i ψi, because every model that does not satisfy any of the ψi must be eliminated under revision.

Proposition 6. If φ is a solution to a model-preference definable PAP P , then φ ∧ ∨i ψi is also a solution of P .

In general, there can be multiple solutions φ, of course; however, there are interesting observations.

Proposition 7. Every PAP P with model-preference definable operators ∗i has a unique weakest solution φ∗ , i.e., for every solution φ, it holds that φ |= φ∗ .

The reason for this is simple: if φ1 and φ2 are solutions, then also φ1 ∨ φ2 is a solution; in terms of models, the union of the set of models of solutions is also a solution.

Total Preorders

Smaller solutions with few models might exist, as in the case of Dalal's operator. There, at most n models are needed to find a solution. This can in fact be generalized to operators that are definable by total prorders ⪯Ki , i.e., either µ ⪯K µ′ or µ′ ⪯K µ holds for all models µ and µ′ .

Proposition 8. Let P be a PAP with model-preference definable operators ∗i where all preorders ⪯Ki are total. Then the following are equivalent:

1. P has some solution,
2. There is (µ1, . . . , µn) with µi |= ψi and for all j, either µj |= ψi or µi ≺Ki µj.
3. {µ1, . . . , µn} as in point 2 is a solution of P.

Proof. (1⇒2) Let φ be a solution. Pick µi in min⪯Ki (mod(φ)) which is non-empty because φ is consistent. As φ is a solution, µi |= ψi. Suppose that µj ̸|= ψi. We also have µj |= φ. By Proposition 5, there exists µ′ such that µ′ |= φ, µ′ |= ψi and µ′ ≺Ki µj. As µi is in min⪯Ki (mod(φ)), and as µi and µ′ are ⪯Ki -comparable, we must have µi ⪯Ki µ′ . By transitivity, we have µi ≺Ki µj.

(2⇒3). Let us show that min⪯Ki ({µ1, . . . , µn}) |= ψi. Take a ⪯Ki -minimal µj. As we do not have µi ≺Ki µj, we must have µj |= ψi.

4 Computational Complexity

It was shown in [Hunter et al., 2017] that for Dalal's operator, the PAP(∗d) problem is in Σp2 , by exhibiting a nondeterministic guess and check algorithm based on an ad-hoc instance of Proposition 8. However, the authors left the issue open whether this bound can be improved. We show that this bound is tight, proving Σp2 -hardness by a nontrivial construction. Furthermore, we establish that the PAP problem is Σp2 - complete in general for partial ordering definable operators ∗i with complexity in P NP , while we show that it is EXPTIMEcomplete for model-preference operators ∗i in general. In particular, EXPTIME-hardness is shown for Ginsberg's operator. Hence, there is a considerable complexity gap between operators that are relevant in practice.

4.1 Upper Bounds

Total Preorders

For operators ∗ definable by total preorders, Proposition 8 implies that we can use a guess and check algorithm to decide the existence of a solution.

Theorem 1. Let ∗i be operators that are definable by total preorders ⪯Ki . If checking µ ⪯Ki µ′ is feasible in complexity C, then PAP(∗i) is decidable in NPC .

Proof. Consider the following non-deterministic algorithm:

for i := 1 to n do (∃) choose µi in mod(ψi) for i, j ∈ {1, . . . , n} do if µi ̸|= ψj then Check that µj ⪯Ki µi ∧ µi ̸⪯Ki µj

The correctness follows by Proposition 8.

For all belief revision operators that satisfy the AGM postulates, it is by Proposition 8 a matter of the complexity of model comparison which may dominate the overall complexity. But in any case, we have a small result for the revision!

In particular for complexity C = P NP , we obtain from Theorem 1 membership in NP P NP = NP NP . Applied to Dalal's operator, we thus obtain the following result.

Corollary 1 (cf. [Hunter et al., 2017]). PAP(∗d) is in ΣP2 .

Proof. Given an interpretation µ and an integer k, deciding dH(µ, ν) ≤ k is in NP. Thus, computing dH(µ,K) is feasible in polynomial time with an NP oracle, and so is deciding µ ⪯DK µ′ ; Theorem 1 implies membership in Σp2 .

For knowledge bases K in special form, the NP-oracle may be eliminated so that lower complexity results. For example, we have the following result.

Proposition 9. PAP(∗d) is in NP, if each Ki is rewritable into a DNF formula in polynomial time.

Indeed, for a DNF α = D1 ∨ · · · ∨ Dn, determining the smallest distance dH(µ, µ′ ) of a model µ to any model µ′ of α is feasible in polynomial time.

General Case

Theorem 2. Given model-preference definable operators ∗i such that µ′ ⪯Ki µ is decidable in exponential time, PAP(∗i) is in EXPTIME.

Sketch of proof. Consider the following alternating algorithm in which the existential player builds φ on the fly, and that checks the assumption of Proposition 5:

Note that at stage s = 2|P | , a loop must have been entered, which allows for acceptance. As APSPACE = EXPTIME [Chandra and Stockmeyer, 1976], the check µ′ ⪯Kj µ (i.e., µ′ ⪯Kj µ and µ ̸⪯Kj µ′ ) is feasible with alternations in polynomial space. Overall, the algorithm runs with alternations in polynomial space, which shows EXPTIME-membership.

In the alternating PSPACE algorithm above the universal branching is only about polynomially many values. It may be tempting to believe that this branching can be eliminated and simulated deterministically. However, the recursion depth is not necessarily polynomially bounded, so this may end up in exponential space consumption. Notably, even if each relation ≺Ki is acyclic, their interaction may create a cycle.

Example 2. Let K1 ={¬evidence ∨guilty} be the prosecutor's and K2 = {¬guilty∨¬evidence} be the accused's KB in a trial. The judge may announce proper account of evidence (φ = evidence) to achieve ψ1 = guilty and ψ2 =¬guilty under Dalal's operator. The models µ1 ={evidence, guilty} and µ2 = {evidence} of φ satisfy µ1 ≺K1 µ2 and µ2 ≺K2 µ1.

However, no acyclic paths of length 2|P| are possible.

In case of just two agents and easier preference checking, we interestingly get a better complexity bound:

Theorem 3. For a PAP P with n = 2 and model-preference definable operators ∗i such that µ′ ⪯Ki µ is decidable in polynomial space, deciding solution existence is in PSPACE.

Proof. In this case, no alternation in the algorithm above is needed: as µi |= ψi resp. µ′ |= ψj, for at most one j ∈ {1, 2} a guess µ′ ∈ mod(ψj) will be made; thus (∀) can be eliminated deterministically. As checking µ′ ⪯Kj µ is in PSPACE, membership in NPSPACE = PSPACE follows.

4.2 Lower Bounds

PAP with Dalal's Operator

Theorem 4. The PAP(∗d) problem (all ∗i are ∗d) is Σp2 -hard.

Proof. We reduce the evaluation of QBFs of the form

where X =X1, . . . , Xm and Y =Y1, . . . , Yl are lists (viewed as sets) of propositional variables in polynomial time to this problem. Without loss of generality, we assume that the following property (see Supplement):

• (*) |Y | is even, and if an assignment σ to X ∪ Y does not satisfy E, it sets exactly half of the variables in Y to 1, i.e., |{Yi ∈ Y | σ(Yi) = 1}| = |{Yi ∈ Y | σ(Yi) = 0}|.

We now construct knowledge bases Ki and formulas ψi, i = 1, . . . , n such that deciding whether some formula φ exists such that Ki ∗d φ |= ψi encodes the evaluation of Φ.

From Proposition 8, φ has w.l.o.g. the form µ1 ∨ · · · ∨ µn, where each µi is a model of ψi and the following holds: no µj that violates ψi will be closer to Ki than µi, i.e., satisfy dH(µj , Ki) < dH(µi, Ki).

In our encoding we need only n=2. The idea is that intuitively, we use the pair (K2, ψ2) to generate a candidate assignment σ to X via a model µ2 that will not be closer to K1 than any model µ1 for a solution φ = µ1 ∨ µ2 if ¬E(σ(X), Y ) is unsatisfiable, i.e., ∀Y E(σ(X), Y ) evaluates to true. Specifically, we define:

Here B and the Xi are disjoint sets of fresh variables, such that 2|B| = |Y | and |Xi | = |B|; we write B resp. Y for the conjunction of all variables in B resp. Y , and similarly B resp. Y for the conjunction of all negated variables in B resp. Y (e.g. for B = {B1,B2} we have that B stands for B1∧B2 and B for ¬B1 ∧¬B2). Furthermore, EQ(Xi, Xi ) expresses that all variables in Xi have the same value as Xi:

The purpose of B is to ensure that the distance of a candidate model µ1 for φ to K1 is at least |B| = |Y |/2; the purpose of the Xi is to ensure that the cost of flipping in a model µ2 of ψ2 a variable Xi to obtain a model of the left disjunct of K1 is, due to the variables in Xi , at least |B| + 1.

We now argue that Φ evaluates to true if and only if the constructed PAP instance has a solution.

• (⇒) Let σ be an assignment to X such that ∀Y E(σ(X), Y ) evaluate to true; hence, ¬E(σ(X), Y ) is unsatisfiable. We consider interpretations µ1 and µ2 as follows:

Note that µi |= ψ1 ∧ ¬ψ2 while µ2 |= ψ2 ∧ ¬ψ1. Consider now the distances dH(µi, Kj) for i, j = 1, 2:

• dH(µ1,K1)=|B|, as flipping B is enough to arrive at a model of the right disjunct of K1; there is no cheaper cost, as to satisfy the left disjunct of K1, by unsatisfiability of ¬E(σ(X), Y ) we would need to flip some Xi and the associated Xi , causing a distance > |B|;
• dH(µ2,K1)>|B|: to arrive at a model of the left disjunct of K1, since ¬E(σ(X), Y ) is unsatisfiable we need to flip some Xi and its associated variables Xi , which causes a distance > |B|; to arrive at a model of right disjunct of K1, flipping B ∪ Y has cost |B| + |Y |;
• dH(µ1,K2) = |B| + |Y |: just flip B ∪ Y ;
• dH(µ2,K2) = |B|: just flip B.

Hence, the disjunction φ = µ1 ∨ µ2 of the models µ1 and µ2 is a solution to the PAP from above.

(⇐) Suppose that without loss of generality some models µ1 and µ2 of ψ1 and ψ2, respectively, exist such that their disjunction φ = µ1 ∨ µ2 yields a solution of the PAP instance.

Then µ1 satisfies B ∧ Y and µ2 satisfies B ∧ Y . Let us consider the distance of µ1 to K1:

• d(µ1,K1) ≤ |B|, as it is sufficient to flip B to satisfy the right disjunct of K1;
• d(µ1,K1) ≥ |Y |/2, as if we do not flip B, we must flip exactly half of Y and perhaps some Xi and Xi to satisfy ¬E(X, Y ) in the left disjunct of K1.

As |B| = |Y |/2 it follows d(µ1,K1) = |B| = |Y |/2. Now let σ be the assignment to X s.t. σ(Xi) = 1 iff µ2 |= Xi, i = 1, . . . , n. We argue that ∀Y E(σ(X), Y ) evaluates to true. As µ2 ̸|= ψ1, we have dH(µ1,K1) < dH(µ2,K1); hence d(µ2,K1) > |Y |/2. As K1 is of the form K1 = K1,1 ∨ K1,2, each K1,j must satisfy d(µ2,K1,j) > |Y |/2, in particular K1,1 = ¬E(X, Y ) ∧ ∧Xi∈X EQ(Xi, Xi ). As µ2 |= ∧Xi∈X EQ(Xi,Xi ), this means that whenever exactly half of Y is flipped, the resulting interpretation does not satisfy ¬E(X, Y ); hence, for the respective assignment µ to Y , E(σ(X), µ(Y )) is satisfied. Hence ∀Y E(σ(X), Y ) evaluates to true, and so does Φ. This proves Σp2 -hardness.

Two remarks should be noticed:

1. We can rewrite the KBs Ki and queries ψi to CNFs in polynomial time, if we assume w.l.o.g. that E(X, Y ) is in DNF. Thus the Σp2 -hardness inherits to the CNF fragment.
2. If we assume that E(X, Y ) is in CNF and no Y variables occur in E(X, Y ), then we can rewrite K1 and K2 to DNF (note that we can rewrite in (5) EQ(Xi,Xi ) to a DNF (Xi∧∧Z∈Xi Z)∨(¬Xi∧∧Z∈Xi ¬Z). This then shows NPhardness as evaluating the QBF in (4) is NP-hard under these restrictions. Combined with Proposition 9, we thus obtain:

Theorem 5. For PAP(∗d), deciding solution existence is NPcomplete if all knowledge bases Ki are in DNF.

It is possible to extend the construction in order to have only Horn KBs Ki and Horn ψi; the idea is to simulate positive disjunction with choice of an atom for closer distance.

PAP with Ginsberg's Operator

We now provide matching lower bounds for the upper bounds for the PAP-problem in the general model preference case from above, specifically for Ginsberg's operator.

Theorem 6. For PAP(∗G), deciding solution existence is (i) EXPTIME-hard in general and (ii) PSPACE-hard if n = 2.

We sketch a proof of this result, which involves a reduction from the following problem.

A bipartite and-or graph is a tuple G = (N1, N2, E1, E2) of disjoint sets N1 and N2 of nodes, and of edges E1 and E2, respectively, where any edge in E1 (resp., E2) is of the form (n1, n2, n′2 ) ∈ N1×N2×N2 resp. (n2, n1) ∈ N2×N1. we assume that every node in N1 occurs in at most one edge of E1. Intuitively, the nodes in N1 are and-nodes and have either no or two (not necessarily) distinct successors, while N2 are or-nodes that can have multiple possible successors;

A nonempty set N ⊆ N1 ∪N2 of nodes is serial in G, if for every n1 ∈ N ∩ N1, some edge (n1, n2, n′2 ) ∈ E1 exists and both n2, n′2 are in N, and for every n2 ∈ N ∩ N2 some (n2, n1) ∈ E2 exists such that n1 ∈ N.

Lemma 1. Let γ1(X, Y,Z) and γ2(Y,X), where X = X1, . . . ,Xn and Y = Y1, . . . , Yn, Z = Z1, . . . ,Zn are Boolean formulas that describe the edges E1 resp. E2 of an and-or graph G with nodes N1 = {0}×{0, 1}n-1 and N2 = {1}×{0, 1}n-1 . Deciding whether G has some serial node set N is EXPTIME-hard.

Informally, this lemma holds as the and-or graph G may represent computations of an alternating Turing machine T, where nodes represent configurations c. In accepting c's with no successors, T is modified to loop back to the initial configuration c0, while other loops are excluded. Then a serial set N exists iff the modified T has a looping run on all branches, i.e., the original T accepts on all branches. As T runs in polynomial space, deciding the latter is EXPTIME-hard.

We now construct a PAP instance as follows:

where

Op′ (X; Y ; Z) = (X ↔¬X′ )∧(Y ↔¬Y ′ )∧(Z ↔¬Z ′ ). Here X′ , Y ′ and Z ′ are copies of X, Y , and Z, respectively, and X0, Y0, Z0 are fresh variables.

Intuitively, ψ1 describes edges from "universal" nodes in N1, while ψ2 and ψ3 describe edges from "existential" nodes in N2, where the variables X′ , Y ′ and Z ′ serve to create incomparability among the encoding of nodes (to avoid clutter by possible world maximization revision ∗G). The formulas ψ1, ψ2 and ψ3 are pairwise mutually inconsistent via the variables X0, Y0, and Z0. Thus a move from an and-node n0 to n1 and n′1 expressed by a model of ψ1 must be followed by a move from n1 (resp. n′1 ) to some and-node n2 (resp. n′2 ) expressed by a model of ψ2. It can be shown that the and-or graph G has a nonempty serial set N iff the PAP(∗G) given by P = (Ki, ψi)3i=1 has a solution.

Case n = 2: with a simplified construction, we can obtain PSPACE-hardness: if each universal state has a single transition i.e., (n1, n2, n′2 ) ∈ E1 implies n2 = n′2 , we have an ordinary graph (intuitively describing non-alternating computations). The Z variables can then be replaced by Y , and K3 and ψ3 can be dropped.

4.3 Constructing PAP Solutions

The algorithms above are constructive and can be used to obtain a solution to a PAP. In fact, Theorems 1 and 4 (respectively their proof) establish that computing some PAP solution for AGM-style revision operators is complete for the multi-valued function analog of Σp2 , i.e. the search problems that can be solved by a nondeterministic Turing machine with an output tape and an NP oracle in polynomial time.

For model-preference based PAPs, the solutions obtained may not be of polynomial size. Indeed, as deciding K∗Gφ |= ψ is Πp2 -complete [Eiter and Gottlob, 1992], it follows that verifying whether a formula φ is a solution of a PAP(∗G) P has the same complexity. Thus if always some polynomial size φ would exist, a guess and check algorithm would put solution existence in Σp3 and EXPTIME ⊆ Σp3 would follow.

Polynomial-size solutions φ can be guessed and the conditions in Proposition 5 checked in exponential time. Note that the weakest solution φ∗ of a model-preference based PAP P is an envelope, computable by an elimination algorithm:

1. Initially, set X0 to the set of all interpretations.
2. Remove then iteratively from Xi a model µ, such that µ ̸|= ψj for some j and no model µ′ ∈ Xi with µ′ |= ψj and µ′ ≺j µ exists, i.e., set Xi+1 := Xi \ {µ}.

Any µ in Step 2 is a "bad model" and must be eliminated, as it would be a revision model but fails to satisfy the query. If X(P) denotes the final Xi, then we have:

Proposition 10. For a PAP P with model-preference operators ◦i, the weakest solution φ∗ fulfills mod(φ∗ )=X(P), where no solution exists if X(P)=∅.

4.4 Reasoning About Solutions

It is of interest to know whether a formula α is a semantic core for the solutions, given by α |= φ for every solution φ, and dually, whether a formula β is an envelope for the solutions, given by φ |= β for every solution φ. In a sense, a core describes possible models that must be compatible with every announcement for belief manipulation, while an envelope limits the models that can be used. Based on the results and techniques above, we can show:

Theorem 7. Deciding whether α is a core (resp., β is an envelope) for a PAP P is (i) EXPTIME-complete for model-preference decidable in exponential time and (ii) Πp2 - complete for operators ◦i definable with total preorders ≺Ki decidable in P NP .

In fact, φ∗ coincides with the logically strongest envelope β∗ , i.e., β∗ |= β for each envelope β; it is intuitively the vaguest statement that one can make to accomplish belief manipulation. A formula γ is thus implied by every solution φ iff it is implied by φ∗ . Dually, a unique weakest core α∗ exists, i.e., α |= α∗ for every core α, which is equivalent to the conjunction of all solutions. Intuitively, it is a lower bound of vagueness for the announcement, which can be void if e.g. solutions φ and φ′ are incompatible, i.e., φ∧φ′ is unsatisfiable. For deciding whether β∗ |= γ resp. α∗ |= γ holds for given PAP and γ, similar results as in Theorem 7 can be obtained, with the interesting exception that in (ii) deciding α∗ |= γ is Σp2 -complete by exploiting Proposition 8.

5 RelatedWork

5.1 Dynamic Epistemic Logic

Dynamic Epistemic Logic (DEL) refers to a class of modal logics for reasoning about actions and belief [Ditmarsch et al., 2008]. In DEL, the announcement problem is addressed in arbitrary public announcement logic (APAL) [Balbiani et al., 2007]. Contrary to us, APAL does not provide any revision mechanism, but allows for higher-order knowledge sentences. The model checking problem of APAL is in PSPACE [ ˚Agotnes et al., 2010], but contrary to our case, their input model is represented explicitly. Closer to our setting, the model checking of APAL in its succinct form is NEXPTIMEcomplete [Charrier and Schwarzentruber, 2015] (see also [Charrier et al., 2019] for a more comprehensive study). The satisfiability problem of APAL is undecidable [French and van Ditmarsch, 2008], but gets decidable when announcements are propositional [van Ditmarsch and French, 2017].

5.2 Non-Modal Belief Revision

Schwind et al. [2019] considered a related problem called inverse revision (IR): when is Ki ∗i φ = ψi for all agents i possible, where φ and any AGM-style revision operators ∗i can be chosen; the set of all such φ is called the frame, which is complete if any φ and φ′ are logically equivalent. Checking whether a formula φ is in the frame is co-NP-complete, and deciding frame-completeness is Πp2 -complete.

Apparently, IR solutions are PAP solutions when the operators are fixed, but not the other way around. In fact, the aims of IR and PAP are different: the former wants to achieve an exact local belief state, while PAP aims to achieve goal fulfillment by an announcement. Our complexity results show that for AGM operators, the reasoning tasks can be intertranslated in polynomial time; studying this remains for future work.

6 Conclusion

We have considered the complexity of public announcement finding in a non-modal setting, where agents incorporate announcements using a revision operator. We have shown that for all AGM style operators, deciding existence of a solution is always in Σp2 and Σp2 -hard for Dalal's operator, closing an open problem. Furthermore, we have shown that for all operators definable by preorders, the problem is in EXPTIME in general and EXPTIME-hard for Ginsberg's operator. Moreover, we proved lower complexity under restrictions.

Our work can be extended in different directions. First, one may consider other revision operators, such as those in [Eiter and Gottlob, 1992] or iterated revision operators [Darwiche and Pearl, 1997; Jin and Thielscher, 2007]. In this context, extending our main results to relations ⪯K that always allow for revision models seems possible. Second, besides AGM revision operators Katsuno and Mendelzon [1991] characterized update operators ⋄ as in [Winslett, 1988; Forbus, 1989], which reflect change of the world rather than of the belief about the world, by model selection; specifically, mod (K ⋄ φ) = ⋃µ|=K min⪯µ(mod (φ))), where ⪯µ is a preorder. Using update operators for public announcements is natural; by our techniques, the respective solution existence problems can be solved in exponential time.

Finally, in addition to extending our approach to different revision operators, it would also be interesting to consider the application of the techniques used in this paper in other domains, such as preference aggregation.