Answer: \(\mathrm{PSPACE}\)-complete, hence \(\mathrm{NP}\)-hard, already for \(\tau=1\) and \(s=2\).
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe following problem is PSPACE-complete: Given a PCS C and two of its outcomes M and M ′, decide whether M ⪯PCS M ′.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set \(T\) of PCS types with rational masses \(\mu_t>0\) summing to \(1\), and two finitely supported rational mass profiles over each type's outcomes that preserve \(\mu_t\), is there a finite sequence of profiles from the first to the second, each step transferring mass along an improving single-component flip? Require endpoint configurations to satisfy global constraints; as in PCS semantics, intermediate configurations may violate them.
A society is given by its support: a list \(T\) of \(\tau\) PCS types with positive binary rational masses \(\mu_t\), summing to \(1\). Here \(\tau=|T|\) counts listed types, not possible types.
A type is a succinctly specified prioritized component system \((\Pi_t,G_t,P_t,\Phi_t)\). Its components are finite propositional normal answer-set programs with cardinality and weight constraints, with pairwise disjoint atom sets; their answer sets are component values. Global constraints \(G_t\) are integrity constraints over these atoms. Parent sets \(P_t(C)\) may induce cycles.
A configuration \(M\) chooses one answer set \(M(C)\) for each component. It is feasible when the union \(U_M=\bigcup_C M(C)\) satisfies \(G_t\). Configuration spaces are implicit, not enumerated.
Each rule in \(\Phi_{t,C}\) has form \(\gamma_1>\cdots>\gamma_k\leftarrow\alpha\): heads are Boolean combinations of literals and default-negated literals of \(C\); the body is a conjunction of literals and default-negated literals from \(C\) and its parents. Evaluate a literal by membership in \(U_M\), default negation by absence, and conjunction and disjunction ordinarily.
For a rule \(r\), let \(d_r(M)\) be the least satisfied head index when its body holds and some head holds; otherwise set \(d_r(M)=1\). Smaller degrees are better, including this equivalence between irrelevance and degree \(1\).
An improving flip \(M\to N\) changes exactly one component \(C\) to a different answer set and satisfies \(d_r(N)\le d_r(M)\) for every \(r\in\Phi_{t,C}\). Indifferent flips are allowed; strict improvement is not required.
The input gives two profiles \(x^0,x^1\) by explicit lists of configurations and nonnegative binary rational masses, with \(\sum_M x^i_{t,M}=\mu_t\) for every type and endpoint. Every configuration with positive endpoint mass must be feasible.
A profile may use any configurations, with nonnegative rational masses preserving each \(\mu_t\). One step chooses a type, an improving flip \(M\to N\), and a rational amount \(0<\delta\le x_{t,M}\), subtracts \(\delta\) at \(M\), and adds it at \(N\). Intermediate configurations need not satisfy \(G_t\); new support configurations are allowed.
Let \(m\) be the maximum number of components in a listed type, \(s\) the total number of listed endpoint support entries, and \(L\) the total binary input length, including programs, rules, configurations and masses. State running times in \(m,\tau,s,L\).
Is deciding whether a finite, possibly empty sequence of these mass-transfer steps takes \(x^0\) to \(x^1\) solvable in polynomial time, or is it \(\mathrm{NP}\)-hard?
Discrete reachability between two feasible PCS configurations is \(\mathrm{PSPACE}\)-complete. [Source](https://cdn.aaai.org/AAAI/2005/AAAI05-093.pdf)
No result settling this exact mass-profile problem was located in the literature search.
The problem is \(\mathrm{PSPACE}\)-complete, and therefore \(\mathrm{NP}\)-hard. Hardness already holds with one listed type and one positive configuration in each endpoint profile: \(\tau=1\) and \(s=2\).
A polynomial-time algorithm would consequently imply \(\mathrm{P}=\mathrm{PSPACE}\).
For each listed type \(t\), define a finite directed graph \(D_t\).
Its vertices are all configurations choosing one answer set for each component, whether or not they satisfy \(G_t\). Its edges are exactly the improving flips specified in the question. Write \(A\leadsto_t B\) when \(B\) is reachable from \(A\), allowing a path of length zero.
This graph uses the intended semantics: global constraints restrict positive endpoint configurations, but do not restrict intermediate configurations.
The cited discrete-reachability theorem applies to these semantics. Specifically, the paper identifies irrelevance with satisfaction degree \(1\), defines improving flips using weak Pareto preference, and permits intermediate configurations violating global constraints. Its Theorem 4 states that deciding reachability between two feasible configurations is \(\mathrm{PSPACE}\)-complete. [Brewka, Niemelä, and Truszczyński, *Prioritized Component Systems*, Definitions 3–4 and 9–10, Theorem 4](https://cdn.aaai.org/AAAI/2005/AAAI05-093.pdf).
We first establish an invariant that applies even when transfers split mass.
Lemma. Suppose a type initially has positive mass only at configuration \(A\). After any finite sequence of permitted transfers, every configuration with positive mass is reachable from \(A\).
Proof. Initially, the assertion holds because \(A\leadsto_t A\).
Suppose it holds before a transfer along an edge \(M\to N\). Since the transferred amount is positive and does not exceed the mass at \(M\), configuration \(M\) has positive mass before the transfer. Thus \(A\leadsto_t M\). Appending the edge gives \(A\leadsto_t N\).
Only \(N\) can acquire positive mass without having had positive mass before this step. Hence the assertion remains true. Induction proves the lemma. \(\square\)
Now take an instance of discrete PCS reachability, consisting of a PCS and feasible configurations \(A,B\). Construct a society with that PCS as its only listed type, set \(\mu_t=1\), and define the endpoint profiles by
\(x^0_{t,A}=1,\qquad x^1_{t,B}=1,\)
with all other masses zero. This construction takes polynomial time and satisfies every endpoint requirement.
If \(A\leadsto_t B\), transfer the entire unit of mass along each successive edge of a witnessing path. Every transfer is permitted and the resulting profile is \(x^1\). If the path is empty, the empty transfer sequence suffices.
Conversely, if a transfer sequence reaches \(x^1\), then \(B\) has positive final mass. The lemma implies \(A\leadsto_t B\).
Thus this is a polynomial-time many-one reduction from discrete PCS reachability. The mass-profile problem is \(\mathrm{PSPACE}\)-hard, already for \(\tau=1\) and \(s=2\). In particular, it is \(\mathrm{NP}\)-hard.
For completeness, we characterize arbitrary endpoint profiles and prove the matching upper bound.
Discard zero-mass endpoint entries and combine repeated configurations. For a fixed type \(t\), write its initial positive support as \(A_1,\ldots,A_p\), with masses \(a_1,\ldots,a_p\), and its final positive support as \(B_1,\ldots,B_q\), with masses \(b_1,\ldots,b_q\). Thus
\(\sum_{i=1}^{p}a_i=\sum_{j=1}^{q}b_j=\mu_t.\)
Transport lemma. The initial distribution can be transformed into the final distribution if and only if there exist nonnegative rational numbers \(f_{ij}\) satisfying
\(\sum_{j=1}^{q}f_{ij}=a_i\quad\text{for every }i,\)
\(\sum_{i=1}^{p}f_{ij}=b_j\quad\text{for every }j,\)
and
\(f_{ij}=0\quad\text{whenever }A_i\not\leadsto_t B_j.\)
Necessity. Label the initial mass at \(A_i\) with label \(i\). Maintain nonnegative rational amounts of each label at each configuration, summing to that configuration’s actual mass.
For a transfer of amount \(\delta\) from \(M\) to \(N\), choose label amounts totaling \(\delta\) from those available at \(M\), and transfer those amounts to \(N\). Such a choice exists because the available total is at least \(\delta\). It can be made rational by taking, successively, the smaller of the available amount of a label and the remaining amount to transfer.
Inductively, positive mass with label \(i\) can occur only at configurations reachable from \(A_i\): initially it occurs at \(A_i\), and each transfer follows an edge.
At the end, let \(f_{ij}\) be the amount of label \(i\) at \(B_j\). Each label’s total mass is conserved, giving the row equations. The actual final masses give the column equations. Nonnegativity ensures that no labeled mass remains outside the final positive support. Finally, the reachability invariant gives the required zero entries.
Sufficiency. For each positive \(f_{ij}\), choose a finite path from \(A_i\) to \(B_j\). Partition the initial mass at \(A_i\) into labeled packets of sizes \(f_{ij}\), which is possible by the row equation.
Process the packets one at a time. Move each packet along its chosen path, transferring exactly its size on every edge. At each step, that packet is present at the source configuration, so the total mass there is at least the transferred amount. Other packets can remain in place even if they share that configuration.
All amounts are rational. There are finitely many packets and every chosen path is finite, so this produces a finite legal transfer sequence. A packet assigned a path of length zero requires no transfer. At the end, the column equations give exactly the required final masses. \(\square\)
Transfers never move mass between types. Consequently, a global profile transformation exists exactly when the transport condition holds for every listed type: necessity follows by restricting a global sequence to each type, and sufficiency follows by concatenating the sequences constructed for the individual types.
For each type, construct a network with a source, an initial-support layer, a final-support layer, and a sink.
Use the following capacities:
The two support layers are separate copies, even when an initial and final configuration coincide. Such a pair has a middle arc because length-zero reachability is allowed.
A flow of value \(\mu_t\) saturates all source arcs and all sink arcs: each group has total capacity \(\mu_t\). Its middle-arc flows therefore satisfy exactly the transport lemma’s equations. Conversely, any matrix satisfying those equations defines a flow of value \(\mu_t\). The middle capacities impose no additional restriction because every matrix entry is at most the total mass \(\mu_t\).
Rational capacities cause no difficulty. Let \(D\) be the product of the denominators of all input masses. Its binary length is \(O(L)\), and multiplying capacities by \(D\) produces integer capacities of \(O(L)\) bits. Integer maximum flow yields rational flows after division by \(D\).
Thus the additional computation, once the required reachability answers are known, takes polynomial time.
Let \(p_t,q_t\) denote the positive endpoint-support sizes for type \(t\). The number of reachability questions needed is
\(Q=\sum_{t\in T}p_tq_t\le s^2.\)
Only the listed types are processed.
To bound each reachability computation, let \(n_t\) be the number of atoms across the components of type \(t\). Since atom sets are disjoint, a configuration is encoded by an \(n_t\)-bit membership vector, and there are at most \(2^{n_t}\) configurations. Moreover, \(n_t\le L\).
For the specified normal component programs, checking a proposed answer set takes polynomial time. This is the component-verification property used in the cited paper’s complexity section. [*Prioritized Component Systems*, complexity section](https://cdn.aaai.org/AAAI/2005/AAAI05-093.pdf). Hence vertex validity and edge validity can be checked in \(\operatorname{poly}(m,L)\) time: check component answer sets, check that exactly one component changes, and evaluate and compare that component’s rule degrees. Binary weight sums have polynomial bit length.
A reachable vertex admits a path with no repeated vertices, obtained by deleting cycles from any witnessing path. Its length is therefore less than \(2^{n_t}\).
For an explicit deterministic polynomial-space procedure, let \(R_k(U,V)\) mean that a path of length at most \(2^k\) exists. Set
\(R_0(U,V)\iff U=V\text{ or }U\to V,\)
and, for \(k\ge 1\), use
\(R_k(U,V)\iff\exists W\in V(D_t)\,[R_{k-1}(U,W)\land R_{k-1}(W,V)].\)
The recurrence is correct by splitting a path into two portions of length at most \(2^{k-1}\), or concatenating two such portions. Enumerate candidate \(W\) using an \(n_t\)-bit counter and reject invalid configurations.
Depth-first evaluation of \(R_{n_t}\) has recursion depth \(n_t\). Each frame stores only a constant number of configuration vectors and counters. It therefore uses polynomial space. At each level there are at most \(2^{n_t}\) candidates and two recursive calls per candidate, giving time
\(2^{O(n_t^2)}\operatorname{poly}(m,L).\)
Store the resulting support reachability relations and run maximum flow for each type. The stored networks have polynomial size in \(s\). For example, Edmonds–Karp uses \(O(s_t^5)\) arithmetic operations for a type with \(s_t=p_t+q_t\), since its network has \(O(s_t)\) vertices and \(O(s_t^2)\) edges. Each operation uses numbers with \(O(L)\) bits, and \(\sum_t s_t^5\le s^5\).
An explicit overall deterministic time bound is therefore
\(O\!\left(s^2\,2^{O(L^2)}\operatorname{poly}(m,L)+(\tau+s^5)\operatorname{poly}(m,L)\right),\)
with space \(\operatorname{poly}(m,\tau,s,L)\).
This proves membership in \(\mathrm{PSPACE}\). Together with the reduction above, it establishes \(\mathrm{PSPACE}\)-completeness and settles the requested hardness question.
⟨structured verdict parsed — rendered above⟩
The prover’s argument is correct and resolves the task. It establishes \(\mathrm{PSPACE}\)-completeness, hence \(\mathrm{NP}\)-hardness, including the restriction to one listed type and one positive configuration in each endpoint profile. No major or minor mathematical issues were found.
The vertices of \(D_t\) correctly include every tuple of component answer sets, regardless of global feasibility. Its edges use precisely the question’s improving-flip condition. Global constraints therefore restrict positive endpoint configurations without restricting intermediate vertices.
The cited theorem applies to the stated semantics. In the [source paper](https://cdn.aaai.org/AAAI/2005/AAAI05-093.pdf), Definitions 3–4 identify irrelevance with degree \(1\) in the preference preorder and use weak Pareto comparison. Definition 9 requires a change in exactly one component. Definition 10 explicitly permits intermediate configurations violating global constraints. Theorem 4 states \(\mathrm{PSPACE}\)-completeness for deciding whether one feasible PCS outcome is PCS-preferred to another. The complexity section includes component programs with cardinality and weight constraints.
Thus neither indifferent flips nor infeasible intermediate configurations create a mismatch with the cited hardness result. The source problem’s syntax is contained in the task’s allowed syntax.
The invariant is correctly stated for a type whose initial mass is concentrated at \(A\).
Its induction step uses the essential positivity condition: because \(0<\delta\le x_{t,M}\), the source \(M\) has positive mass immediately before the transfer. The induction hypothesis therefore gives \(A\leadsto_t M\), and the transfer edge gives \(A\leadsto_t N\).
Only the destination can acquire positive mass at a previously unoccupied configuration. Decreasing the source mass cannot introduce another positive-support configuration. This proves the invariant for every finite sequence, including sequences that split or recombine mass.
The construction preserves the PCS and its feasible endpoints, adds one type of mass \(1\), and places unit mass at \(A\) initially and at \(B\) finally. Its encoding size is polynomial in the discrete instance size.
Both implications are justified:
The case \(A=B\) is correctly covered by empty paths and empty transfer sequences. There remains one listed support entry in each endpoint profile, so \(s=2\) under the task’s definition.
This proves \(\mathrm{PSPACE}\)-hardness and consequently \(\mathrm{NP}\)-hardness.
Combining duplicate configurations and discarding zero-mass entries preserves the endpoint distributions.
The labeling argument is valid. Each transfer can be divided among the finitely many available labels using rational amounts; the stated successive-minimum procedure supplies the required allocation.
Label mass is conserved and follows graph edges. Consequently, label \(i\) can reach only configurations reachable from \(A_i\). At termination, nonnegativity and the prescribed final distribution ensure that no labeled mass remains outside the final support.
The resulting matrix therefore satisfies the row totals, column totals, and reachability restrictions. No assumption about unsplit mass is used.
The packet argument correctly realizes any admissible rational matrix. The row equations permit the initial packet allocation. During sequential processing, the packet being moved remains present at its current location, so its size never exceeds the actual source mass.
Sharing a configuration with other packets causes no difficulty: packet labels are bookkeeping, and the aggregate transfer is a permitted operation. Each positive matrix entry uses a finite path, and there are finitely many entries. Zero-length paths require no operation.
The column equations give the exact final distribution. Since transfers affect only one type, restricting sequences proves necessity type by type, and concatenating the individual sequences proves sufficiency.
The network correctly uses separate copies of initial and final support vertices. This handles coinciding configurations and zero-length reachability.
A flow of value \(\mu_t\) saturates every source and sink arc because each respective group has total capacity \(\mu_t\). The middle flows then satisfy precisely the transport equations. Conversely, every admissible matrix gives such a flow.
Middle capacities of \(\mu_t\) impose no additional restriction: every nonnegative matrix entry is bounded by its row sum, which is at most \(\mu_t\).
The denominator scaling is also valid. The product of all input denominators has binary length \(O(L)\). Scaling the capacities produces integers of polynomial bit length, and an integral maximum-flow computation supplies rational flows after rescaling. Combining duplicate entries does not invalidate this common denominator.
Disjoint component atom sets make an \(n_t\)-bit membership vector sufficient to encode a configuration. There are at most \(2^{n_t}\) configurations, and \(n_t\le L\).
The polynomial-time answer-set verification property cited for the specified component-program class supports the vertex and edge checks. Comparing rule degrees also takes polynomial time: formulas are explicitly represented, and binary weight arithmetic has polynomial bit length.
The simple-path bound is correct. Whenever reachability holds, deleting repeated-vertex portions yields a path of length below \(2^{n_t}\).
The recurrence for \(R_k\) correctly handles paths of length *at most* \(2^k\). A shorter path can be split with a zero-length portion, which the equality case permits. Candidate intermediate vectors are checked for vertex validity.
Depth-first evaluation has depth \(n_t\), with polynomial storage per frame. The stated deterministic time bound \(2^{O(n_t^2)}\operatorname{poly}(m,L)\) follows from at most \(2^{n_t}\) candidates and two recursive evaluations per candidate.
The number of endpoint reachability questions satisfies
\[
\sum_t p_tq_t\le s^2.
\]
The stored relations and flow networks have polynomial size. The Edmonds–Karp arithmetic bound and the inequality \(\sum_t s_t^5\le s^5\) are valid, with polynomial bit cost per operation.
The reported overall time bound is therefore a valid upper bound, and the space bound is polynomial in \(m,\tau,s,L\). Together with the reduction, this establishes \(\mathrm{PSPACE}\)-completeness.
No additional clarification or mathematical repair is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.