Answer: \(\mathrm{NP}\)-hard under polynomial-time many-one reductions, already for \(\tau=2\) with Boolean domains, equal masses, and \(p_1=p_2=1\); also in \(\mathrm P_{\parallel}^{\mathrm{NP}}\).
Proposition 4.5 — class: hardness
Given a finite-support distribution \(\mu\) over expert types \(t=(M_t,p_t)\), a default setting \(\vec v^*\), and a rational threshold \(q\), decide whether \(K(\mu)\ge q\), where \(K(\mu)=\sum_{t,s}\mu_t\mu_s p_t p_s\chi(t,s)\) and \(\chi(t,s)=1\) exactly when \(M_t\) and \(M_s\) are fully compatible with respect to \(\vec v^*\), and is \(0\) otherwise.
A society is given by its support: a list of \(\tau\ge1\) expert types \(t=(M_t,p_t)\) with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\) and \(p_t\in\mathbb Q\cap(0,1]\). Here \(\tau\) is the support size, not the number of possible types.
Each \(M_t=((U_t,V_t,R_t),F_t)\) is an acyclic structural causal model with finite disjoint exogenous and endogenous variable sets, explicitly listed nonempty finite domains, and structural equations represented by circuits of size polynomial in its number of variables. Circuits encode domain values in binary and always output valid values. Let \(m\) be the number of distinct variables across the support and \(L\) the total input bit length; state running times in \(m,\tau,L\).
The causal graph has an edge \(A\to B\) exactly when varying \(A\), with all other inputs fixed, can change \(F_B\). Write \(N_i=U_i\cup V_i\) and \(\operatorname{Pa}_i(C)\) for the parents of \(C\), taking this set to be empty when \(C\) is exogenous.
The input default setting \(\vec v^*\) assigns a valid value to every variable exogenous in any support model. Contexts \(u_i,u_j\) are compatible with it when they agree on \(U_i\cap U_j\) and equal \(\vec v^*\) on \(U_i\setminus U_j\) and \(U_j\setminus U_i\), respectively.
For models agreeing on all shared domains, define \(M_i\succeq_C^{\vec v^*}M_j\) by two conditions: \(\operatorname{Pa}_j(C)\) equals the set of nodes \(B\in N_j\) having a positive-length directed path to \(C\) in \(M_i\) with no internal node in \(N_j\); and, for every assignment \(x\) to \(X=(N_i\cap N_j)\setminus\{C\}\) and every compatible context pair, \(C\) has the same value in both models after intervening on \(X\) to set it to \(x\). Interventions replace endogenous equations by constants and override exogenous context values.
Models are fully compatible relative to \(\vec v^*\) iff their domains agree on every shared variable and, for every \(C\in(V_i\cap V_j)\cup(V_i\cap U_j)\cup(V_j\cap U_i)\), either \(M_i\succeq_C^{\vec v^*}M_j\) or \(M_j\succeq_C^{\vec v^*}M_i\).
Let \(\chi(t,s)\) indicate this full compatibility and define \(K(\mu)=\sum_{t,s}\mu_t\mu_s p_t p_s\chi(t,s)\), summing over ordered support pairs including diagonal pairs. The input includes \(q\in\mathbb Q\).
Is deciding whether \(K(\mu)\ge q\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For two succinctly represented models, full compatibility relative to a default setting is known to be \(\mathrm{coNP}\)-hard and in \(\mathrm P_{\parallel}^{\mathrm{NP}}\); with full structural-function tables it is polynomial-time decidable. [Source](https://arxiv.org/pdf/2005.10180v1)
No published complexity classification for exactly this distribution-weighted threshold problem was identified in the search.
The problem is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions, already when \(\tau=2\), all domains are Boolean, both masses are \(1/2\), and both reliability parameters are \(1\).
It also belongs to \(\mathrm P_{\parallel}^{\mathrm{NP}}\). Consequently, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm P=\mathrm{NP}\).
Let \(\varphi(X_1,\ldots,X_n)\) be a Boolean formula. We construct two models, denoted \(M_{\mathrm{large}}\) and \(M_{\mathrm{small}}\). Every variable has domain \(\{0,1\}\).
Both models have exogenous variables
\[
\text{}
\]
\(U=\{A,X_1,\ldots,X_n\}\).
Their endogenous variables and equations are:
| Model | Endogenous variables | Structural equations |
|---|---|---|
| \(M_{\mathrm{large}}\) | \(\{D,H,C\}\) | \(D=A\land\varphi(X_1,\ldots,X_n)\), \(H=A\), \(C=D\oplus H\oplus A\) |
| \(M_{\mathrm{small}}\) | \(\{C\}\) | \(C=A\land\varphi(X_1,\ldots,X_n)\) |
Here \(\oplus\) denotes Boolean exclusive-or. Set the default value of every exogenous variable to \(0\).
Both models are acyclic: in the larger model, edges go from exogenous variables to \(D,H,C\), or from \(D,H\) to \(C\); in the smaller model, all edges go from exogenous variables to \(C\).
The construction has polynomial input length. To ensure that circuit sizes are polynomial in the number of model variables, we may append as many unused, shared Boolean exogenous variables as the encoding length of \(\varphi\). These variables create no edges and do not affect the argument. Thus, for a formula of length \(s\), the construction has \(m=O(s)\), \(\tau=2\), and \(L=s^{O(1)}\).
The models share exactly the variables \(U\cup\{C\}\), and \(C\) is their only shared endogenous variable. Therefore, the only variable requiring a dominance comparison is \(C\).
For this comparison, the intervention set is exactly \(U\). Write an arbitrary intervention assignment as \(A=a\) and \(X_k=x_k\). The larger model then gives
\(D=a\land\varphi(x)\), \(H=a\), and hence
\(C=(a\land\varphi(x))\oplus a\oplus a=a\land\varphi(x)\).
This is exactly the value of \(C\) in the smaller model.
The exogenous sets are identical, so compatible contexts agree everywhere. Moreover, the intervention overrides every exogenous value. The calculation therefore proves agreement for every intervention assignment and every compatible context pair.
Thus, the universal value-agreement condition holds in both dominance directions, regardless of whether \(\varphi\) is satisfiable.
Call \(X_k\) *essential* for \(\varphi\) if two Boolean assignments differing only at \(X_k\) can give different values of \(\varphi\). Let \(E_\varphi\) be the set of essential variables.
No computation of \(E_\varphi\) is needed in the reduction; it is used only to describe the semantic graphs.
The equation is \(C=A\land\varphi(X)\).
The variable \(A\) is a parent of \(C\) exactly when \(\varphi\) is satisfiable:
For each \(X_k\), membership in \(\operatorname{Pa}_{\mathrm{small}}(C)\) is equivalent to membership in \(E_\varphi\). Indeed, fixing \(A=1\) makes the equation equal to \(\varphi\), while fixing \(A=0\) makes it constant.
Consequently,
\(\operatorname{Pa}_{\mathrm{small}}(C)=E_\varphi\cup\{A\}\) if \(\varphi\) is satisfiable, and \(\operatorname{Pa}_{\mathrm{small}}(C)=\varnothing\) otherwise.
In the larger model, the parents of \(C\) are exactly \(\{D,H,A\}\). Each is an actual semantic parent: changing any one input to the exclusive-or equation, while fixing the others, changes its output.
Consider the nodes of \(N_{\mathrm{small}}\) that have a positive-length path to \(C\) in the larger model with no internal node in \(N_{\mathrm{small}}\).
The node \(A\) always qualifies, because \(A\to C\) is a direct edge. An \(X_k\) qualifies exactly when it belongs to \(E_\varphi\): its only possible outgoing edge is to \(D\), and this edge exists exactly when \(X_k\) is essential for \(A\land\varphi(X)\), equivalently for \(\varphi(X)\). When present, the path \(X_k\to D\to C\) qualifies because \(D\notin N_{\mathrm{small}}\).
There are no other qualifying nodes. Thus this projected parent set is always
\(\{A\}\cup E_\varphi\).
Together with the value-agreement result, this proves
\(M_{\mathrm{large}}\succeq_C^{\vec v^*}M_{\mathrm{small}}\quad\Longleftrightarrow\quad\varphi\text{ is satisfiable}.\)
For \(M_{\mathrm{small}}\succeq_C^{\vec v^*}M_{\mathrm{large}}\), the graph condition would require \(\operatorname{Pa}_{\mathrm{large}}(C)=\{D,H,A\}\) to equal a set of nodes having paths in the smaller model.
But \(D\) and \(H\) are absent from the smaller model, so neither can belong to that path set. The required equality is impossible.
All shared domains agree, and \(C\) is the only variable requiring comparison. Therefore,
\(\chi(M_{\mathrm{large}},M_{\mathrm{small}})=1\quad\Longleftrightarrow\quad\varphi\text{ is satisfiable}.\)
Every model is fully compatible with itself. To check this explicitly, when comparing a model with itself, a path with no internal node in its full node set must have length one. The projected parent set is therefore exactly the ordinary parent set. Compatible contexts are identical, so the value-agreement condition also holds.
Now use the two distinct types
\(t_1=(M_{\mathrm{large}},1)\), \(t_2=(M_{\mathrm{small}},1)\),
with \(\mu_1=\mu_2=1/2\), and choose \(q=3/4\). These are valid positive binary-rational masses summing to \(1\).
Compatibility is symmetric by definition. Including both diagonal and both off-diagonal ordered pairs gives
\(K(\mu)=\frac14+\frac14+\frac14\chi(t_1,t_2)+\frac14\chi(t_2,t_1)=\frac12+\frac12\chi(t_1,t_2)\).
Hence \(K(\mu)=1\) when \(\varphi\) is satisfiable, and \(K(\mu)=1/2\) otherwise. In particular,
\(K(\mu)\ge\frac34\quad\Longleftrightarrow\quad\varphi\text{ is satisfiable}.\)
The construction is polynomial-time, so this is a polynomial-time many-one reduction from Boolean satisfiability. It proves the claimed \(\mathrm{NP}\)-hardness.
The upper bound extends the pairwise bound in [Proposition 4.9 of the cited paper](https://arxiv.org/pdf/2005.10180v1) to the explicit weighted support. The following argument verifies it directly for the given representation.
Issue one batch of queries to an \(\mathrm{NP}\) oracle:
All queries can be prepared without oracle answers. After receiving the answers, construct the semantic graphs, compute the required projected path sets, and evaluate every compatibility indicator. Graph processing takes \(O(\tau^2m^3)\) time.
Finally, compute the weighted sum exactly. Products of the input rational denominators provide a common denominator of polynomial bit length in \(L\), so summation and comparison with \(q\) take polynomial bit time.
Thus the problem uses \(O(\tau m^2+\tau^2m)\) parallel \(\mathrm{NP}\) queries and polynomial deterministic work in \(m,\tau,L\). This proves membership in \(\mathrm P_{\parallel}^{\mathrm{NP}}\).
A direct deterministic implementation can instead enumerate the assignments for these queries. Since domains are explicitly listed, their cardinalities are at most \(L\); this gives a running-time bound of \(\tau^2L^{O(m+1)}\).
⟨structured verdict parsed — rendered above⟩
The output proves the claimed \(\mathrm{NP}\)-hardness and membership in \(\mathrm P_{\parallel}^{\mathrm{NP}}\). The reduction respects the task’s semantic definition of causal edges, intervention semantics, support encoding, and ordered-pair sum. I found no mathematical gaps requiring repair.
Both constructed models satisfy the input requirements:
The padding argument correctly addresses the requirement that circuit sizes be polynomial in the number of model variables. Adding \(O(s)\) unused shared exogenous variables makes the variable count sufficiently large for the formula circuit, while preserving every relevant dependency and outcome. Listing their domains and default values also takes polynomial space.
Thus the claimed bounds \(m=O(s)\), \(\tau=2\), and \(L=s^{O(1)}\) are justified. Computing the semantic graphs is unnecessary during the reduction.
The only variable requiring a dominance comparison is \(C\): it is the only shared variable endogenous in either model. The shared exogenous variables are excluded from that comparison requirement.
The intervention set for \(C\) consists of all shared exogenous variables, including any padding variables. Consequently, every exogenous value used by either model is overridden by the intervention.
For every intervention assignment, the larger model gives \(D=a\land\varphi(x)\), \(H=a\), and therefore \(C=(a\land\varphi(x))\oplus a\oplus a=a\land\varphi(x)\). This agrees with the smaller model.
The calculation covers every compatible context pair because the intervention removes dependence on the original context values. The universal agreement condition is therefore established in both directions.
The claimed characterization of \(\operatorname{Pa}_{\mathrm{small}}(C)\) is correct.
The variable \(A\) is essential to \(A\land\varphi(X)\) exactly when some assignment satisfies \(\varphi\). Each \(X_k\) is essential to that function exactly when it is essential to \(\varphi\): fixing \(A=1\) preserves its dependence, while fixing \(A=0\) removes all dependence.
If \(\varphi\) is unsatisfiable, it is constant zero and \(E_\varphi=\varnothing\). Thus the stated satisfiable and unsatisfiable cases are consistent.
The parents of \(C\) are exactly \(\{D,H,A\}\). Each input independently affects the exclusive-or structural function.
This uses the task’s definition correctly: semantic dependence tests arbitrary fixed input values to the structural function. The identity \(H=A\) along actual solutions does not eliminate either input’s semantic edge to \(C\).
The projected path set is exactly \(\{A\}\cup E_\varphi\):
Hence the forward graph condition holds exactly when \(\varphi\) is satisfiable.
The reverse graph condition cannot hold. Its required parent set contains \(D\) and \(H\), but neither is a node of the smaller model and therefore neither can start a path there.
Combining these graph checks with universal value agreement establishes the claimed equivalence between full compatibility and satisfiability.
The self-compatibility argument is valid. When a model is compared with itself, every internal path node would belong to its full node set. Thus qualifying paths have length one, yielding exactly the ordinary parents. Identical compatible contexts and identical interventions give identical outcomes.
The two types are distinct, their masses are valid positive binary rationals, and their reliability parameters are permitted.
Accounting for all four ordered pairs gives exactly \(K(\mu)=\frac12+\frac12\chi(t_1,t_2)\). Therefore the score is \(1\) for satisfiable formulas and \(\frac12\) for unsatisfiable formulas. The threshold \(q=\frac34\) separates these cases correctly.
This is a polynomial-time many-one reduction from Boolean satisfiability, establishing the stated restricted \(\mathrm{NP}\)-hardness.
Both proposed oracle query families are in \(\mathrm{NP}\).
For semantic edges, valid input assignments differing only at the candidate parent provide polynomial-size certificates, and circuit evaluation verifies dependence.
For value disagreement, the supplied contexts, intervention, and resulting assignments have polynomial encoding length. Checking domains, compatibility, overridden values, and all remaining equations is polynomial-time. Under the promised acyclicity, satisfying assignments are exactly the unique intervention outcomes. This also handles comparisons where \(C\) is exogenous in one model.
The queries are genuinely nonadaptive: the disagreement certificates can be checked directly against equations without knowing the semantic graph. Shared-domain mismatches can be detected deterministically.
The query counts \(O(\tau m^2+\tau^2m)\) and graph-processing bound \(O(\tau^2m^3)\) are valid. Exact rational arithmetic remains polynomial in \(L\), including the final comparison with \(q\).
The cited pairwise upper bound is indeed stated in [Proposition 4.9](https://arxiv.org/pdf/2005.10180v1). The output also supplies an independent verification for the task’s representation, so its conclusion does not depend on an unstated application of that proposition.
Finally, explicit domains have cardinality at most \(L\), and each certificate assigns only \(O(m)\) variable values. Exhaustive enumeration therefore supports the loose deterministic bound \(\tau^2L^{O(m+1)}\).
No additional mathematical clarification or repair is needed. The target is resolved as \(\mathrm{NP}\)-hard, with the stated upper bound. The conclusion that a polynomial-time algorithm would imply \(\mathrm P=\mathrm{NP}\) follows.
⟨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.