Answer: \(\mathrm{NP}\text{-hard}\)
Proposition 1 — class: hardness
Given a finite type set \(T\), rational masses \(\mu_t\), initial influenced and mapped masses, rational type-level kernels defining cascade transmission and teaching events, a horizon \(H\), intervention budget \(\beta\), and weight \(\lambda\), choose feasible intervention masses \(x_t^r\) to maximize \(\lambda I_H+(1-\lambda)M_H\), where \(I_H\) and \(M_H\) are the resulting expected influenced and mapped masses. For input accuracy \(\epsilon\), find a schedule within \(\epsilon\) of the optimum.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Thus \(\tau\) is the support size, not the number of possible types.
Use the following homogeneous Poisson mass dynamics. Inputs are nonnegative rational transmission and teaching intensities \(P_{tu},Q_{tu}\), a unary horizon \(H\ge1\), rational budget \(0<\beta\le1\), weight \(\lambda\in[0,1]\), and accuracy \(0<\epsilon<1\). Let \(m\) count ordered pairs having a nonzero intensity, and \(L\) be the total bit length of the rational input, including \(\epsilon\).
For each type, maintain unselected masses \(U_{t,b,c}\), where \(b,c\in\{0,1\}\) indicate influenced and mapped status, and selected mass \(s_t\), which is always influenced and mapped. Initially \(s_t=0\); the four initial joint masses are supplied as nonnegative binary rationals summing to \(\mu_t\). Initial influence has already finished spreading.
In round \(r\), choose nonnegative intervention masses \(x_{t,b}^r\le U_{t,b,1}\), set \(x_t^r=x_{t,0}^r+x_{t,1}^r\), and require \(\sum_{r,t}x_t^r\le\beta\). Remove these masses from their compartments and add them to \(s_t\). Previously selected mass cannot be selected again; influenced but unselected mapped mass remains eligible.
Teaching then transfers the fraction \(1-\exp(-\sum_tQ_{tu}x_t^r)\) of every \(U_{u,b,0}\) to \(U_{u,b,1}\). Mapping means discovering individuals, and persists; it does not itself cause influence.
Complete a cascade before the next intervention. Start its active cohort at \(a_t=x_{t,0}^r\). In each wave, transfer the fraction \(f_u=1-\exp(-\sum_tP_{tu}a_t)\) of every \(U_{u,0,c}\) to \(U_{u,1,c}\); the transferred mass, summed over \(c\), is the next \(a_u\). Use each cohort once and take the limit of the wave updates. Influence persists and may reach unmapped mass.
All kernels are supplied to the planner; mapping restricts intervention eligibility. A schedule specifies rational intervention masses for these deterministic expected-mass dynamics. Define \(I_H=\sum_t(s_t+\sum_cU_{t,1,c})\), \(M_H=\sum_t(s_t+\sum_bU_{t,b,1})\), and \(\mathrm{OPT}\) as the supremum of \(\lambda I_H+(1-\lambda)M_H\) over feasible schedules.
Is finding a feasible schedule with value at least \(\mathrm{OPT}-\epsilon\) solvable in time polynomial in \(m,\tau,H,L\), or is this computational problem NP-hard?
Discrete simultaneous influencing and mapping is NP-hard, including the fully mapped, empty-teaching-list case; the source labels it NP-complete but its reduction establishes hardness only. [Source](https://amulyayadav.com/Papers/HIAI16.pdf)
Discount-based continuous influence maximization on a finite graph is also NP-hard; its controls change individual seed probabilities rather than population masses. No result settling the mass dynamics specified here was located. [Source](https://www.cs.sfu.ca/~jpei/publications/CIM%20SIGMOD16.pdf)
The problem is \(\mathrm{NP}\text{-hard}\), even with \(\ H=1\), \(\lambda=1\), no teaching, full initial mapping, and no initial influence.
The proof gives a polynomial reduction from Independent Set. It controls the complete cascade uniformly and explicitly rules out an advantage from fractional intervention masses.
Let \(G=([n],E)\) be a simple undirected graph, let \(1\le k\le n\) be an integer, and let \(d\ge2\). Define
\(\displaystyle F(y)=d\sum_{i=1}^{n}y_i-2\sum_{\{i,j\}\in E}y_i y_j,\qquad 0\le y_i\le1,\quad \sum_i y_i\le k.\)
Lemma. Every feasible \(y\) can be replaced by a feasible vector in \(\{0,1\}^{n}\) without decreasing \(F\).
Proof. Suppose two coordinates \(y_i,y_j\) are strictly between zero and one. Vary them as \(y_i+z,y_j-z\) over the maximal interval preserving their bounds. This preserves their sum and hence feasibility.
Along this interval, every term of \(F\) is affine in \(z\), except possibly the term corresponding to \(\{i,j\}\). If that edge exists, its contribution is
\(\displaystyle -2(y_i+z)(y_j-z)=-2y_i y_j+2(y_i-y_j)z+2z^2.\)
Thus \(F\) is convex along the interval. At least one endpoint has value at least its value at \(z=0\). Moving to that endpoint makes at least one of these coordinates integral.
Repeating leaves at most one fractional coordinate. If the other coordinates contain \(\ell\) ones and the remaining coordinate is fractional, feasibility and integrality of \(k\) imply \(\ell\le k-1\). Both rounding choices are therefore feasible. Since \(F\) is affine in that coordinate, one choice does not decrease \(F\). This proves the lemma.
For a set \(S\subseteq[n]\), write \(e(S)\) for the number of edges with both endpoints in \(S\). Then
\(\displaystyle F(\mathbf 1_S)=d|S|-2e(S).\)
Consequently:
For the second assertion, apply the lemma. A rounded set of size \(k\) has at least one internal edge. A rounded set of size at most \(k-1\) has value at most \(d(k-1)\le dk-2\). The first assertion follows from an independent-set witness and the universal bound \(F(y)\le d\sum_i y_i\le dk\).
We use the standard \(\mathrm{NP}\)-complete Independent Set problem: given a simple undirected graph and an integer \(1\le k\le n\), decide whether it has an independent set of size at least \(k\). Its hardness follows from the classical Clique theorem by taking graph complements: a set is independent in a graph exactly when it is a clique in its complement. [Karp, *Reducibility Among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Given such an instance, let \(d_i\) denote vertex \(i\)'s degree and set
\(\displaystyle d=\max\{2,\max_i d_i\}.\)
Let \(N\) be the smallest power of two at least \(n+2\), and let \(D\) be the smallest power of two at least \(d\). Define
\(\displaystyle \eta=\frac1N,\qquad \theta=\frac{\eta^2}{32D^2},\qquad \Delta=\theta\eta^2.\)
There are \(n+2\) types: the vertices \(1,\ldots,n\), an auxiliary type \(z\), and a filler type \(w\). Their masses are
\(\displaystyle \mu_i=\mu_z=\eta,\qquad \mu_w=1-(n+1)\eta.\)
Every mass is positive, and their sum is one. Initially everyone is mapped and uninfluenced:
\(\displaystyle U_{t,0,1}=\mu_t,\qquad U_{t,0,0}=U_{t,1,0}=U_{t,1,1}=0.\)
Set
\(\displaystyle H=1,\qquad \lambda=1,\qquad Q_{tu}=0,\qquad \beta=k\eta,\qquad \epsilon=\frac{\Delta}{4}.\)
For every edge \(\{i,j\}\in E\), set \(P_{ij}=P_{ji}=\theta\). Additionally, set
\(\displaystyle P_{iz}=\theta(d-d_i)\)
for each vertex \(i\). All other transmission intensities are zero.
Thus each vertex has total outgoing intensity \(\theta d\), and both auxiliary types have no outgoing transmission. All input quantities are dyadic rationals.
Since there is only one intervention round and no initial influence, write \(x_t=x_{t,0}^{1}\). Feasibility is exactly
\(\displaystyle 0\le x_t\le\mu_t,\qquad T:=\sum_t x_t\le\beta.\)
The objective is the final influenced mass, denoted \(I(x)\).
Define the nonnegative integer matrix \(W=P/\theta\). Its vertex rows sum to \(d\); its other rows are zero. Every type receiving transmission has mass \(\eta\).
Immediately after intervention, let
\(\displaystyle S_u=\mu_u-x_u,\qquad h_u=\theta\sum_tW_{tu}x_t.\)
The first cascade wave influences mass \(S_u(1-e^{-h_u})\) at type \(u\). Define its linear approximation and the resulting surrogate by
\(\displaystyle A(x)=\sum_u S_u h_u,\qquad J(x)=T+A(x).\)
Writing \(X=\sum_{i=1}^{n}x_i\), direct expansion gives
\(\displaystyle A(x)=\theta\left(d\eta X-2\sum_{\{i,j\}\in E}x_i x_j-x_z\sum_i(d-d_i)x_i\right).\)
Indeed, the graph edges contribute
\(\displaystyle \theta\sum_i d_i\eta x_i-2\theta\sum_{\{i,j\}\in E}x_i x_j,\)
and transmission into \(z\) contributes
\(\displaystyle \theta(\eta-x_z)\sum_i(d-d_i)x_i.\)
Their sum is the stated expression. In particular, \(J(x)\) is an exactly computable rational number whenever the intervention masses are rational.
We next prove the uniform bound
\(\displaystyle |I(x)-J(x)|\le\frac{\Delta}{16}\)
for every feasible intervention.
Let \(a^{(0)}=x\), and let \(a^{(\ell)}\) be the newly influenced cohort in wave \(\ell\), for \(\ell\ge1\). Put
\(\displaystyle \rho=\theta\eta d.\)
For any wave, susceptible masses are at most their initial masses. Using \(1-e^{-v}\le v\) for \(v\ge0\), we obtain
\(\displaystyle \|a^{(\ell+1)}\|_1\le\theta\sum_t a_t^{(\ell)}\sum_u\mu_uW_{tu}\le\rho\|a^{(\ell)}\|_1.\)
The last inequality holds because each vertex row has weighted sum \(\eta d\), and the auxiliary rows are zero. Moreover,
\(\displaystyle \rho=\frac{\eta^3d}{32D^2}\le\frac1{32d}\le\frac1{64}<\frac12.\)
Induction therefore gives \(\|a^{(\ell)}\|_1\le\rho^\ell T\). In particular, the complete cascade converges, and
\(\displaystyle \sum_{\ell\ge2}\|a^{(\ell)}\|_1\le\frac{\rho^2T}{1-\rho}\le2\theta^2\eta^2d^2T\le2\theta^2d^2.\)
Here \(T\le1\) and \(\eta\le1\). Since each cohort consists of newly influenced mass,
\(\displaystyle I(x)=T+\sum_{\ell\ge1}\|a^{(\ell)}\|_1.\)
For \(h\ge0\),
\(\displaystyle 0\le h-(1-e^{-h})=\int_0^h(1-e^{-v})\,dv\le\frac{h^2}{2}.\)
Every entry of \(W\) is at most \(d\), so \(h_u\le\theta dT\). Also \(A(x)\le\rho T\), by the same weighted-row calculation used above. Hence
\(\displaystyle 0\le A(x)-\|a^{(1)}\|_1\le\frac12\sum_uS_uh_u^2\le\frac{\theta dT}{2}A(x)\le\frac{\theta^2\eta d^2T^2}{2}\le\frac{\theta^2d^2}{2}.\)
Combining the first-wave error with the later-wave bound yields
\(\displaystyle -\frac{\theta^2d^2}{2}\le I(x)-J(x)\le2\theta^2d^2.\)
Finally,
\(\displaystyle 2\theta^2d^2=\Delta\frac{d^2}{16D^2}\le\frac{\Delta}{16},\)
which proves the claimed uniform bound.
For each vertex, set \(y_i=x_i/\eta\). Every feasible intervention satisfies
\(\displaystyle 0\le y_i\le1,\qquad \sum_i y_i=\frac X\eta\le k.\)
The term involving \(x_z\) in \(A(x)\) is nonpositive. Therefore
\(\displaystyle J(x)\le T+\Delta F(y).\)
Define the rational reference value
\(\displaystyle V_0=\beta+\Delta dk.\)
Yes instance. Suppose \(G\) has an independent set \(S\) of size \(k\). Select the whole mass \(\eta\) of each type in \(S\), and select no other mass. This is a rational feasible schedule. Its total selected mass is \(\beta\), its internal-edge term vanishes, and \(x_z=0\). Thus
\(\displaystyle J(x)=V_0,\qquad I(x)\ge V_0-\frac{\Delta}{16}.\)
Consequently,
\(\displaystyle \mathrm{OPT}\ge V_0-\frac{\Delta}{16}.\)
No instance. Suppose \(G\) has no independent set of size \(k\). The rounding lemma gives \(F(y)\le dk-2\) for every feasible intervention, including every fractional one. Hence
\(\displaystyle J(x)\le\beta+\Delta(dk-2)=V_0-2\Delta.\)
The cascade bound also implies
\(\displaystyle \mathrm{OPT}\le V_0-\frac{31\Delta}{16}.\)
These bounds concern the supremum over rational schedules directly: the yes bound uses a rational witness, and the no bound holds for every feasible schedule.
Suppose an algorithm returns a rational feasible schedule \(x\) satisfying
\(\displaystyle I(x)\ge\mathrm{OPT}-\epsilon.\)
On a yes instance, because \(\epsilon=\Delta/4\),
\(\displaystyle I(x)\ge V_0-\frac{5\Delta}{16},\)
and therefore
\(\displaystyle J(x)\ge I(x)-\frac{\Delta}{16}\ge V_0-\frac{3\Delta}{8}>V_0-\Delta.\)
On a no instance, every feasible output satisfies
\(\displaystyle J(x)\le V_0-2\Delta<V_0-\Delta.\)
Thus a single call to the proposed approximation algorithm, followed by the exact rational comparison
\(\displaystyle J(x)>V_0-\Delta,\)
decides Independent Set. This comparison requires neither exponential evaluation nor numerical simulation of the cascade.
The constructed society has exactly \(\tau=n+2\) positive-mass types and at most \(m=2|E|+n\) nonzero ordered transmission pairs. Its horizon is the unary constant \(H=1\).
Both \(N\) and \(D\) are polynomially bounded in \(n\). Every rational input has \(O(\log n)\) bits, including
\(\displaystyle \epsilon=\frac1{128D^2N^4}.\)
Hence the entire instance has polynomial encoding length. Any algorithm running in time polynomial in \(m,\tau,H,L\) also produces a polynomial-length output; evaluating \(J\) and performing the threshold comparison then takes polynomial time.
Such an algorithm would decide an \(\mathrm{NP}\)-complete problem in polynomial time. Therefore the requested additive-approximation search problem is \(\mathrm{NP}\text{-hard}\), and is not polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The claimed hardness result is correct. The proof addresses the specified population-mass dynamics, controls the complete cascade, and establishes a gap that applies to every feasible fractional intervention. I found no major or minor mathematical issues requiring repair.
The lemma is valid on the stated domain.
The resulting independent-set gap is also correct. A rounded set of size \(k\) in a no instance has at least one internal edge, giving value at most \(dk-2\). A smaller rounded set has value at most \(d(k-1)\le dk-2\), using precisely the hypothesis \(d\ge2\). In a yes instance, an independent set of size \(k\) attains the universal upper bound \(dk\).
The source problem is stated precisely: Independent Set on a simple undirected graph, with \(1\le k\le n\). The cited Clique hardness result applies through graph complementation, which preserves the vertex set and exchanges cliques with independent sets. This is a valid use of the classical result. [Karp, *Reducibility Among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf)
All constructed inputs satisfy the task’s restrictions:
The outgoing row sum of each vertex is indeed \(\theta d\): its graph transmissions contribute \(\theta d_i\), and its transmission into \(z\) contributes \(\theta(d-d_i)\). Both auxiliary rows vanish.
With one round and no initial influence, \(x_{t,1}^{1}=0\). Consequently, the stated constraints on \(x_t=x_{t,0}^{1}\) describe exactly the feasible interventions.
The expansion of \(A(x)\) is correct.
Each undirected edge contributes
\[
\theta x_i(\eta-x_j)+\theta x_j(\eta-x_i),
\]
where, following the required formatting, this expression is \(\theta x_i(\eta-x_j)+\theta x_j(\eta-x_i)\). Summing these contributions gives the stated degree term and the coefficient \(-2\theta\) on each internal product.
Transmission into \(z\) contributes \(\theta(\eta-x_z)\sum_i(d-d_i)x_i\). Combining the two expressions gives exactly
\[
A(x)=\theta\left(d\eta X-2\sum_{\{i,j\}\in E}x_ix_j-x_z\sum_i(d-d_i)x_i\right).
\]
Equivalently, in inline notation, \(A(x)=\theta\left(d\eta X-2\sum_{\{i,j\}\in E}x_ix_j-x_z\sum_i(d-d_i)x_i\right)\). Thus \(J(x)\) is rational and exactly evaluable from a rational schedule.
The wave estimate matches the dynamics as written. Susceptible mass only decreases, and \(1-e^{-v}\le v\) applies because every exposure is nonnegative.
Every recipient of a nonzero transmission has initial mass \(\eta\). Hence the weighted outgoing row sum is \(\eta d\) for vertex rows and zero for auxiliary rows. This justifies
\(\|a^{(\ell+1)}\|_1\le\rho\|a^{(\ell)}\|_1\).
The claimed bound \(\rho\le1/(32d)\le1/64\) follows from \(D\ge d\), \(\eta\le1\), and \(d\ge2\). Therefore the geometric bound on all waves after the first is valid.
Each cohort consists of newly influenced mass, so cohorts are disjoint. The expression \(I(x)=T+\sum_{\ell\ge1}\|a^{(\ell)}\|_1\) counts selected mass and cascade influence correctly.
For the first wave, the integral identity and quadratic error bound are correct. The bounds \(h_u\le\theta dT\) and \(A(x)\le\rho T\) justify every subsequent inequality.
Combining the estimates gives the stated asymmetric error interval. Its absolute value is bounded by \(2\theta^2d^2\), and substitution yields
\(2\theta^2d^2=\Delta d^2/(16D^2)\le\Delta/16\).
Thus the uniform approximation bound is established for every feasible intervention.
The normalized vertex vector satisfies the rounding lemma’s hypotheses even when intervention mass is assigned to auxiliary types.
The term involving \(x_z\) is nonpositive, so \(J(x)\le T+\Delta F(y)\) is valid. The yes witness selects exactly the budget and attains \(J(x)=V_0\). It is a rational feasible schedule.
For no instances, the rounding lemma bounds every fractional intervention, giving \(J(x)\le V_0-2\Delta\). Adding the uniform cascade error yields the stated upper bound on \(\mathrm{OPT}\).
The treatment of the supremum is rigorous: the lower bound uses an explicit rational witness, while the upper bound holds pointwise for every feasible rational schedule. Attainment of the supremum is unnecessary.
The threshold arithmetic is correct. On yes instances, the approximation guarantee implies \(J(x)\ge V_0-3\Delta/8>V_0-\Delta\). On no instances, feasibility alone implies \(J(x)\le V_0-2\Delta<V_0-\Delta\).
The decision procedure therefore needs only an exact rational comparison, avoiding any requirement to evaluate exponentials or simulate the limiting cascade.
The encoding argument is valid. The number of types and nonzero intensities is polynomially bounded, the horizon is constant, and all rational inputs have logarithmic bit length. In particular, \(\epsilon=1/(128D^2N^4)\) has polynomial encoding length despite the small additive gap.
A polynomial-time schedule algorithm has polynomial-length output, so evaluating the quadratic rational surrogate also takes polynomial time. The reduction establishes hardness of the requested search problem through one oracle call; it makes no unsupported NP-membership or NP-completeness claim about that problem.
No 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.