Answer: \(\mathrm{P}\). Every accepted family has a successful ordering constructible in time polynomial in \(m,\tau,L,d,N(k)\) and the bit length of \(k\).
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet F be a family of graphs.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a fixed finite set of network roles \(T\), a fixed signal accuracy \(q\), a role-incidence rule generating graphs \(G_N\), and rational role distributions \(\mu^{(N)}\) with \(N\mu_t^{(N)}\in\mathbb{Z}_{\ge 0}\), determine whether there is an ordering family \(\sigma_N\) for which Bayesian network learning quality \(L_{\sigma_N}(G_N)\to 1\), and construct such a family when it exists. In particular, characterize the hub-and-seed regime with a hub \(v_N\), an independent neighbor set \(S_N\), \(|S_N|\to\infty\), \(|S_N|/N\to0\), and a component containing all but \(o(N)\) agents after removing \(S_N\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types.
A family has a finite role set \(T\), with \(m=|T|\), and a symmetric matrix \(A\in\{0,1\}^{T\times T}\). Distinct agents of roles \(t,u\) are adjacent exactly when \(A_{tu}=1\); diagonal entries specify whether a role induces a clique or an independent set.
Specify population growth by densely encoded polynomials \(p_t(k)\) with nonnegative integer coefficients, allowing zero polynomials, with \(N(k)=\sum_t p_t(k)\to\infty\). At integer scale \(k\geq1\), role \(t\) has \(p_t(k)\) agents and mass \(\mu_t^{(k)}=p_t(k)/N(k)\); write the resulting simple undirected graph as \(G_k\). Roles and incidence remain fixed as \(k\) grows, but vary between inputs.
Fix a rational \(q\in(1/2,1)\). The state \(\theta\) is uniform on \(\{0,1\}\); conditional on it, private binary signals are independent and satisfy \(\Pr(s_v=\theta\mid\theta)=q\). An ordering is a permutation chosen before signals are realized. Each agent knows the graph, ordering, and signal model, observes its own signal and earlier neighbors' actions, and announces a posterior-maximizing binary action, breaking ties with an independent fair coin.
Define \(L_{\sigma_k}(G_k)=N(k)^{-1}\sum_v\Pr(a_v=\theta)\). The hub-and-seed regime means there exist \(v_k\) and an independent set \(S_k\subseteq N_{G_k}(v_k)\) with \(|S_k|\to\infty\), \(|S_k|/N(k)\to0\), and the component of \(v_k\) in \(G_k-S_k\) omitting only \(o(N(k))\) remaining agents; this is a subclass, not an input promise.
Let \(L\) be the total bit length of the family description and \(d=\max_t\deg p_t\). State decision running times in \(m,\tau,L,d\), and ordering-construction running times additionally in \(N(k)\) and the bit length of \(k\).
Is deciding whether there exists an ordering family \((\sigma_k)\) with \(L_{\sigma_k}(G_k)\to1\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? When such a family exists, can it be constructed within the stated running-time parameters?
Known: the hub-and-seed conditions above guarantee a constructible successful ordering for finite graph families. [Lu et al.](https://arxiv.org/html/2410.04317v1)
Finite directed-network Bayesian learning-threshold decision is \(\mathrm{NP}\)-hard, even for fixed signal accuracy in \((\sqrt{7/8},1)\); this concerns a finite accuracy threshold, not the undirected role-mass limit problem. [Úradník et al.](https://arxiv.org/html/2502.12704v1)
No complexity classification for this exact encoded role-mass limit problem was located.
There is a complete structural criterion, and every accepted family admits a successful ordering constructible in time polynomial in the description parameters, the bit length of \(k\), and \(N(k)\).
Let
\[
\]
\(U=\{t\in T:p_t\not\equiv0\}\), and let \(R\) be the undirected graph on \(U\) whose edges are the pairs of distinct roles \(t,u\) with \(A_{tu}=1\). Thus diagonal entries do not create edges in \(R\).
Since the coefficients are nonnegative, every role in \(U\) is populated at every integer scale \(k\geq1\). Moreover, \(N(k)\to\infty\) implies \(d\geq1\).
Call a component \(C\) of \(R\) dominant if it contains a role \(t\) with \(\deg p_t=d\).
The criterion is: a successful ordering family exists if and only if every dominant component \(C\) satisfies both conditions:
In words, every role component carrying positive limiting population mass must contain a growing independent role connected to another role.
The substantial converse is an information bound for clique roles, proved next.
Consider any finite graph of the prescribed role form. Suppose it has \(h\) populated clique roles, and its independent roles together contain at most \(b\) agents.
We prove that, for every ordering and every agent \(v\),
\(\Pr(a_v\neq\theta)\geq\delta(q,h,b)>0\),
where the bound is independent of the clique populations.
Throughout this proof, logarithms are natural. Define
\(c_q=\frac12q(1-q)(2q-1)^2>0\)
and
\(D_q=(2q-1)\log\frac{q}{1-q}>0\).
A bound that will suffice is
\(\delta(q,h,b)=\frac14\exp\!\left[-D_q\left(\frac{2h\log2}{c_q}+b\right)\right]\).
Number agents in their decision order. Let \(F_i\) be the vector of earlier neighbors’ actions observed by agent \(i\), and put
\(r_i=\Pr(\theta=1\mid F_i)\).
Conditional on \(\theta\), the current private signal is independent of all earlier actions: those actions depend only on earlier private signals and independent tie coins.
Bayes’ rule therefore gives the following policy at any observation history with social posterior \(r\):
Define \(Z_i=\mathbf1\{1-q\leq r_i\leq q\}\). Thus \(Z_i=1\) precisely at histories where the action’s distribution depends on the fresh signal.
We claim
\(I(\theta;a_i\mid F_i)\geq c_q\,\mathbb E Z_i\).
To verify this, fix a history with \(r\in[1-q,q]\). Write
\(\alpha_s=\Pr(a_i=1\mid F_i,s_i=s)\).
The policy above implies
\(\alpha_1-\alpha_0\geq\frac12\).
If \(b_j=\Pr(a_i=1\mid F_i,\theta=j)\), conditional independence gives
\(b_1-b_0=(2q-1)(\alpha_1-\alpha_0)\).
Put \(\bar b=rb_1+(1-r)b_0\). The conditional mutual information at this history is
\(rD(\operatorname{Ber}(b_1)\Vert\operatorname{Ber}(\bar b))+(1-r)D(\operatorname{Ber}(b_0)\Vert\operatorname{Ber}(\bar b))\).
The elementary binary relative-entropy inequality
\(D(\operatorname{Ber}(x)\Vert\operatorname{Ber}(y))\geq2(x-y)^2\)
then gives the lower bound
\(2r(1-r)(b_1-b_0)^2\geq\frac12q(1-q)(2q-1)^2=c_q\).
For completeness, the binary inequality follows by differentiating in \(x\): the difference between its two sides has value and derivative zero at \(x=y\), and second derivative
\(\frac1{x(1-x)}-4\geq0\).
Boundary cases follow by continuity. Averaging over histories proves the claim.
Fix a clique role \(t\). Consider the chronological action stream consisting of all agents of role \(t\) and all agents of roles adjacent to \(t\).
Immediately before an agent of role \(t\) acts, the preceding part of this stream is exactly its observed action vector \(F_i\). This uses both defining properties of a role:
By the mutual-information chain rule, the sum of the contributions from agents of role \(t\) is at most the information in the entire stream. All other chain-rule contributions are nonnegative. Consequently,
\(\sum_{i:\,t_i=t}I(\theta;a_i\mid F_i)\leq H(\theta)=\log2\).
Combining this with the preceding bound yields
\(\mathbb E\sum_{i:\,t_i=t}Z_i\leq\frac{\log2}{c_q}\).
The expectation here uses the uniform mixture of the two states. Hence, under \(\theta=1\),
\(\mathbb E_1\sum_{i:\,t_i=t}Z_i\leq\frac{2\log2}{c_q}\).
Summing over clique roles and adding the at most \(b\) independent-role agents gives
\(\mathbb E_1\sum_i Z_i\leq\frac{2h\log2}{c_q}+b\).
Let \(P_1,P_0\) denote the laws of the complete action transcript under the respective states. They have common support: every private-signal assignment and every relevant tie-coin assignment has positive probability under both states.
Fix a complete earlier action history. The current private signal remains independent of that history conditional on the state. The current action is obtained from that signal through a channel determined by its observed subhistory and the tie rule.
If \(Z_i=0\), this channel produces the same deterministic action under both states, contributing zero relative entropy. If \(Z_i=1\), the log-sum inequality, equivalently relative-entropy contraction under a common channel, bounds its contribution by
\(D(\operatorname{Ber}(q)\Vert\operatorname{Ber}(1-q))=D_q\).
The relative-entropy chain rule therefore gives
\(D(P_1\Vert P_0)\leq D_q\,\mathbb E_1\sum_iZ_i\leq K\),
where
\(K=D_q\left(\frac{2h\log2}{c_q}+b\right)\).
Let \(\rho=\sum_x\sqrt{P_1(x)P_0(x)}\). Jensen’s inequality gives
\(\rho=\mathbb E_1\exp\!\left[-\frac12\log\frac{P_1(X)}{P_0(X)}\right]\geq e^{-K/2}\).
Cauchy–Schwarz gives
\(\operatorname{TV}(P_1,P_0)\leq\sqrt{1-\rho^2}\).
Under the uniform prior, the minimum error attainable from the full transcript is therefore at least
\(\frac{1-\operatorname{TV}(P_1,P_0)}2\geq\frac{\rho^2}{4}\geq\frac{e^{-K}}4\).
Every individual action is an estimator available from that transcript. Its error cannot be smaller than the optimal transcript-based error. This proves the claimed uniform obstruction.
For each role, let \(c_{t,d}\) be its coefficient of \(k^d\), possibly zero. For a component \(C\) of \(R\), write
\(n_C(k)=\sum_{t\in C}p_t(k)\).
Nonnegativity of the coefficients gives
\(\frac{n_C(k)}{N(k)}\longrightarrow w_C=\frac{\sum_{t\in C}c_{t,d}}{\sum_{t\in U}c_{t,d}}\).
Thus \(w_C>0\) exactly when \(C\) is dominant.
There are no edges between different role components. Restricting any ordering to one role component leaves its learning process unchanged: agents there observe only actions from that component, and the externally specified ordering carries no state information.
Suppose a dominant component fails the criterion.
First case: it is a singleton independent role. Its agents have no neighbors, so every agent acts on its private signal and has accuracy exactly \(q\). Therefore, for every ordering family,
\(\liminf_{k\to\infty}(1-L_{\sigma_k}(G_k))\geq w_C(1-q)>0\).
Second case: it contains no growing independent role. This includes a singleton clique role. Every independent role in this component has a constant population, because its nonzero polynomial has degree zero. Let \(b_C\) be their total, and let \(h_C\) be the number of clique roles.
The obstruction from Section 1 applies uniformly at every scale and under every ordering. Hence
\(1-L_{\sigma_k}(G_k)\geq\frac{n_C(k)}{N(k)}\delta(q,h_C,b_C)\),
and consequently
\(\liminf_{k\to\infty}(1-L_{\sigma_k}(G_k))\geq w_C\delta(q,h_C,b_C)>0\).
These cases exhaust failures of the criterion. Necessity follows.
Assume every dominant component passes the criterion. We construct its ordering separately.
Fix such a component \(C\). Choose a role \(t\in C\) with \(A_{tt}=0\) and \(\deg p_t\geq1\). Since \(|C|\geq2\), choose a neighboring role \(u\), and choose one agent \(v\) of role \(u\).
At scale \(k\), put
\(b_C(k)=\min\{p_t(k)-1,\lfloor\sqrt{p_t(k)}\rfloor\}\),
and choose \(b_C(k)\) agents of role \(t\) as the seed set \(S_C(k)\).
Then \(b_C(k)\to\infty\), while at least one agent of role \(t\) remains outside the seed set.
Use this order:
For role \(t\), choose its representative outside the seed set.
The seeds are independent and act before any of their neighbors. Their actions equal their private signals.
The hub consequently observes \(b_C(k)\) independent signals, in addition to its own. Its Bayesian action is their majority, with the specified fair tie rule.
Let \(n=b_C(k)+1\), and let \(X\) count correct signals among these \(n\) signals. Conditional on either state, \(X\) is binomial with mean \(nq\) and variance \(nq(1-q)\). A wrong majority, including a possible wrong tie outcome, requires \(X\leq n/2\). Applying Markov’s inequality to \((X-nq)^2\) gives
\(\Pr(a_v\neq\theta)\leq\varepsilon_C(k)=\min\left\{1,\frac{q(1-q)}{(b_C(k)+1)(q-\frac12)^2}\right\}\to0\).
If an agent observes an earlier neighbor’s action, copying that action is a feasible decision rule. Posterior maximization therefore implies
\(\Pr(a_x=\theta)\geq\Pr(a_y=\theta)\)
whenever \(y\) is an earlier neighbor of \(x\). This argument requires no independence between the observed actions.
Every nonroot representative observes its parent representative. Induction along the spanning tree shows that every representative has error at most \(\varepsilon_C(k)\).
Every role in the nontrivial connected graph \(R[C]\) has a neighboring role. Once all representatives have acted, every remaining agent observes a representative of such a neighboring role. It too has error at most \(\varepsilon_C(k)\).
This is a componentwise form of the seed aggregation and propagation construction in [Lu et al., Theorem 3](https://arxiv.org/html/2410.04317v1).
Concatenate these orders over dominant components, and append all nondominant components in any order. Let \(n_{\mathrm{ign}}(k)\) be the total population of the latter.
The construction gives
\(1-L_{\sigma_k}(G_k)\leq\frac{n_{\mathrm{ign}}(k)}{N(k)}+\sum_{C\text{ dominant}}\left(\frac{b_C(k)}{N(k)}+\frac{n_C(k)}{N(k)}\varepsilon_C(k)\right)\).
Every term tends to zero:
Therefore \(L_{\sigma_k}(G_k)\to1\), proving sufficiency.
The decision algorithm scans the dense polynomials to find their supports and degrees, computes components of \(R\), and checks the criterion. It never enumerates an ambient universe of possible types; only the encoded support is relevant.
A conservative bit-operation bound, displaying the requested parameters, is
\(\widetilde O(L+m^2+m(d+1)+\tau)\),
where the tilde suppresses logarithmic factors. In particular, the decision problem is in \(\mathrm{P}\).
For an explicit ordering at scale \(k\), label agents by their role and their index within that role. Let \(\ell(k)\) be the bit length of \(k\), and set
\(R_0=L+m^2+m(d+1)+\tau+1\)
and
\(B_k=L+(d+1)\ell(k)+\left\lceil\log_2((m+\tau+1)(d+1)+1)\right\rceil+3\).
This bounds the bit lengths of the evaluated populations, \(N(k)\), and the required indices. Using schoolbook arithmetic:
Thus a valid construction bound is
\(O(R_0B_k^2+mB_k^3+N(k)B_k)\).
This constructs the ordering itself; it requires no computation of agents’ Bayesian posteriors.
The criterion covers families outside the single hub-and-seed regime. For example, two disjoint stars, each with one hub and \(k\) leaves, satisfy it and learn componentwise. They fail the stated global hub condition because every hub’s component omits approximately half the population.
The [finite directed-network threshold hardness result](https://arxiv.org/html/2502.12704v1) concerns a different decision problem. Here the uniform error obstruction, together with the fixed role structure across scales, yields the polynomial-time criterion proved above.
⟨structured verdict parsed — rendered above⟩
The output proves the claimed polynomial-time criterion and provides a valid ordering construction within the requested parameters. I found no mathematical gaps or incorrect steps.
Nonnegative coefficients ensure that every nonzero polynomial is positive at every integer scale \(k\geq1\). Thus the populated role set \(U\) is fixed across scales. The assumption \(N(k)\to\infty\) ensures that the maximum degree satisfies \(d\geq1\).
The role graph \(R\) correctly excludes diagonal entries: these govern adjacency within a role, rather than connectivity between distinct roles.
The limiting component weight
\[
w_C=\frac{\sum_{t\in C}c_{t,d}}{\sum_{t\in U}c_{t,d}}
\]
is correct. Its denominator is positive, and nonnegativity prevents cancellation. Consequently, dominance is exactly the condition that a role component has positive limiting population weight.
Conditional on the state, the current signal is independent of earlier actions. Earlier actions depend only on earlier signals and independent tie coins, so this independence holds both for observed neighbor actions and for the complete earlier transcript.
The thresholds \(1-q\) and \(q\), including the stated fair-coin behavior at equality, are correct. Since \(q>1/2\), the thresholds are distinct. Accordingly, \(Z_i\) correctly identifies precisely those histories at which the action channel depends on the current signal.
At an informative history, the action probabilities satisfy
\[
\alpha_1-\alpha_0\geq\frac12.
\]
Conditional independence then gives the claimed identity
\[
b_1-b_0=(2q-1)(\alpha_1-\alpha_0).
\]
The binary relative-entropy inequality is stated with the correct constant for natural logarithms. Its supplied differentiation argument is valid. Applying it to the displayed mutual-information expression gives
\[
2r(1-r)(b_1-b_0)^2
\geq\frac12q(1-q)(2q-1)^2=c_q.
\]
Here \(r(1-r)\geq q(1-q)\) throughout the specified interval. Averaging over histories proves the stated bound, and \(c_q>0\) under the task’s assumptions.
This is the crucial structural step, and it is correct.
For an agent in a clique role \(t\), the preceding prefix of the specified stream contains exactly its earlier neighbors: all earlier agents of its own role and all earlier agents of adjacent roles. Fixed ordering and agent identities make the stream prefix and the observed vector equivalent information.
Therefore, the clique agents’ conditional mutual-information terms are actual terms in the chain rule for that stream. Other terms are nonnegative, and the stream’s total information about the binary state is at most \(\log2\). The resulting budget
\[
\mathbb E\sum_{i:t_i=t}Z_i\leq\frac{\log2}{c_q}
\]
follows.
Conversion from the uniform-prior expectation to the state-\(1\) expectation correctly incurs a factor of at most two. Each independent-role agent contributes at most one to the count, so the additional bound by \(b\) is valid.
The two transcript distributions have common support because signals and tie-coin assignments have positive probability under both states and are processed through the same decision rules.
After fixing a complete earlier history, the current action is obtained from the current signal through a channel determined by the observed subhistory. That channel is the same under both states.
When \(Z_i=0\), the channel is constant and contributes zero relative entropy. When \(Z_i=1\), contraction bounds its contribution by
\[
D_q=(2q-1)\log\frac{q}{1-q}.
\]
This is the correct relative entropy between the two conditional signal distributions.
The relative-entropy chain rule averages these contributions under state \(1\), matching the expectation bounded in Section 1.2. Hence the claimed bound by \(K\) follows without a conditioning mismatch.
The affinity bound obtained through Jensen’s inequality has the correct direction and exponent:
\[
\rho\geq e^{-K/2}.
\]
The stated total-variation bound and uniform-prior testing-error formula apply to the finite transcript distributions. The subsequent bound by \(\rho^2/4\) has the correct constant.
Each individual action is a coordinate of the full transcript, hence an available transcript-based estimator. Its error cannot be below the optimal error using the transcript. Thus the uniform obstruction applies to every agent, exactly as claimed.
Restricting an ordering to a role component preserves its action process. There are no intercomponent observations, and the ordering is chosen before signals and supplies no state information.
A singleton independent role consists entirely of isolated agents, each with accuracy exactly \(q\).
If a component contains no growing independent role, every populated independent role has degree zero and therefore a fixed constant population. The obstruction consequently applies with constants \(h_C\) and \(b_C\) independent of \(k\).
These cases exhaust criterion failures: a singleton clique belongs to the second case, and a nonsingleton failing the criterion must lack a growing independent role. Positive component weight makes both displayed limiting error lower bounds strictly positive.
The chosen growing independent role has a neighboring role because its role component is connected and nonsingleton. Every chosen role has at least one agent at every allowed scale.
The seed count is a nonnegative integer, tends to infinity, and leaves at least one agent of its role outside the seeds. This includes scales at which \(p_t(k)=1\), when the seed count is zero.
The hub, seeds, and representatives can therefore be chosen distinctly as specified. A rooted spanning tree supplies the required parent-before-child representative order.
The seeds have no earlier neighbors and act on their independent private signals. The hub observes exactly those seed actions before acting, so its posterior-maximizing action is the majority of those signals and its own, with fair tie-breaking.
The binomial mean and variance are correct. An erroneous action can occur only when \(X\leq n/2\). Markov’s inequality applied to the squared deviation gives the displayed error bound, including its constant. Capping it at one is valid, and it tends to zero.
Copying an observed earlier neighbor is a feasible decision rule. Posterior maximization therefore gives the stated unconditional accuracy comparison within the same constructed process. Independence between observed actions is unnecessary.
Every nonroot representative observes its parent. After the representatives act, every remaining agent observes a representative of a neighboring role. Thus the hub’s error bound propagates to all nonseed agents.
The attribution to [Lu et al., Theorem 3](https://arxiv.org/html/2410.04317v1) is consistent with its independent-seed aggregation and propagation construction. The output also supplies its own sufficient argument, so this citation introduces no unverified dependency.
The displayed aggregate error bound validly charges seeds and nondominant agents error at most one, and all other agents the corresponding component error bound.
Nondominant populations have lower degree than \(N(k)\). Seed counts are bounded by \(\sqrt{N(k)}\), and there are finitely many components for each fixed input. Every term therefore tends to zero.
Concatenating component orders preserves their learning processes because components have no edges between them.
Support and degree detection, role-component computation, and criterion checking require only the encoded polynomials and role matrix. The stated conservative decision bound is valid and does not enumerate possible types outside the supplied support.
The proposed \(B_k\) safely bounds coefficient evaluation sizes, total population size, and label lengths: polynomial evaluation contributes at most degree times the bit length of \(k\), together with coefficient and summation overhead.
The schoolbook Horner, binary-search square-root, and output-writing bounds are consistent. Spanning-tree computation and input processing fit within the remaining term. Thus
\[
O(R_0B_k^2+mB_k^3+N(k)B_k)
\]
is a valid construction bound. The distinction between constructing the ordering and computing agents’ posteriors correctly matches the requested task.
The two-disjoint-stars example correctly demonstrates successful learning outside the stated global hub-and-seed subclass. Each component passes the criterion, while either hub’s component omits a positive fraction of the total population.
The cited [finite directed-network hardness result](https://arxiv.org/html/2502.12704v1) concerns a different decision problem and does not contradict the established criterion.
No repair or additional clarification is required.
⟨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.