Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateInfluence minimization (Problem 1) is NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(\mathcal{T}\), rational type masses \(\mu\), seed fractions \(s_a\), type-to-type contact rates \(\lambda_{ab}\), activation probabilities \(p_{ab}\), horizon \(H\), blocking costs \(q_{ab}\), budget \(B\), and \(\varepsilon>0\), choose retained-contact fractions \(\rho\in[0,1]^{\mathcal{T}\times\mathcal{T}}\) satisfying \(\sum_{a,b}q_{ab}(1-\rho_{ab})\le B\) to obtain an \(\varepsilon\)-optimal value of \(\sum_b z_{b,H}\), where \(x_{b,0}=s_b\mu_b\), \(z_{b,h}=\sum_{\ell=0}^{h}x_{b,\ell}\), and \(x_{b,h+1}=(\mu_b-z_{b,h})\left(1-\exp\left(-\sum_a\lambda_{ab}p_{ab}\rho_{ab}x_{a,h}/\mu_b\right)\right)\).
A society is given by its support: a list \(\mathcal T\) of \(\tau\) types with positive binary-rational masses \(\mu_b\), with \(\sum_b\mu_b=1\). Here \(\tau\) is the support size, not the number of possible types; let \(m=\tau^2\) count ordered type pairs.
Inputs are binary rationals \(s_b,p_{ab}\in[0,1]\), \(\lambda_{ab}\ge0\), \(q_{ab}>0\), \(B>0\), and \(0<\varepsilon<1\), together with a positive integer horizon \(H\) encoded in unary. Let \(L\) be the total input bit length.
Choose a single, time-independent matrix \(\rho\in[0,1]^{\mathcal T\times\mathcal T}\) satisfying \(\sum_{a,b}q_{ab}(1-\rho_{ab})\le B\); \(q_{ab}\) is the cost of completely blocking that ordered pair.
Define newly activated masses \(x_{b,0}=s_b\mu_b\), cumulative activated masses \(z_{b,h}=\sum_{\ell=0}^{h}x_{b,\ell}\), and, for \(0\le h<H\),
\(x_{b,h+1}=(\mu_b-z_{b,h})\left(1-\exp\left(-\sum_a\lambda_{ab}p_{ab}\rho_{ab}x_{a,h}/\mu_b\right)\right)\).
Only newly activated mass transmits at the next step; activated mass never becomes susceptible again. Minimize \(F(\rho)=\sum_bz_{b,H}\), including seeds.
The computational problem is to find a feasible rational \(\rho\) with \(F(\rho)\le\min_{\rho'\text{ feasible}}F(\rho')+\varepsilon\), using ordinary bit computation.
Is this additive-\(\varepsilon\) optimization problem solvable in time polynomial in \(m,\tau,H,L\), or is it NP-hard?
For finite directed graphs, minimizing expected terminal independent-cascade influence by deleting a prescribed number of edges is NP-hard ([Lee et al., 2025](https://arxiv.org/html/2502.01031v1)).
Their continuous edge-retention method optimizes a learned surrogate with budget and integrality penalties; it does not classify the mass recurrence above. No complexity classification for this precise recurrence was located.
The problem is \(\mathrm{NP}\text{-hard}\), already when \(H=1\). Consequently, an algorithm polynomial in \(m,\tau,H,L\) would imply \(\mathrm P=\mathrm{NP}\).
The proof uses the stated binary encoding of \(\varepsilon\). It gives a polynomial reduction from SUBSET SUM and handles fractional retention matrices directly.
SUBSET SUM asks whether positive binary-encoded integers \(w_1,\ldots,w_n\) have a subset summing to an integer \(T\). This problem is \(\mathrm{NP}\)-complete. [MIT lecture notes](https://people.csail.mit.edu/rrw/6.1400-2025/lec19-before-class.pdf)
Write \(W=\sum_{i=1}^n w_i\). We may assume \(0<T<W\), since the excluded cases are immediately decidable.
Let \(D\) be the smallest power of two strictly greater than \(2W\). Thus \(2W<D\le 4W\). Construct a society with support
\(\mathcal T=\{\sigma,d,1,\ldots,n\}\), where \(\sigma\) is the seeded source and \(d\) is an isolated auxiliary type.
Set the masses to
\(\displaystyle \mu_\sigma=\frac12,\qquad \mu_i=\frac{w_i}{D}\quad(1\le i\le n),\qquad \mu_d=\frac12-\frac WD.\)
Every mass is positive, and their sum is one. Set \(s_\sigma=1\) and every other seed fraction to zero.
The only pairs with nonzero transmission parameters are
\(\displaystyle p_{\sigma i}=1,\qquad \lambda_{\sigma i}=\frac{2w_i}{D}\quad(1\le i\le n).\)
Set all other \(p_{ab}\) and \(\lambda_{ab}\) to zero. Define the blocking costs by
\(\displaystyle q_{\sigma i}=w_i,\)
and set every other \(q_{ab}=1\). Finally, take
\(\displaystyle B=T,\qquad H=1,\qquad \varepsilon=\frac{1}{64D}.\)
All input numbers are dyadic rationals, including the integers.
Write \(r_i=\rho_{\sigma i}\). Initially, only the source has newly activated mass, namely \(x_{\sigma,0}=1/2\). For target type \(i\), the exposure in the recurrence is exactly
\(\displaystyle \lambda_{\sigma i}p_{\sigma i}\rho_{\sigma i}\frac{x_{\sigma,0}}{\mu_i} =\frac{2w_i}{D}\,r_i\,\frac{1/2}{w_i/D} =r_i.\)
Consequently, the objective is
\(\displaystyle F(\rho)=\Phi(r):=\frac12+\frac1D\sum_{i=1}^n w_i(1-e^{-r_i}).\)
The source contributes its seeded mass; the auxiliary type contributes zero.
Every feasible matrix satisfies
\(\displaystyle \sum_{i=1}^n w_i(1-r_i)\le T,\)
because these terms are part of the budget sum and all remaining terms are nonnegative. Conversely, any vector satisfying this inequality extends to a feasible matrix by setting every other retention coordinate to one. Those coordinates do not affect the objective.
Thus the optimization problem is exactly minimization of \(\Phi\) over
\(\displaystyle P=\left\{r\in[0,1]^n:\sum_i w_i r_i\ge W-T\right\}.\)
Define \(f(t)=1-e^{-t}\) and \(c=f(1)=1-e^{-1}\). For every \(t\in[0,1]\),
\[\displaystyle f(t)-ct\ge \frac18t(1-t)\ge \frac1{16}\min\{t,1-t\}. \tag{1}\]
To prove the first inequality, define
\(\displaystyle g(t)=f(t)-ct-\frac18t(1-t).\)
We have \(g(0)=g(1)=0\), and
\(\displaystyle g''(t)=-e^{-t}+\frac14\le -e^{-1}+\frac14<0,\)
using the elementary bound \(e<4\). Hence \(g\) is concave and lies above the chord joining its endpoints, so \(g(t)\ge0\).
For the second inequality, put \(u=\min\{t,1-t\}\). Then \(u\le1/2\) and \(t(1-t)=u(1-u)\ge u/2\). This proves (1). We also have \(c>1/2\), since \(e>2\).
Define the reference value
\(\displaystyle C=\frac12+\frac{c(W-T)}D.\)
For any \(r\in P\), let its budget slack in retention coordinates be
\(\displaystyle S=\sum_i w_i r_i-(W-T)\ge0.\)
Round each coordinate to a nearest endpoint:
\(\displaystyle \widehat r_i=0\ \text{if }r_i<\frac12,\qquad \widehat r_i=1\ \text{if }r_i\ge\frac12.\)
Define the weighted rounding error
\(\displaystyle E=\sum_i w_i|r_i-\widehat r_i| =\sum_i w_i\min\{r_i,1-r_i\}.\)
By (1),
\[\displaystyle \Phi(r)-C =\frac1D\left(cS+\sum_i w_i\bigl(f(r_i)-cr_i\bigr)\right) \ge\frac1D\left(cS+\frac E{16}\right) \ge\frac{S+E}{16D}. \tag{2}\]
In particular, \(\Phi(r)\ge C\) for every feasible vector. Moreover, the triangle inequality gives
\[\displaystyle \left|\sum_i w_i\widehat r_i-(W-T)\right| \le E+S \le16D\bigl(\Phi(r)-C\bigr). \tag{3}\]
This bound applies to every feasible fractional vector; no integrality assumption about an optimizer is needed.
Suppose a subset \(I\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in I}w_i=T\). Choose \(r_i=0\) for \(i\in I\) and \(r_i=1\) otherwise. This vector is feasible and has
\(\displaystyle \Phi(r)=\frac12+\frac{c(W-T)}D=C.\)
Together with (2), this proves that the optimum is exactly \(C\).
If an additive-\(\varepsilon\) optimizer returns a feasible matrix, its active coordinates therefore satisfy
\(\displaystyle \Phi(r)-C\le\varepsilon=\frac1{64D}.\)
Equation (3) yields
\(\displaystyle \left|\sum_i w_i\widehat r_i-(W-T)\right|\le\frac14.\)
Both quantities inside the absolute value are integers. They must therefore be equal. Consequently, the rounded blocked subset
\(\displaystyle \widehat I=\{i:\widehat r_i=0\}\)
satisfies \(\sum_{i\in\widehat I}w_i=T\).
If no subset sums to \(T\), no rounded blocked subset can sum to \(T\). Equivalently, for every feasible \(r\),
\(\displaystyle \sum_i w_i\widehat r_i\ne W-T.\)
The difference is an integer, so its absolute value is at least one. By (3),
\(\displaystyle \Phi(r)\ge C+\frac1{16D}.\)
Thus fractional choices cannot close the separation gap.
The construction has \(\tau=n+2\), \(m=(n+2)^2\), and unary horizon \(H=1\). Since \(D\le4W\), its binary length is polynomial in the SUBSET SUM input length. The same holds for every constructed parameter, including \(\varepsilon=1/(64D)\), and for the complete pair tables.
Now suppose the requested optimizer ran in time polynomial in \(m,\tau,H,L\). To decide SUBSET SUM:
For YES instances, the rounding guarantee proves acceptance. For NO instances, no subset can pass the check. All postprocessing uses polynomial-time rational and integer arithmetic; no exponential evaluation is required.
This would decide an \(\mathrm{NP}\)-complete problem in polynomial time, establishing the claimed hardness. The reduction permits very small binary-encoded accuracy; it does not establish hardness for fixed \(\varepsilon\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the stated task: the additive-\(\varepsilon\) optimization problem is \(\mathrm{NP}\)-hard already for \(H=1\), with binary-encoded accuracy. I found no major or minor mathematical issues.
The reduction addresses fractional retention matrices directly and uses only exact rational and integer arithmetic to interpret the optimizer’s output.
The invoked theorem is that SUBSET SUM with positive binary-encoded integer weights and an integer target is \(\mathrm{NP}\)-complete. The cited [MIT lecture notes](https://people.csail.mit.edu/rrw/6.1400-2025/lec19-before-class.pdf) confirm NP-completeness for positive integer weights and a positive integer target.
The restriction \(0<T<W\) is legitimate. With positive weights, targets outside this range are immediately decidable: \(T=0\) and \(T=W\) are achievable, while \(T<0\) and \(T>W\) are not. Such inputs can be handled before invoking the construction.
For the smallest power of two strictly greater than \(2W\), the bound \(2W<D\le4W\) is correct. Consequently, each target mass \(\mu_i=w_i/D\) is positive, and the auxiliary mass satisfies \(\mu_d=1/2-W/D>0\).
The masses sum exactly to one:
\[
\frac12+\frac WD+\left(\frac12-\frac WD\right)=1.
\]
All seed fractions and transmission probabilities lie in their required intervals. Every transmission rate is nonnegative, every blocking cost is positive, and \(B=T>0\).
Since \(D\) is a power of two, every constructed numerical input is dyadic. The chosen accuracy satisfies \(0<\varepsilon=1/(64D)<1\). The horizon \(H=1\) is a valid positive unary-encoded horizon.
Thus the construction respects every stated input restriction, including positive support masses.
Initially, only the source has newly activated mass, equal to \(1/2\). Each target has cumulative activated mass zero and therefore susceptible mass \(\mu_i\).
The exposure calculation is exact:
\[
\lambda_{\sigma i}p_{\sigma i}\rho_{\sigma i}\frac{x_{\sigma,0}}{\mu_i}
=\frac{2w_i}{D}r_i\frac{1/2}{w_i/D}
=r_i.
\]
The source has no susceptible mass, and the auxiliary type receives no transmission. Hence the stated objective
\[
\Phi(r)=\frac12+\frac1D\sum_iw_i(1-e^{-r_i})
\]
correctly includes all seeds and all activation through horizon one.
The feasible-region equivalence is also exact. Nonnegative budget contributions from other coordinates imply \(\sum_iw_i(1-r_i)\le T\). Conversely, setting every other coordinate to one makes its blocking cost zero and extends every such vector to a feasible matrix.
Accordingly, minimizing over matrices is equivalent to minimizing over the stated set \(P\).
The derivatives and constants are correct. For the defined function \(g\),
\[
g''(t)=-e^{-t}+\frac14\le-e^{-1}+\frac14<0
\]
throughout \(0\le t\le1\), using \(e<4\). Since \(g(0)=g(1)=0\), concavity gives \(g(t)\ge0\).
For \(u=\min\{t,1-t\}\), the identity \(t(1-t)=u(1-u)\) and the bound \(u\le1/2\) give \(t(1-t)\ge u/2\). Both inequalities in equation (1), including their constants and endpoints, follow.
The additional bound \(c>1/2\) follows from \(e>2\).
The slack \(S\) is nonnegative for every feasible vector. The rounding rule, including its tie convention, gives exactly
\[
|r_i-\widehat r_i|=\min\{r_i,1-r_i\}.
\]
The decomposition of \(\Phi(r)-C\) is algebraically correct. Applying equation (1) yields
\[
D(\Phi(r)-C)\ge cS+\frac E{16}\ge\frac{S+E}{16}.
\]
The last inequality uses \(S\ge0\) and \(c>1/2>1/16\). Thus equation (2) is valid.
The triangle inequality bounds the rounded retention sum’s distance from \(W-T\) by \(E+S\). Combining this with equation (2) proves equation (3). These bounds hold for every feasible fractional vector; they require no assertion about integral optimizers.
In a YES instance, blocking a subset of weight \(T\) produces a feasible endpoint vector attaining \(C\). The universal lower bound proves that \(C\) is the optimum.
An additive-\(\varepsilon\) output therefore has rounded retention sum within \(16D\varepsilon=1/4\) of \(W-T\). Both sums are integers, so they are equal. The rounded blocked subset consequently has weight exactly \(T\).
In a NO instance, no rounded blocked subset can have weight \(T\). Its complementary retention sum differs from \(W-T\) by a nonzero integer, whose absolute value is at least one. Equation (3) therefore gives the stated gap \(1/(16D)\).
The argument correctly covers fractional outputs and arbitrary rounding ties.
The binary length of \(W\), and hence of \(D\), is polynomial in the source input length. All constructed parameters have polynomial encoding length. Writing the complete pair tables requires only polynomially many entries, since \(\tau=n+2\) and \(m=(n+2)^2\).
Under the hypothesized polynomial-time optimizer, its explicitly returned rational coordinates have polynomial total output length. Comparing them with \(1/2\) and summing the selected integer weights are polynomial-time operations.
The decision procedure accepts every YES instance and rejects every NO instance. It does not evaluate exponentials or compare transcendental objective values.
The resulting hardness concerns precisely the requested dependence on binary input length, including the encoding of \(\varepsilon\). The prover correctly refrains from claiming hardness for fixed accuracy.
No repair or additional mathematical 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.