Answer: Polynomial-time solvable.
Proposition 4.10 — class: other
Given a finite market-state model, rational masses μ_t summing to \(1\), and each supported account type \(t\)’s asset blocks and proposed structure-preserving edit encoded by rational multiplicative factors, compute \(q_{t,\min}^{\mathrm{post}}=\min_v q_t^{\mathrm{post}}(v)\), where \(q_t(v)=\exp(a_t(v)/b)\). Decide for each type whether \(q_{t,\min}^{\mathrm{post}}\ge 1\), equivalently whether its post-edit minimum cash \(b\ln q_{t,\min}^{\mathrm{post}}\) is nonnegative, and report the eligible mass \(\sum_t \mu_t\mathbf{1}[q_{t,\min}^{\mathrm{post}}\ge 1]\). Treat this as a snapshot audit against the current market distribution: do not pool accounts or assume their proposed edits are committed together.
Let \(V=(V_1,\ldots,V_m)\) have explicitly listed, finite nonempty domains, and let \(\Omega\) be their Cartesian product. The current market distribution \(p\) is given by a junction tree with explicitly tabulated, consistent, strictly positive binary-rational cluster and separator marginals. Let \(b>0\) be a binary-rational liquidity parameter.
A society is given by its support: the list of the \(\tau\) account types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Type \(t\) has \(k_t\ge1\) asset blocks with scopes \(S_{ti}\) and explicitly tabulated positive binary-rational factors \(f_{ti}\). Each scope lies in a market junction-tree cluster, and no distinct block scope is contained in another. Empty scopes may encode constant cash.
Define \(\delta_{ti}(v_{S_{ti}})=b\ln f_{ti}(v_{S_{ti}})\), \(a_t(v)=\sum_i\delta_{ti}(v_{S_{ti}})\), and \(q_t(v)=\exp(a_t(v)/b)=\prod_i f_{ti}(v_{S_{ti}})\). Current accounts are promised solvent: \(q_t(v)\ge1\) for every \(v\in\Omega\); individual block cash values may have either sign.
A proposed structure-preserving edit is an explicitly tabulated positive binary-rational factor \(r_t\) on a scope \(Y_t\) contained in one market cluster, promised to satisfy \(\sum_{v\in\Omega}p(v)r_t(v_{Y_t})=1\). Its proposed distribution is \(x_t(v)=p(v)r_t(v_{Y_t})\), and its post-edit assets satisfy \(q_t^{\mathrm{post}}(v)=q_t(v)r_t(v_{Y_t})\).
Compute exactly \(q_{t,\min}^{\mathrm{post}}=\min_{v\in\Omega}q_t^{\mathrm{post}}(v)\) for every supported type, decide whether each value is at least \(1\), and report \(\sum_t\mu_t\mathbf1[q_{t,\min}^{\mathrm{post}}\ge1]\). This tests nonnegative minimum cash \(b\ln q_{t,\min}^{\mathrm{post}}\). Audit every proposal separately against the same current distribution; accounts are not pooled and edits are not jointly committed.
Let \(L\) be the total input bit length, \(d\) the largest variable-domain size, and \(K=\sum_t k_t\). State running times in \(m,\tau,L,d,K\).
Is this exact snapshot-audit problem solvable in polynomial time, or is it NP-hard?
For discrete accounts, the global-separator identity expresses minimum cash as the minimum, over assignments to variables shared by blocks, of the sum of compatible block minima; junction-tree cash algorithms also have bounds exponential in cluster size ([Laskey et al., 2018](https://www.jair.org/index.php/jair/article/download/11249/26447/20854)).
No result specifically classifying this rational-mass snapshot audit was located.
The exact snapshot-audit problem is polynomial-time solvable. The decisive hypotheses are that every asset factor and proposed edit fits a cluster of a supplied junction tree, and that every market-cluster table is explicitly listed.
Minimum-product message passing computes each requested minimum using exact rational arithmetic. A conservative total bit-operation bound is \(O((K+\tau)L^3+\tau L^4)\). This bound includes processing all supported types and computing the final rational mass.
Let the supplied junction tree have node set \(\mathcal C\), with cluster \(C_c\) at node \(c\). Its running-intersection property states that, for every variable, the nodes whose clusters contain that variable form a connected subtree.
Write \(\Omega_A\) for the assignments to a variable set \(A\). Define
\(D_c=|\Omega_{C_c}|=\prod_{j\in C_c}|\operatorname{Dom}(V_j)|,\qquad n=|\mathcal C|,\qquad N=\sum_{c\in\mathcal C}D_c.\)
Fix a supported type \(t\). Assign every factor \(f_{ti}\) to one cluster containing its scope, and assign \(r_t\) to one cluster containing \(Y_t\). Such assignments exist by hypothesis. Assign each factor exactly once.
For \(z\in\Omega_{C_c}\), let \(F_{t,c}(z)\) be the product of the factors assigned to node \(c\), evaluated at the appropriate restrictions of \(z\). An empty product equals \(1\). Thus
\(\prod_{c\in\mathcal C}F_{t,c}(v_{C_c})=\left(\prod_{i=1}^{k_t}f_{ti}(v_{S_{ti}})\right)r_t(v_{Y_t})=q_t^{\mathrm{post}}(v).\)
All these factors are positive. Empty scopes cause no difficulty: their factors are constants assigned to any cluster.
Root the junction tree at a node \(\rho\). For a nonroot node \(c\), let \(\pi(c)\) be its parent and set \(H_c=C_c\cap C_{\pi(c)}\).
Process nodes from leaves toward the root. For every \(s\in\Omega_{H_c}\), compute
\(M_{t,c}(s)=\min_{\substack{z\in\Omega_{C_c}\\z_{H_c}=s}}\left[F_{t,c}(z)\prod_{h\in\operatorname{child}(c)}M_{t,h}(z_{H_h})\right].\)
At the root, return
\(Q_t=\min_{z\in\Omega_{C_\rho}}\left[F_{t,\rho}(z)\prod_{h\in\operatorname{child}(\rho)}M_{t,h}(z_{H_h})\right].\)
These formulas require only multiplication and comparison of positive rationals. In particular, they do not require computing logarithms.
For a node \(c\), let \(\mathcal T_c\) be its rooted subtree and let \(U_c=\bigcup_{a\in\mathcal T_c}C_a\). We prove that every nonroot message satisfies
\(M_{t,c}(s)=\min_{\substack{u\in\Omega_{U_c}\\u_{H_c}=s}}\prod_{a\in\mathcal T_c}F_{t,a}(u_{C_a}).\)
First, running intersection gives the separation facts needed for this identity.
If a variable occurs in a cluster in \(\mathcal T_c\) and in a cluster outside \(\mathcal T_c\), the path between those clusters crosses the edge joining \(c\) to \(\pi(c)\). Running intersection therefore puts that variable in both endpoint clusters, hence in \(H_c\). Conversely, every variable in \(H_c\) occurs on both sides of that edge.
Consequently, for any child \(h\) of \(c\),
\(U_h\cap C_c=H_h.\)
Also, if a variable occurs in two distinct child subtrees, their connecting path passes through \(c\); thus that variable belongs to \(C_c\).
Now fix \(z\in\Omega_{C_c}\). Once \(z\) is fixed, assignments to distinct child subtrees have no remaining compatibility constraints between them. Indeed, every variable shared by two child subtrees lies in \(C_c\), and both assignments must agree with \(z\) there. Conversely, compatible child assignments and \(z\) combine into an assignment to \(U_c\).
For a leaf, the claimed message identity is exactly the recurrence. For an internal node, assume the identity holds for its children. Conditional on \(z\), each child's minimum is attained because its assignment space is finite and nonempty. The minimizing child assignments can be combined by the compatibility argument above.
Because all factors are positive, the minimum of the product of the independent child contributions is the product of their minima. Hence the conditional minimum for fixed \(z\) is exactly
\(F_{t,c}(z)\prod_{h\in\operatorname{child}(c)}M_{t,h}(z_{H_h}).\)
Minimizing over \(z\) extending \(s\) proves the claimed identity by induction.
At the root, the same argument has no boundary condition. The clusters cover the market variables, so
\(Q_t=\min_{v\in\Omega}\prod_{c\in\mathcal C}F_{t,c}(v_{C_c})=q_{t,\min}^{\mathrm{post}}.\)
This proves exactness.
For type \(t\), constructing the local products uses at most \(O((k_t+1)N)\) rational multiplications.
Computing all messages examines each cluster assignment once. For each assignment it multiplies one incoming value per child, then compares the resulting candidate with the current minimum for its separator assignment. The number of these operations is
\(O\left(N+\sum_{c\in\mathcal C}D_c|\operatorname{child}(c)|\right)=O(nN).\)
Therefore all supported types require
\(O((K+\tau)N+\tau nN)\)
rational operations, together with table indexing and scope processing.
Every cluster marginal is explicitly tabulated, so \(N=O(L)\) and \(n=O(L)\). The total is consequently
\(O((K+\tau)L+\tau L^2)\)
rational operations.
Write each input rational as a positive integer numerator divided by a positive integer denominator, both encoded in binary.
Every local product, message candidate, and selected message value is a product of entries from distinct original factors. No original factor is used twice: factors are assigned once, and different child subtrees contain disjoint sets of assigned factors.
Thus, even without cancelling common divisors, the numerator and denominator of every intermediate product have \(O(L)\) bits. Taking a minimum merely selects one candidate and does not increase its representation length.
Multiplication and comparison of such rationals take \(O(L^2)\) bit operations using elementary integer arithmetic. For comparison, cross-multiplication produces integers with \(O(L)\) bits.
Scope containment and table indexing are polynomial as well. Explicit domains imply \(m,d=O(L)\); each projection can be computed using polynomially bounded indices. The resulting conservative overall bound is
\(\boxed{O((K+\tau)L^3+\tau L^4)\text{ bit operations}.}\)
If reduced output fractions are required, applying the Euclidean algorithm to the returned fractions remains within this bound.
The domain parameter enters through \(D_c\le d^{|C_c|}\le d^m\). However, these \(D_c\) entries are already present in the input, and their sum is \(O(L)\). Therefore this algorithm incurs no additional \(d^m\) enumeration. Since \(K,\tau=O(L)\), the displayed bound is polynomial in the total input length.
For each type, write the computed minimum as \(Q_t=A_t/B_t\), with positive integer numerator and denominator. Then
\(q_{t,\min}^{\mathrm{post}}\ge1\quad\Longleftrightarrow\quad A_t\ge B_t.\)
This is an exact integer comparison.
Because \(b>0\) and the logarithm is strictly increasing,
\(\min_{v\in\Omega}b\ln q_t^{\mathrm{post}}(v)=b\ln Q_t,\)
and this minimum cash is nonnegative exactly when \(Q_t\ge1\).
Finally, compute the requested output
\(W=\sum_{t:Q_t\ge1}\mu_t.\)
This rational sum is also polynomial-time computable. For example, use the product of the selected masses' denominators as a common denominator. Its bit length is at most the sum of their input denominator lengths, hence \(O(L)\). Since the selected masses sum to at most \(1\), the resulting numerator has \(O(L)\) bits too.
Every computation uses only the current factors and that type's own proposal. Thus it implements the stipulated separate audits.
Laskey et al. describe both global-separator enumeration and one-way junction-tree minimum propagation; they also explain why global-separator enumeration can become expensive. [Laskey et al., 2018, Sections 4.4–4.5](https://www.jair.org/index.php/jair/article/download/11249/26447/20854).
A large global separator need not make this input representation difficult. For example, with binary variables and block scopes \(\{V_i,V_{i+1}\}\), the global separator contains the \(m-2\) internal variables. Enumerating its assignments examines \(2^{m-2}\) possibilities, whereas the path junction tree has only \(4(m-1)\) cluster entries.
More generally, exponential dependence on cluster cardinality is compatible with polynomial time in an input that explicitly lists every cluster entry. Here the supplied tree already accommodates every asset and edit scope. The proof above establishes the polynomial classification directly, including exact rational arithmetic.
⟨structured verdict parsed — rendered above⟩
The prover’s polynomial-time claim is correct for the stated input representation. The message recurrence is justified, intermediate rational values have polynomial bit length, and the algorithm computes all requested outputs. No major or minor issues were found.
The output addresses every required component:
The proof uses the supplied junction tree and explicitly listed cluster tables. These are substantive hypotheses of USER_TASK, so using them does not narrow the assigned problem.
Every asset factor and proposal has a scope contained in a supplied cluster. Therefore the stated assignment of each factor to exactly one containing cluster exists.
For any complete assignment \(v\), multiplying the local products includes each asset factor and the proposal exactly once. Hence the identity
\(\prod_c F_{t,c}(v_{C_c})=q_t^{\mathrm{post}}(v)\)
is correct.
Empty scopes represent constants and can be assigned to any cluster. Nodes without assigned factors correctly receive local product \(1\). Neither overlapping scopes nor repeated scopes invalidate this construction.
The condition forbidding strict containment between distinct block scopes is not needed by this algorithm. Proving correctness without using that restriction is valid.
The running-intersection argument is correct. A variable appearing on both sides of a tree edge must occur in both endpoint clusters, so the intersection of the variable sets on the two sides is precisely the edge separator.
For a child \(h\) of \(c\), this establishes
\(U_h\cap C_c=H_h\).
A variable appearing in two different child subtrees must also occur in \(C_c\).
Consequently, once an assignment \(z\) to \(C_c\) is fixed, assignments in different child subtrees have no unresolved compatibility constraints. Each child assignment agrees with \(z\) on every variable it shares with \(C_c\), and any variable shared between child subtrees is already fixed by \(z\).
The claimed combination of compatible assignments is therefore justified.
The induction invariant states exactly what each separator-conditioned message represents.
The leaf case agrees directly with the recurrence. At an internal node, every separator assignment has extensions because the domains are nonempty Cartesian-product domains. The relevant assignment spaces are finite, so every child minimum is attained.
For fixed \(z\), the child choices can be combined independently. Their contributions and the local factor are positive. Therefore multiplying their attained minima gives the conditional minimum product. Positivity is essential here and is supplied explicitly by the task.
Minimizing over cluster assignments extending the boundary assignment proves the invariant. At the root, the supplied market junction tree covers the variables, so the returned value is exactly
\(Q_t=q_{t,\min}^{\mathrm{post}}\).
This is a self-contained correctness proof; it does not rely on an unstated external message-passing theorem.
The local-product count \(O((k_t+1)N)\) is a valid upper bound: each assigned factor is evaluated over its containing cluster’s assignments.
For message computation, each cluster assignment contributes one multiplication per child and a comparison for its separator entry. Thus
\(O(N+\sum_c D_c|\operatorname{child}(c)|)=O(nN)\)
is a valid conservative bound.
Summing over supported types gives
\(O((K+\tau)N+\tau nN)\)
rational operations.
Because every cluster marginal is explicitly tabulated, every cluster contributes at least one encoded entry, and each entry occupies input bits. Thus \(N=O(L)\) and \(n=O(L)\), as claimed. The resulting bound
\(O((K+\tau)L+\tau L^2)\)
on rational operations follows.
The crucial representation-length claim is justified.
Every stored local product, candidate, or message value can be represented as a product containing at most one entry from each original factor involved in that subtree. Different child subtrees contain disjoint sets of assigned factors. Selecting a minimum selects an existing candidate rather than combining competing candidates.
Accordingly, the total numerator and denominator bit lengths are bounded by the sum of the relevant input entry lengths, which is \(O(L)\). Cancellation is unnecessary.
Elementary integer multiplication and rational comparison therefore cost \(O(L^2)\) bit operations. Cross-products used for comparison still have \(O(L)\) bits.
The stated conservative bound
\(O((K+\tau)L^3+\tau L^4)\)
is valid. Routine scope containment, assignment projection, and table access can be implemented within this allowance. Fraction reduction and the final mass computation also fit within it.
The requested parameters are adequately accounted for: explicitly listed domains give \(m,d=O(L)\), and the proof explains that cluster assignment counts are already charged to the input length. Its runtime bound need not contain an additional explicit factor in \(m\) or \(d\).
For positive numerator and denominator, comparing \(Q_t=A_t/B_t\) with \(1\) is exactly the integer comparison \(A_t\ge B_t\).
Since \(b>0\) and the logarithm is strictly increasing, the minimum cash equals \(b\ln Q_t\), and its sign is determined exactly by whether \(Q_t\ge1\). No logarithmic approximation is needed.
The mass calculation is also justified. The product of selected denominators has \(O(L)\) bits. Because the selected positive masses sum to at most \(1\), the corresponding numerator has \(O(L)\) bits. The empty selection gives mass \(0\).
Each type is processed using only its own factors and proposal. Thus the computation respects separate audits and does not pool accounts or jointly apply edits.
The current-solvency and proposal-normalization conditions are promises. The task does not require validating them, so their absence from the computation is not a gap.
The cited paper does discuss global-separator enumeration in Section 4.4 and one-way minimum propagation in Section 4.5. The prover’s descriptive attribution is accurate. [Laskey et al., 2018](https://www.jair.org/index.php/jair/article/download/11249/26447/20854).
The binary path example correctly has \(m-2\) shared internal variables and \(4(m-1)\) cluster entries for \(m\ge2\). It illustrates the difference between enumerating the global separator and processing the supplied cluster tables.
The polynomial classification follows from the prover’s own argument, independently of that citation. Exponential dependence on cluster size does not contradict polynomial dependence on an input that explicitly contains every cluster entry.
No repair or additional clarification 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.