d4-conf-aaai-2010-0019 (d4-conf-aaai-2010-0019)

Given a finite set \(A\), supported propositional IIA types \(I_1,\ldots,I_\tau\) with rational masses \(\mu_i\) summing to \(1\), and sets \(X,Y\subseteq A\), decide whether \(\sum_{i:\,X\succeq_{I_i}Y}\mu_i\ge\frac12\), where \(X\succeq_{I_i}Y\) means an improving sequence under \(I_i\) leads from \(Y\) to \(X\).

Let \(A\) be a finite universe with \(m=|A|\), and let \(X,Y\subseteq A\).
A society is given by its support: an explicit list of \(\tau\) types with positive binary rational masses \(\mu_i\), where \(\sum_i\mu_i=1\). Here \(\tau\) is the support size, not the number of possible types.
Each propositional incremental-improvement type \(I_i\) is an explicitly listed finite set of statements \(\epsilon:\varphi\), where \(\varphi\) is a propositional formula over atoms \(\operatorname{in}(a),g(a),l(a),t(a,b)\), with \(a,b\in A\).
On a current set \(E\), \(g(a)\) adds an absent \(a\); \(l(a)\) removes a present \(a\); and \(t(a,b)\) replaces a present \(a\) by an absent \(b\). These are the only permitted modifications.
A statement permits its modification exactly when that modification is applicable and its condition holds before the move. The atom \(\operatorname{in}(a)\) tests current membership; each modification atom tests whether that particular operation occurred earlier in the sequence.
An improving sequence starts with empty operation history and follows permitted modifications. Its length is unrestricted, including zero; histories persist throughout it, and sets and operations may recur.
Write \(X\succeq_{I_i}Y\) when one improving sequence leads from \(Y\) to \(X\); this denotes direct sequence reachability, without taking a further transitive closure. Types need not be consistent or acyclic.
Let \(L\) be the total binary input length, including all statements, formulas, masses and sets; state running times in \(m,\tau,L\).

Is deciding whether \(\sum_{i:\,X\succeq_{I_i}Y}\mu_i\ge\frac12\) solvable in polynomial time, or is it \(\mathrm{NP}\)-hard?

Known discrete results: generalized binary CP-net reachability has a polynomial translation into these types preserving comparisons; unrestricted propositional incremental-improvement reachability is \(\mathrm{PSPACE}\)-complete. [Source](https://cdn.aaai.org/ojs/7584/7584-13-11114-1-2-20201228.pdf)
Generalized binary CP-net dominance is also \(\mathrm{PSPACE}\)-complete. [Source](https://www.lamsade.dauphine.fr/~lang/papers/gltw08.pdf)
No result addressing exactly the rational-mass society decision problem was located.

Result. The society decision problem is \(\mathrm{PSPACE}\)-complete under polynomial-time many-one reductions, and therefore \(\mathrm{NP}\)-hard. Hardness holds even when \(\tau=1\), the sole mass is \(1\), and conditions contain only membership atoms.

Consequently, a polynomial-time algorithm exists if and only if \(\mathrm{P}=\mathrm{PSPACE}\).

1. Degenerate case and intended scope.

If \(X=Y\), the zero-length sequence witnesses reachability for every type, so the supporting mass is \(1\). We prove hardness for instances with \(X\ne Y\), allowing the universe and explicitly listed types to vary with the input.

2. Polynomial-time reduction establishing hardness.

We use the following known theorem: deciding whether one outcome reaches a distinct target outcome by improving flips in a generalized binary CP-net is \(\mathrm{PSPACE}\)-complete. Theorem 1 establishes hardness, and its proof uses distinct endpoints. Thus allowing zero-length sequences does not affect this hardness result. See [Goldsmith, Lang, Truszczyński, and Wilson, Theorem 1](https://www.lamsade.dauphine.fr/~lang/papers/gltw08.pdf).

Let such an instance have Boolean variables \(V\), initial outcome \(\alpha\), and target outcome \(\beta\), with \(\alpha\ne\beta\). Construct a universe \(A=V\), identifying each variable with one element. Represent an outcome \(\gamma\) by

\[ E_\gamma=\{a\in A:\gamma(a)=1\}. \]

Here and below, the displayed expression means \(E_\gamma=\{a\in A:\gamma(a)=1\}\).

For each CP-net rule whose condition is \(\psi\):

• If the rule permits changing variable \(a\) from false to true, include \(g(a):\widehat{\psi}\).
• If it permits changing \(a\) from true to false, include \(l(a):\widehat{\psi}\).

The formula \(\widehat{\psi}\) replaces each variable \(b\) in \(\psi\) by \(\operatorname{in}(b)\), preserving every Boolean connective. This is the standard translation described in [Brewka, Truszczyński, and Woltran, “Expressive Power of IIA”](https://cdn.aaai.org/ojs/7584/7584-13-11114-1-2-20201228.pdf).

We verify the translation directly. Under the outcome–set correspondence, \(\psi\) holds at \(\gamma\) exactly when \(\widehat{\psi}\) holds at \(E_\gamma\). Moreover, \(g(a)\) is applicable exactly when \(a\) is false, and \(l(a)\) exactly when \(a\) is true. Their resulting sets represent precisely the corresponding flipped outcomes.

Thus every permitted CP-net flip corresponds to a permitted modification, and conversely. Applying this observation at each step proves equivalence of the two kinds of sequences. No condition mentions operation history, so previously performed operations cannot change this equivalence.

Set \(Y=E_\alpha\) and \(X=E_\beta\). Create a society consisting only of the translated type \(I\), with mass \(1\). Its supporting mass is \(1\) when \(X\succeq_IY\), and \(0\) otherwise. Therefore,

\( \displaystyle \sum_{i:\,X\succeq_{I_i}Y}\mu_i\ge\frac12 \quad\Longleftrightarrow\quad \text{an improving CP-net sequence leads from }\alpha\text{ to }\beta. \)

The translation copies formulas with constant-factor syntactic overhead, and the society adds only a constant-size mass representation. It is polynomial-time and produces a valid input. This proves \(\mathrm{PSPACE}\)-hardness.

3. Polynomial-space reachability with persistent histories.

Fix a type \(I_i\). Let \(O_i\) be the set of distinct operations appearing as statement heads, and write \(q_i=|O_i|\). Only operations in \(O_i\) can occur. Every history atom naming an operation outside \(O_i\) consequently remains false.

A complete state is a pair \((E,H)\), where \(E\subseteq A\) is the current set and \(H\subseteq O_i\) records the operations that have occurred at least once. This representation suffices because conditions inspect only current membership and whether each particular operation occurred earlier.

The initial state is \((Y,\varnothing)\). For every statement \(\epsilon:\varphi\), include an edge

\( (E,H)\longrightarrow\bigl(\epsilon(E),H\cup\{\epsilon\}\bigr) \)

exactly when \(\epsilon\) is applicable to \(E\) and \(\varphi\) evaluates to true at \((E,H)\). Conditions are evaluated before updating the history, as required.

There are at most \(2^{m+q_i}\) states. Checking an edge requires only polynomial time and space in \(m,L\): scan the explicit statements, evaluate their formulas, and check the specified modification and history update.

Add one accepting vertex \(z\), with an edge from every state \((X,H)\) to \(z\). Then \(X\succeq_{I_i}Y\) holds exactly when \(z\) is reachable from \((Y,\varnothing)\).

Whenever such a path exists, a shortest path has no repeated vertex: deleting the segment between repeated vertices preserves all subsequent edges because the vertices include the complete history information. Its length is therefore at most \(2^{m+q_i}\).

For completeness, deterministic reachability can be implemented recursively. Let \(R_k(u,v)\) mean that a path of length at most \(2^k\) connects \(u\) to \(v\). Define \(R_0(u,v)\) by equality or a single edge, and for \(k\ge1\) use

\( R_k(u,v)\quad\Longleftrightarrow\quad \exists w\;\bigl(R_{k-1}(u,w)\land R_{k-1}(w,v)\bigr). \)

The equivalence follows by splitting a path after at most \(2^{k-1}\) edges; the reverse implication concatenates the two paths. Enumerate \(w\) sequentially and evaluate the recursion depth first.

Taking \(k=m+q_i\) suffices. Each recursion frame stores a constant number of vertices and counters, using \(O(m+q_i+1)\) bits. The recursion depth is \(O(m+q_i+1)\). Thus the space bound is

\( O\bigl(L+(m+q_i+1)^2\bigr). \)

If the universe contains elements never named in the statements, formulas, \(X\), or \(Y\), discard them: they start absent, cannot be modified, and are absent from the target. After this preprocessing, the number of relevant elements is \(O(L)\). Hence the space bound is polynomial in the binary input length.

4. Exact rational aggregation and running time.

Write each input mass as \(\mu_i=p_i/d_i\), with positive binary integers \(p_i,d_i\). Define

\( D=\prod_{i=1}^{\tau}d_i,\qquad P=\sum_{i:\,X\succeq_{I_i}Y}p_i(D/d_i). \)

The desired decision is exactly \(2P\ge D\). The bit length of \(D\) is at most \(1+\sum_i\log_2 d_i=O(L)\). Since the masses are positive and sum to \(1\), every partial accumulated numerator lies between \(0\) and \(D\). Thus exact aggregation uses polynomial space and polynomial-time arithmetic per update.

Run the reachability procedure for each listed type sequentially, reusing its workspace and updating \(P\). This proves membership in \(\mathrm{PSPACE}\).

For an explicit deterministic running-time bound, let

\( q=\max_i q_i,\qquad n=\max\{1,m+q\}. \)

The recursive procedure has depth at most \(n\), and each call enumerates at most \(2^n+1\) intermediate vertices with two recursive subcalls each. Consequently, the entire society decision takes

\( \tau\,2^{O(n^2)}\operatorname{poly}(m,L) \)

time and \(O(L+n^2)\) space. Because \(q\le\min\{m^2+2m,L\}\), a bound solely in the requested parameters is

\( \tau\,2^{O((m+\min\{m^2+2m,L\}+1)^2)}\operatorname{poly}(m,L). \)

These are upper bounds, not assertions of optimal running time. Together with the reduction, they establish the claimed completeness result.

⟨structured verdict parsed — rendered above⟩

The claimed result is correct: the society decision problem is \(\mathrm{PSPACE}\)-complete, hence \(\mathrm{NP}\)-hard. The proof addresses the specified persistent-history semantics and exact rational threshold. No major or minor mathematical issues were found.

• Zero-length sequences and distinct endpoints.

If \(X=Y\), every type admits the zero-length sequence, so the supporting mass is \(1\). The hardness argument explicitly uses \(X\ne Y\), avoiding any mismatch between reflexive reachability in the task and nonempty improving sequences in the cited dominance problem.

• The cited hardness theorem.

The cited Theorem 1 establishes \(\mathrm{PSPACE}\)-completeness of generalized propositional CP-net dominance, even for consistent nets in conjunctive form. Its proof explicitly uses distinct initial and target outcomes. Thus the restricted source problem invoked by the prover is indeed \(\mathrm{PSPACE}\)-hard. The source represents nets by explicitly listed preference rules with propositional conditions, matching the representation needed by the reduction. [Goldsmith et al., definitions and Theorem 1](https://www.lamsade.dauphine.fr/~lang/papers/gltw08.pdf).

• Translation of individual rules.

The outcome–set correspondence is bijective. Replacing each variable by its membership atom preserves the truth value of every condition.

A false-to-true flip corresponds exactly to an applicable \(g(a)\), and a true-to-false flip corresponds exactly to an applicable \(l(a)\). The resulting set represents the flipped outcome. Conversely, every permitted modification in the constructed type comes from a source rule.

These checks establish equivalence step by step in both directions. Because the constructed conditions contain no history atoms, accumulated histories cannot affect this equivalence. The translation also agrees with the construction in the cited “Expressive Power of IIA” section. [Brewka et al., CP-net translation](https://cdn.aaai.org/ojs/7584/7584-13-11114-1-2-20201228.pdf).

• Reduction to the society threshold.

With one type of mass \(1\), the supporting mass is exactly \(1\) for a reachable target and \(0\) otherwise. Consequently, the threshold \(\frac12\) distinguishes precisely the source problem’s yes-instances.

The construction uses permitted operations, explicit formulas, and a valid positive rational mass. Formula substitution and construction of the endpoint sets take polynomial time. The claimed hardness restriction to \(\tau=1\) and membership-only conditions is therefore established.

• State representation with persistent histories.

The pair \((E,H)\) contains all information inspected by the conditions: current membership and whether each operation has previously occurred. Recording multiplicities or order is unnecessary under the task’s semantics.

Operations absent from statement heads can never occur, so their history atoms remain false. Evaluating conditions before updating \(H\) correctly handles conditions referring to the operation currently being considered, including repeated operations.

The transition relation therefore represents direct sequence reachability with persistent histories. It does not inadvertently introduce history resets or a further transitive closure.

• Finite-state reachability and recursion.

There are at most \(2^{m+q_i}\) ordinary states. Adding \(z\) gives at most \(2^{m+q_i}+1\) vertices, so a shortest accepting path has at most \(2^{m+q_i}\) edges. The stated bound correctly includes the final edge to \(z\).

Deleting a segment between repeated complete states preserves subsequent transitions, since both membership and history agree.

The recurrence for \(R_k\) is correct for paths of length *at most* \(2^k\). Its equality base case permits either subpath to have length zero. Taking \(k=m+q_i\) therefore suffices.

Sequential enumeration and depth-first evaluation require only a constant number of vertex descriptions and counters per frame. With polynomial workspace for formula evaluation and input processing, the claimed space bound
\[ O\bigl(L+(m+q_i+1)^2\bigr) \]
is justified.

• Input length and edge cases.

Discarding elements absent from all statements, formulas, and endpoint sets is valid: they begin absent, cannot be modified, and are not required by the target. The remaining number of elements is \(O(L)\), which establishes polynomial space in the binary input length.

Empty types and an empty universe cause no failure: reachability still includes equality, and the auxiliary-vertex construction and recursion cover these cases.

• Exact rational aggregation.

Each \(D/d_i\) is an integer, and \(P/D\) is exactly the supporting mass. Thus \(2P\ge D\) is precisely the required decision, including equality at the threshold.

The product denominator has \(O(L)\) bits. Positivity and normalization imply that every accumulated numerator lies between \(0\) and \(D\). Exact arithmetic therefore requires polynomial space and polynomial time per arithmetic update. Sequential processing of types preserves the polynomial-space bound.

• Running time and final classification.

With at most \(2^n+1\) intermediate vertices per recursive call and depth at most \(n\), the stated bound
\[ \tau\,2^{O(n^2)}\operatorname{poly}(m,L) \]
is valid. The bound \(q\le\min\{m^2+2m,L\}\) correctly bounds the number of distinct statement-head operations.

Membership and hardness establish \(\mathrm{PSPACE}\)-completeness. The conclusions of \(\mathrm{NP}\)-hardness and polynomial-time solvability if and only if \(\mathrm{P}=\mathrm{PSPACE}\) follow.

Repair feedback: None required; the argument is verifiable as written.

⟨structured verdict parsed — rendered above⟩