Answer: \(\mathrm{NP}\)-hard under polynomial-time Turing reductions
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIn the partial propagation setting, it is #P-complete to compute the ex- pected number of adopters for a given non-adaptive spreading strategy π. We also present a polynomial-time algorithm to compute the expected number of adopters for a given non-adaptive spreading strategy in a full propagation setting. We design an algorithm in order to simulate the amount of propagation for a given spreading strategy in Appendix D.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite community template \(G=(V,E)\), thresholds \(c_v\), rational acceptance probabilities \(p_v\), and a fixed schedule \(\pi\), consider a continuum of copies indexed by \(x\in[0,1]\), with edges only between corresponding roles within each copy. What is the exact expected adopting mass \(M=\frac{1}{|V|}\sum_{v\in V}\Pr[X_v=1]\) under the paper's cascade process?
Given a nonempty finite simple undirected graph \(G=(V,E)\), let \(m=|V|\). Each role \(v\) has a threshold \(c_v\in\mathbb Z_{>0}\) and an acceptance probability \(p_v\in\mathbb Q\cap[0,1]\); the fixed schedule \(\pi\) is a permutation of \(V\).
A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational. Here types are labeled roles, each of mass \(1/m\), so \(\tau=m\); support size means the number of listed types, not the number of possible types. Total mass is \(1\).
The population consists of copies indexed by \(x\in[0,1]\) with Lebesgue measure; role \(v\) has mass element \(dx/m\). An edge joins \((u,x)\) to \((v,x)\) exactly when \(\{u,v\}\in E\), and there are no edges between copies.
Within each copy, initial preferences \(B_v\in\{-1,1\}\) are independent, with \(\Pr(B_v=1)=p_v\). All copies have this same law and follow \(\pi\).
When role \(v\) is scheduled, put \(D_v=\sum_{u\in N(v):\,\pi^{-1}(u)<\pi^{-1}(v)}X_u\). Its permanent decision is \(X_v=1\) if \(D_v\ge c_v\), \(X_v=-1\) if \(D_v\le-c_v\), and \(X_v=B_v\) otherwise. Influence uses these neighbor counts, without mass weighting.
The quantity to compute exactly, as a binary rational, is the expected adopting mass \(M=\frac1m\sum_{v\in V}\Pr(X_v=1)\). Let \(L\) be the total binary input length, including the graph, schedule, thresholds, probabilities, and support masses.
Is exact computation of \(M\) solvable in time polynomial in \(m,\tau,L\), or is it NP-hard under polynomial-time Turing reductions?
For finite populations on arbitrary graphs, exact expected-adopter computation for a fixed schedule is reported as \(\#\mathrm P\)-complete; on complete graphs it has a polynomial-time algorithm. [Source](https://arxiv.org/pdf/1311.5925)
No result addressing this precise continuum-copy formulation was located.
Result. Exact computation of \(M\) is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. Two oracle calls suffice to recover the number of satisfying assignments of a Boolean formula. The reduction uses only dyadic probabilities and dyadic support masses.
For general rational inputs, “exact binary rational output” is understood as a numerator and denominator written in binary.
1. The continuum quantity equals a normalized finite expectation.
Fix one copy. Its decisions are determined recursively by its initial preference vector and the schedule. Because edges never connect different copies, this recursion is exactly the finite process on \(G\). Independence of the initial preferences within the copy gives the specified finite joint distribution. These finite decision rules also agree with those formalized in [Section 2 of the supplied paper](https://arxiv.org/pdf/1311.5925).
Let \(A=\sum_{v\in V}\mathbf{1}_{\{X_v=1\}}\) be the number of adopting roles in one copy. By linearity of expectation,
\[ mM=\sum_{v\in V}\Pr(X_v=1)=\mathbb{E}[A]. \]
Thus an oracle for the continuum quantity supplies the normalized expected number of adopters in the finite process. No independence between different copies is needed for this equality.
We now prove hardness directly.
2. Deterministic OR and AND gates.
Interpret decision \(1\) as Boolean true and decision \(-1\) as Boolean false.
Suppose a role has exactly \(r\ge 1\) neighbors scheduled before it. Set its threshold to \(r\).
If its acceptance probability is \(1\), it computes the OR of those neighbors’ decisions. Indeed, if every input is \(-1\), then \(D=-r\), so the role rejects. Otherwise \(D>-r\): the role either adopts because \(D\ge r\), or uses its initial preference, which is deterministically \(1\).
If its acceptance probability is \(0\), it computes their AND. When every input is \(1\), we have \(D=r\), so the role adopts. Otherwise \(D<r\): the role either rejects because \(D\le-r\), or uses its initial preference, which is deterministically \(-1\).
These statements concern earlier neighbors only; edges to roles scheduled later have no effect.
3. Constructing the two oracle instances.
Start with a \(3\)-CNF formula \(\varphi\) on variables \(z_1,\ldots,z_n\), where \(n\ge1\), with nonempty clauses \(C_1,\ldots,C_s\). Satisfiability remains \(\mathrm{NP}\)-complete under these restrictions. Repeated occurrences of a literal within a clause may be deleted without changing its satisfying assignments.
Set
\[ \varepsilon=2^{-(2n+2)}. \]
Construct the following roles and undirected edges.
Write \(h=n+s\). There are initially \(m_0=2n+h+1\) roles. Pad with isolated roles to make the total number \(m\) the least power of two at least \(m_0\). Each padding role has threshold \(1\) and acceptance probability \(0\).
The schedule places all sources first, then all OR roles and padding roles, and finally \(t\). The graph is simple: all endpoints are distinct roles, and every required edge is inserted once.
List every role as a separate support type with mass \(1/m\). Thus \(\tau=m\), the total mass is \(1\), and every support mass is dyadic.
The two instances differ only in the output threshold:
Let their exact expected adopting masses be \(M_{\mathrm{on}}\) and \(M_{\mathrm{off}}\).
In the first instance, \(t\) computes the AND of the \(h\) OR roles. In the second, \(|D_t|\le h<c_t\), so \(t\) always uses its deterministic rejecting preference.
Every other role has the same decision in both instances under the same source preferences: \(t\) is scheduled last, and changing its threshold cannot affect an earlier decision. Consequently,
\[ q:=\Pr_{\mathrm{on}}(X_t=1) =m\bigl(M_{\mathrm{on}}-M_{\mathrm{off}}\bigr). \]
This isolates the output probability using two oracle calls.
4. Recovering the number of satisfying assignments.
For each source, let \(Y_i^\pm=\mathbf{1}_{\{X_{u_i^\pm}=1\}}\). Since sources have no earlier neighbors, these \(2n\) variables are independent Bernoulli variables with parameter \(\varepsilon\).
By the gate construction, the output adopts exactly when the following monotone Boolean formula is true:
\[ F(Y)= \left(\bigwedge_{i=1}^{n}(Y_i^+\lor Y_i^-)\right) \land \left(\bigwedge_{j=1}^{s} \bigvee_{\ell\in C_j}Y_\ell\right), \]
where \(Y_{z_i}=Y_i^+\) and \(Y_{\neg z_i}=Y_i^-\).
Let \(a_k\) be the number of vectors in \(\{0,1\}^{2n}\) that satisfy \(F\) and contain exactly \(k\) ones.
Each pair condition requires at least one selected source per variable, so \(a_k=0\) for \(k<n\). A satisfying vector with exactly \(n\) ones therefore selects exactly one source from each pair. Such vectors correspond bijectively to assignments of \(\varphi\), by setting \(z_i\) true precisely when \(Y_i^+=1\). Under this correspondence, every clause condition has exactly its usual meaning. Hence
\[ a_n=\#\{\text{satisfying assignments of }\varphi\}. \]
Independence of the sources gives
\[ q=\sum_{k=n}^{2n} a_k\varepsilon^k(1-\varepsilon)^{2n-k}. \]
Define
\[ \rho=\frac{\varepsilon}{1-\varepsilon} =\frac{1}{2^{2n+2}-1}. \]
Dividing the preceding identity yields
\[ \frac{q}{\varepsilon^n(1-\varepsilon)^n} =a_n+\sum_{k=n+1}^{2n}a_k\rho^{k-n}. \]
The remainder is nonnegative. Since \(0<\rho<1\), and there are only \(2^{2n}\) source vectors in total,
\[ 0\le \sum_{k=n+1}^{2n}a_k\rho^{k-n} \le \rho\sum_{k=n+1}^{2n}a_k \le \frac{2^{2n}}{2^{2n+2}-1} <1. \]
Therefore the exact decoding formula is
\[ \#\{\text{satisfying assignments of }\varphi\} = \left\lfloor \frac{m(M_{\mathrm{on}}-M_{\mathrm{off}})} {\varepsilon^n(1-\varepsilon)^n} \right\rfloor. \]
In particular, \(\varphi\) is satisfiable if and only if this integer is positive.
5. Polynomial size and exact arithmetic.
For a \(3\)-CNF input, the construction has \(m=O(n+s)\) roles and \(O(n+s)\) edges. Padding increases the number of roles by less than a factor of two. Every threshold is at most \(h+1\), and the explicitly listed support contains exactly \(m\) types.
The binary denominator of \(\varepsilon\) has \(2n+3\) bits. Consequently, the graph, schedule, thresholds, probabilities, and support masses all have total length polynomial in the formula’s input length.
Only the \(2n\) sources are random. Put \(d=2^{2n+2}\). Each source vector has probability with denominator \(d^{2n}\), so both oracle outputs have a common denominator
\[ m d^{2n}. \]
Their exact numerator and denominator lengths are therefore \(O(n^2+\log m)\). The scaling factor \(\varepsilon^n(1-\varepsilon)^n\) also has numerator and denominator of polynomial bit length. Subtraction, scaling, and integer division in the decoding formula can thus be performed in polynomial time.
We have constructed a polynomial-time, two-query Turing reduction from Boolean satisfiability to exact computation of \(M\). This proves the requested \(\mathrm{NP}\)-hardness, even with \(\tau=m\) and entirely dyadic inputs. A polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof establishes the requested \(\mathrm{NP}\)-hardness under polynomial-time Turing reductions. The construction, probability decoding, and polynomial bit-length bounds are correct. No major or minor mathematical issues were found.
Within a copy, the decisions depend only on that copy’s preference vector and the fixed schedule. Since no edge connects different copies, the recursion is exactly the specified finite process.
The identity
\[
mM=\sum_{v\in V}\Pr(X_v=1)=\mathbb{E}[A]
\]
follows directly from the definition of \(M\) and linearity of expectation. It requires no independence between copies and no assumption about almost-sure realized population mass.
The cited comparison with the finite decision rules is accurate: Section 2 of the [supplied paper](https://arxiv.org/pdf/1311.5925) specifies the same neighbor-sum threshold rule. The proof does not rely on the paper’s hardness theorem.
Both gate claims are correct under their stated hypothesis of exactly \(r\ge1\) earlier neighbors.
For the OR role, all inputs equal to \(-1\) give \(D=-r\), forcing rejection. Every other input configuration gives \(D>-r\), so rejection cannot be forced; either adoption is forced or the deterministic adopting preference applies.
For the AND role, all inputs equal to \(1\) give \(D=r\), forcing adoption. Every other configuration gives \(D<r\), so adoption cannot be forced; either rejection is forced or the deterministic rejecting preference applies.
The threshold boundaries are handled correctly. Later neighbors have no influence under the task’s definition of \(D_v\).
The starting restrictions on \(3\)-CNF satisfiability preserve its standard \(\mathrm{NP}\)-completeness. Deleting repeated occurrences of the same literal preserves the satisfying assignments. A clause containing both signs of a variable also causes no difficulty: those signs correspond to distinct source roles.
Every source has no earlier neighbors, despite having edges to later roles. Thus its decision equals its initial preference.
Each \(P_i\) has exactly its two sources as earlier neighbors. Each \(Q_j\) has exactly its distinct literal sources as earlier neighbors. Nonempty clauses ensure that every clause threshold is positive.
The output has exactly \(h=n+s\) earlier neighbors. Since \(n\ge1\), its on-instance threshold is positive. In the on instance it computes their AND; in the off instance its threshold exceeds every possible absolute neighbor sum, so it always rejects.
Padding preserves the process on the other roles because padding roles are isolated. The graph remains finite, nonempty, simple, and undirected. The schedule is a valid permutation. Listing each role separately gives exactly \(\tau=m\) positive support masses totaling \(1\). Choosing \(m\) as a power of two makes those masses dyadic.
The two instances have the same graph, schedule, population size, support, and preferences. Only the last role’s threshold changes.
Under the same source preference vector, every earlier decision therefore agrees between the instances. The off-instance output always rejects. Consequently,
\[
m(M_{\mathrm{on}}-M_{\mathrm{off}})
=\Pr_{\mathrm{on}}(X_t=1)=q.
\]
This cancellation is exact and does not assume independence among the gate outputs.
The source indicators are independent Bernoulli variables with parameter \(\varepsilon\), as required by the task.
The displayed formula \(F\) correctly represents the output event. Its pair conditions imply that every satisfying vector has at least \(n\) selected sources. A satisfying vector with exactly \(n\) selected sources selects precisely one source from each pair.
The stated correspondence with assignments of \(\varphi\) is bijective, and under that correspondence the clause conditions agree with literal satisfaction. Thus
\[
a_n=\#\{\text{satisfying assignments of }\varphi\}.
\]
Grouping source vectors by their number of ones gives the displayed expression for \(q\). Dividing by \(\varepsilon^n(1-\varepsilon)^n\) correctly produces
\[
a_n+\sum_{k=n+1}^{2n}a_k\rho^{k-n}.
\]
The remainder estimate is valid: its terms are nonnegative, each relevant power of \(\rho\) is at most \(\rho\), and the total number of source vectors is \(2^{2n}\). For every \(n\ge1\),
\[
\frac{2^{2n}}{2^{2n+2}-1}<1.
\]
Taking the floor therefore recovers \(a_n\) exactly. This also handles unsatisfiable formulas: contributions from vectors selecting both signs of some variables remain strictly below \(1\) after scaling.
The explicit recovery argument concerns the constructed \(3\)-CNF input. That scope suffices for the claimed hardness result.
The unpadded role count is \(3n+s+1\), and power-of-two padding increases it by less than a factor of two. The number of edges is \(O(n+s)\), because each clause has at most three distinct literals.
All thresholds, schedules, labels, probabilities, and explicitly listed masses have polynomial encoding length. The denominator \(2^{2n+2}\) indeed has \(2n+3\) binary digits.
Only the \(2n\) sources are random. With \(d=2^{2n+2}\), the stated common denominator \(md^{2n}\) for the oracle outputs is valid. Because each output lies in \([0,1]\), its numerator also has polynomial bit length. Reduced representations cannot increase these bounds.
The scaling factor has polynomial numerator and denominator lengths. Exact subtraction, rational scaling, and integer division therefore take polynomial time. The decoding does not require exponentially long oracle responses.
The two legal oracle queries, followed by polynomial-time arithmetic and a positivity test, decide the restricted \(3\)-CNF satisfiability problem. This proves the requested \(\mathrm{NP}\)-hardness, including on the stated dyadic subclass with \(\tau=m\).
No additional clarification or repair is required. The proof establishes hardness; it does not claim membership in a counting complexity class or an unconditional separation from polynomial time.
⟨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.