Answer: Polynomial-time solvable (\(\mathrm{P}\)), even for arbitrary finite undirected role graphs.
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateReachable Object is NP-complete even when the network is a tree. Sketch of proof: One can easily verify that the prob- lem is in NP. We use a reduction from the NP-complete problem 2P1N-SAT [Yoshinaka, 2005]. In 2P1N-SAT, we are given a set V = {v1, . . . , vn} of variables, and a collection C = {C1, . . . , Cm} of clauses over V such that each positive (resp., negative) literal occurs exactly 2 (resp., 1) times in C. Is C satisfiable? Let vi k (resp., vi k) denote the positive (resp., negative) literal vk if present in Ci.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Input a finite cohort-role tree \(H\), finite agent and object types \(A\) and \(X\), rational masses \(\mu_a\), strict preferences \(\succ_a\), initial object categories \(e(a)\), a target type \(a^\star\), target object category \(x^\star\), and rational \(\eta>0\). Starting from \(z^0\), where \(z_{a,x}\) is the mass of type \(a\) holding \(x\), may a finite sequence of aggregate swaps across edges of \(H\), each moving a nonnegative rational mass \(\delta\) between mutually improving types while conserving object mass, reach a state with \(z_{a^\star,x^\star}\ge\eta\)?
A society is given by its support: a list \(A\) of \(\tau\) types with positive binary-rational masses \(\mu_a\), normalized by \(\sum_{a\in A}\mu_a=1\). Here \(\tau\) is the support size, not the number of possible types.
Input also consists of a finite undirected role tree \(H=(V,E)\), a role map \(r:A\to V\), a nonempty set \(X\) of \(m\) object categories, a strict linear order \(\succ_a\) over \(X\) for each type, and an initial category \(e(a)\in X\). Every category has positive initial supply; copies within a category are interchangeable.
A state is a nonnegative rational matrix \(z\), with \(z_{a,x}\) the mass of type \(a\) holding category \(x\). Initially \(z^0_{a,e(a)}=\mu_a\) and all other entries vanish. States preserve \(\sum_x z_{a,x}=\mu_a\) and \(\sum_a z_{a,x}=\sum_{a:e(a)=x}\mu_a\).
A swap selects types \(a,b\) with \(\{r(a),r(b)\}\in E\), categories \(x,y\) satisfying \(y\succ_a x\) and \(x\succ_b y\), and rational \(0<\delta\le\min\{z_{a,x},z_{b,y}\}\). It subtracts \(\delta\) from \(z_{a,x},z_{b,y}\) and adds \(\delta\) to \(z_{a,y},z_{b,x}\), leaving everything else fixed. There are no payments or other moves.
Given \(a^\star\in A\), \(x^\star\in X\), and binary-rational \(\eta>0\), continuous object reachability asks whether some finite sequence of swaps, possibly empty, reaches \(z_{a^\star,x^\star}\ge\eta\); limiting states alone do not count. Let \(L\) be the total input bit length; state running times in \(m,\tau,|V|,L\).
Is continuous object reachability on role trees solvable in polynomial time, or is it \(\mathrm{NP}\)-hard?
For individual agents holding distinct indivisible objects, object reachability under mutually improving neighboring swaps is \(\mathrm{NP}\)-complete even on trees, and polynomial-time solvable on stars ([source](https://www.ijcai.org/proceedings/2017/0031.pdf)); it is also polynomial-time solvable on paths with strict preferences ([source](https://ojs.aaai.org/index.php/AAAI/article/download/4033/3911)).
No result specifically treating the continuous object-reachability problem defined above was located.
Continuous object reachability is polynomial-time solvable. The argument applies to arbitrary finite role graphs, and therefore to role trees.
The essential observation is that swaps are transitions of a rational continuous Petri net. The threshold condition can be reduced to finite exact reachability in such a net.
A rational continuous Petri net consists of finite sets of places \(P\) and transitions \(T\), together with nonnegative integer matrices \(\mathrm{Pre},\mathrm{Post}\), indexed by \(P\times T\).
A marking is a vector \(h\in\mathbb{Q}_{\ge 0}^{P}\). A transition \(t\) can fire by a rational amount \(\delta>0\) when
\(h_p\ge\delta\,\mathrm{Pre}_{p,t}\quad\text{for every }p\in P.\)
The resulting marking is
\(h'=h+\delta(\mathrm{Post}_{\cdot,t}-\mathrm{Pre}_{\cdot,t}).\)
We use the following established result:
Finite rational reachability theorem. Given such a net and binary-encoded rational markings \(h^0,h^{\mathrm{tar}}\), deciding whether a finite sequence of rational firings reaches \(h^{\mathrm{tar}}\) from \(h^0\) takes polynomial time in their total encoding length.
This is the rational reachability result stated in Proposition 2.4 of [Blondin, Finkel, Haase, and Haddad, *The Logical View on Continuous Petri Nets*](https://www.cs.ox.ac.uk/people/christoph.haase/home/publication/bfhh-17/bfhh-17.pdf). Its Section 2.3 explicitly defines rational markings, rational firing amounts, and reachability by finite sequences. The underlying polynomial algorithm is Algorithm 2 and Proposition 27 of [Fraca and Haddad, *Complexity Analysis of Continuous Petri Nets*](https://lsv.ens-paris-saclay.fr/Publis/PAPERS/PDF/FH-fundi15.pdf).
Thus the theorem concerns precisely finite reachability, including targets on the boundary of the nonnegative orthant.
Create one place \(p_{a,x}\) for every \(a\in A\) and \(x\in X\). Identify a marking with the matrix of holdings:
\(h_{p_{a,x}}=z_{a,x}.\)
Set \(h^0_{p_{a,e(a)}}=\mu_a\), with all other coordinates zero.
For each admissible swap involving types \(a,b\) and categories \(x,y\), introduce a transition whose inputs are
\(p_{a,x},\ p_{b,y}\)
and whose outputs are
\(p_{a,y},\ p_{b,x},\)
each with coefficient one. Introduce this transition exactly when
\(\{r(a),r(b)\}\in E,\qquad y\succ_a x,\qquad x\succ_b y.\)
Because the role graph has no loops and preferences are strict, \(a\ne b\) and \(x\ne y\). Consequently, these four places are distinct.
Firing this transition by \(\delta>0\) is enabled exactly when
\(\delta\le\min\{z_{a,x},z_{b,y}\},\)
and its effect is exactly the prescribed swap. Therefore finite rational firing sequences correspond to finite legal swap sequences.
Each transition preserves every type’s total mass and every category’s total supply: it removes and adds equal amounts within each participating type and category. Hence all markings reachable using these transitions satisfy the required conservation equations.
Define the target marking \(q\) by
\(q_{p_{a^\star,x^\star}}=\eta,\qquad q_p=0\quad\text{for all other places }p.\)
The desired condition is that some swap-reachable marking \(h\) satisfies \(h\ge q\), where the inequality is coordinatewise.
For each place \(p\), add an auxiliary discard transition \(d_p\). Its only input is one unit at \(p\), and it has no outputs. Firing it by \(\delta\) removes \(\delta\) from that coordinate.
These transitions belong only to the decision reduction. They are not additional society moves.
Lemma. A finite legal swap sequence reaches a state satisfying the threshold if and only if the augmented net reaches \(q\) by a finite rational firing sequence.
Proof, forward direction. Suppose swaps reach \(h\ge q\). At each place \(p\) with \(h_p>q_p\), fire \(d_p\) by the rational amount \(h_p-q_p\). This is enabled because
\(0<h_p-q_p\le h_p.\)
After at most \(|P|\) additional firings, the marking is exactly \(q\).
Proof, reverse direction. Suppose a finite augmented execution reaches \(q\). Process its firings in order, replaying each swap with its original amount and omitting each discard.
Let \(w\) denote the augmented marking at a given point, and let \(z\) denote the marking produced by the replay. We prove inductively that the replay is legal and \(z\ge w\).
Initially, \(z=w=h^0\).
If the next firing discards \(\delta\) at place \(p\), the augmented marking decreases by \(\delta\) at that coordinate while the replay marking stays fixed. Thus \(z\ge w\) continues to hold.
If the next firing is a swap transition \(t\) of amount \(\delta\), its legality in the augmented execution gives
\(w_p\ge\delta\,\mathrm{Pre}_{p,t}\quad\text{for every }p.\)
Since \(z\ge w\), the same firing is enabled in the replay. Both markings receive the same change \(\delta(\mathrm{Post}_{\cdot,t}-\mathrm{Pre}_{\cdot,t})\), so their coordinatewise difference is unchanged.
At the end, the replay is a finite rational sequence consisting entirely of legal swaps, and its final marking satisfies \(z\ge q\). In particular,
\(z_{a^\star,x^\star}\ge\eta.\)
This proves the lemma.
The algorithm constructs the augmented net and applies the finite rational reachability theorem to \(h^0\) and \(q\). The lemma proves both directions of correctness.
Let \(n_P\) and \(n_T\) be the augmented net’s numbers of places and transitions. Then
\(n_P=\tau m.\)
For each unordered pair of types and unordered pair of distinct categories, there is at most one admissible swap direction: the opposite direction would contradict strict preferences. Adding the discard transitions therefore gives
\(n_T\le\binom{\tau}{2}\binom{m}{2}+\tau m =O(\tau^2m^2+\tau m).\)
Preference comparisons can be implemented using rank tables. Enumerating candidate swaps takes polynomial time, with \(O(\tau^2m^2)\) candidates. Role adjacency can also be checked in polynomial time from the given tree.
All incidence entries are zero or one. Even using dense incidence matrices, the augmented reachability instance has encoding length
\(B=O\!\left(L+n_Pn_T\right) =O\!\left(L+(\tau m)^3\right).\)
The initial and target markings add only \(O(L+\tau m)\) bits: they use the input masses, \(\eta\), and zeros. No normalization or expansion into individual agents is needed.
Consequently, the complete decision algorithm runs in
\(\operatorname{poly}\!\left(|V|+L+(\tau m)^3\right),\)
and hence in \(\operatorname{poly}(m,\tau,|V|,L)\).
The construction uses only the listed \(\tau\) support types. It does not enumerate other possible types or expand binary-encoded masses into discrete copies.
The target question is settled: continuous object reachability on role trees belongs to \(\mathrm{P}\). The proof also establishes the same upper bound for arbitrary finite undirected role graphs.
Finite rational executions are preserved in both directions of the reduction. Thus equality at the threshold is handled exactly; a state obtainable only as a limit does not supply a witness.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes polynomial-time decidability of the stated continuous object-reachability problem. The cited theorem applies to finite rational executions, the swap encoding is exact, and the threshold reduction is valid in both directions. I found no major or minor issues requiring repair.
The theorem is stated with the necessary hypotheses: finite place and transition sets, nonnegative integer incidence matrices, and binary-encoded nonnegative rational initial and target markings.
The cited source supports precisely this statement:
There is no restriction requiring strictly positive target coordinates, conservativity, or a particular graph structure. Thus boundary targets and auxiliary discard transitions are permitted. [Blondin, Finkel, Haase, and Haddad, Sections 2.1–2.3](https://www.cs.ox.ac.uk/people/christoph.haase/home/publication/bfhh-17/bfhh-17.pdf)
The underlying reference also matches the output’s attribution: Algorithm 2 decides reachability; Proposition 26 establishes its correctness; Proposition 27 establishes polynomial running time. It explicitly distinguishes reachability from limit reachability. [Fraca and Haddad, Algorithm 2 and Propositions 26–27](https://lsv.ens-paris-saclay.fr/Publis/PAPERS/PDF/FH-fundi15.pdf)
The first source permits zero-amount firings. This does not cause a mismatch: such firings leave the marking unchanged and can be removed from any finite execution.
Assessment: The external theorem is accurately stated and its hypotheses are satisfied.
The place set has exactly one coordinate for each holding entry, so it has size \(\tau m\). The initial marking agrees exactly with the specified initial state.
For each admissible swap:
\(\delta\le\min\{z_{a,x},z_{b,y}\}\).
Thus every positive rational firing of a swap transition is a legal society swap, and every legal society swap has a corresponding transition firing.
The conservation claim is also correct. Each participating type loses and gains the same amount, and each participating category loses and gains the same amount. Nonnegativity follows from the enabling condition. These properties hold after every finite sequence.
Assessment: The encoding is exact and preserves all required state constraints.
The target marking \(q\) is nonnegative and rational. Since every other coordinate is zero, \(h\ge q\) is exactly the requested threshold condition for a nonnegative marking \(h\).
If swaps reach \(h\ge q\), each positive surplus \(h_p-q_p\) is rational and no greater than the available holding \(h_p\). Its discard is therefore enabled.
Discarding one coordinate does not change another coordinate, so all listed discards remain legal. At most \(\tau m\) firings reach \(q\) exactly.
The replay invariant \(z\ge w\) is correctly proved:
This checks legality at every replay step, rather than merely comparing final markings. At termination, \(z\ge q\), so the replay reaches the required threshold using only legal swaps.
The replay remains finite and uses the original rational firing amounts. Its conservation properties follow from the swap encoding.
Assessment: The equivalence is fully proved. Interleaved discards do not create false positive answers.
The transition count is valid. For fixed unordered pairs of distinct types and distinct categories, the two possible exchange orientations cannot both improve both types: they would require contradictory strict comparisons. Therefore,
\[
n_T\le\binom{\tau}{2}\binom{m}{2}+\tau m.
\]
Rank tables permit preference comparisons in constant time after polynomial preprocessing. Enumerating candidate swaps and checking role adjacency takes polynomial time.
With dense incidence matrices, their entries require
\(O(n_Pn_T)\) bits, since all entries are zero or one. The initial and target markings require \(O(L+\tau m)\) bits. Hence the stated bound
\(B=O(L+(\tau m)^3)\) is valid.
Applying the verified reachability theorem to this polynomial-size instance gives the claimed running time
\(\operatorname{poly}(m,\tau,|V|,L)\).
Assessment: The reduction respects binary encoding and support size. It does not implicitly expand masses into individual agents.
The written argument also handles the relevant edge cases:
The proof does not use acyclicity. Its extension to arbitrary finite loopless undirected role graphs is therefore justified.
No additional clarification or 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.