Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 3 — class: hardness
Given a finite type set \(T\), positive rational masses \(\mu_t\) summing to \(1\), rational internal opinions \(s_t\in[-1,1]\), a rational signed interaction kernel \(K_{tu}\), and a rational intervention share \(\beta\in[0,1]\), choose shielded masses \(x_t\) with \(0\le x_t\le\mu_t\) and \(\sum_t x_t=\beta\). For each type, let the expressed opinion of its unshielded mass satisfy \(y_t=[s_t+\sum_u K_{tu}(x_us_u+(\mu_u-x_u)y_u)]/[1+\sum_u\mu_u|K_{tu}|]\). Find \(x\) maximizing the population’s average expressed opinion \(\sum_t[x_ts_t+(\mu_t-x_t)y_t]\), with running time measured in the type count and input bit length.
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) counts supported types, not all possible types.
Each type has a rational internal opinion \(s_t\in[-1,1]\). A directed signed interaction kernel has rational entries \(K_{tu}\in[-1,1]\), with no symmetry requirement; diagonal entries describe interactions within a type.
Given a rational intervention share \(\beta\in[0,1]\), choose real shielded masses \(x_t\in[0,\mu_t]\) satisfying \(\sum_t x_t=\beta\). Shielded individuals express \(s_t\) and remain influential on others.
For each feasible \(x\), define \(y\in[-1,1]^T\) as the unique solution of \(y_t=\frac{s_t+\sum_{u\in T}K_{tu}[x_us_u+(\mu_u-x_u)y_u]}{1+\sum_{u\in T}\mu_u|K_{tu}|}\). When \(x_t=\mu_t\), \(y_t\) is only an auxiliary variable.
The population average is \(F(x)=\sum_{t\in T}[x_ts_t+(\mu_t-x_t)y_t]\). The exact threshold problem asks, given a binary rational \(q\), whether some feasible \(x\) satisfies \(F(x)\ge q\).
Is this continuous shielding threshold problem in \(\mathrm{P}\), with running time polynomial in \(\tau\) and total input bit length \(L\), or is it \(\mathrm{NP}\)-hard? There is no separate \(m\) parameter in this model.
For finite directed signed networks, maximizing the equilibrium opinion sum by shielding exactly a prescribed number of individuals at their internal opinions is NP-hard ([source](https://www.ijcai.org/proceedings/2020/0174.pdf)).
No complexity classification for exactly this distribution-based mass-splitting problem was located in the literature search.
The continuous shielding threshold problem is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions. This holds even when every internal opinion is \(1\), every kernel entry is nonpositive, and all input numbers are dyadic rationals.
Consequently, an algorithm polynomial in \(\tau\) and \(L\) would imply \(\mathrm{P}=\mathrm{NP}\). The proof below directly handles arbitrary real mass splits; the [finite-network hardness result](https://www.ijcai.org/proceedings/2020/0174.pdf) provides background.
Let \(A\) be the adjacency matrix of a nonempty simple undirected graph, and let \(\omega\) be its clique number. Define \(M_r=1-1/r\) for positive integers \(r\).
We will use the identity
\(\displaystyle \max_{\substack{p_i\ge 0\\ \sum_i p_i=1}}p^{\mathsf T}Ap=M_\omega.\)
Here is a proof. Suppose two nonadjacent vertices \(u,v\) both have positive weights. Holding their combined weight and all other weights fixed, the objective is affine in the weight assigned to \(u\): there are no diagonal terms and \(A_{uv}=0\). Moving their entire combined weight to one endpoint therefore does not decrease the objective and reduces its support.
Repeating this operation produces a vector supported on a clique of size \(r\le\omega\). On that support,
\(\displaystyle p^{\mathsf T}Ap=1-\sum_i p_i^2\le 1-\frac1r\le M_\omega,\)
where the first inequality follows from Cauchy–Schwarz. Uniform weights on a maximum clique attain \(M_\omega\), proving the identity.
By homogeneity, for any nonnegative vector \(w\) with total weight \(S\),
\(\displaystyle w^{\mathsf T}Aw\le S^2M_\omega.\)
This includes \(S=0\).
We reduce from CLIQUE, restricted to instances with at least two vertices and target size \(k\) satisfying \(2\le k\le |V|\). This restriction remains \(\mathrm{NP}\)-complete because the excluded cases are immediately decidable.
Pad the graph with isolated vertices until its number \(n\) of vertices is a power of two. This increases its size by less than a factor of two and preserves its clique number. Write \(A\) for the padded graph’s adjacency matrix and \(\deg(i)\) for its degrees.
Construct \(n+1\) supported types, indexed by \(0,1,\ldots,n\). Set
\(\displaystyle W=\frac1{2n},\qquad \varepsilon=\frac1{4n},\qquad \mu_0=\frac12,\qquad \mu_i=W\quad(1\le i\le n).\)
These masses are positive and sum to one. Set every internal opinion to \(s_i=1\), and set the intervention share to
\(\displaystyle \beta=1-W.\)
For each graph vertex define
\(\displaystyle h_i=\frac{\varepsilon\bigl(n-1-\deg(i)\bigr)}n.\)
The kernel is
\(\displaystyle K_{00}=-1,\qquad K_{0j}=0\quad(1\le j\le n),\)
\(\displaystyle K_{i0}=-h_i,\qquad K_{ij}=-\varepsilon A_{ij}\quad(1\le i,j\le n).\)
Since \(0\le h_i\le\varepsilon\le1\), every kernel entry belongs to \([-1,1]\).
For every vertex type \(i\), its absolute interaction total is the same:
\(\displaystyle \sum_{u=0}^n\mu_u|K_{iu}|=\frac{h_i}{2}+\frac{\varepsilon\deg(i)}{2n}=\frac{\varepsilon(n-1)}{2n}=:D.\)
Define
\(\displaystyle d=1+D,\qquad c=\frac{2D}{d},\qquad a=\frac{\varepsilon}{d}.\)
The common value \(D\) is the purpose of the padding interactions with type \(0\).
Write the unshielded masses as \(w_i=\mu_i-x_i\). Feasibility is equivalent to
\(\displaystyle 0\le w_i\le\mu_i,\qquad \sum_{i=0}^n w_i=W.\)
Write \(r_i=1-y_i\). Since every internal opinion is \(1\), the aggregate expressed mass of type \(i\) is
\(\displaystyle x_i+w_i y_i=\mu_i-w_i r_i,\)
and therefore
\(\displaystyle F=1-\sum_{i=0}^n w_i r_i.\)
For completeness, the equilibrium indeed lies in the prescribed cube. For any feasible shielding vector, the equilibrium update maps \([-1,1]^T\) into itself: each aggregate expressed mass has absolute value at most its type mass. If \(D_t=\sum_u\mu_u|K_{tu}|\), its Lipschitz constant in the supremum norm is at most
\(\displaystyle \max_t\frac{\sum_u w_u|K_{tu}|}{1+D_t}\le\max_t\frac{D_t}{1+D_t}\le\frac12.\)
The last inequality uses \(D_t\le\sum_u\mu_u=1\). Thus the contraction mapping theorem gives a unique equilibrium in the cube. In particular, \(r_i\ge0\).
Substituting \(\mu_u-w_u r_u\) into the equilibrium equations gives
\(\displaystyle (1+D_t)r_t=2D_t+\sum_u K_{tu}w_u r_u,\)
because all kernel entries are nonpositive.
For type \(0\), whose absolute interaction total is \(1/2\), this yields
\(\displaystyle r_0=\frac1{3/2+w_0}.\)
Consequently \(r_0\ge1/2\), since \(w_0\le\mu_0=1/2\).
For vertex types, the exact identities are
\(\displaystyle r_i=c-a\sum_{j=1}^n A_{ij}w_jr_j-\frac{h_i}{d}w_0r_0.\)
All subtracted terms are nonnegative, so
\(\displaystyle 0\le r_i\le c\qquad(1\le i\le n).\)
Define
\(\displaystyle B=1-cW,\qquad \lambda=acW^2>0,\qquad Q(w)=\sum_{i,j=1}^n A_{ij}w_iw_j.\)
We prove an upper bound for every feasible split and a matching lower bound up to a controlled error.
Let \(S=\sum_{i=1}^n w_i=W-w_0\). The exact equilibrium identities give
\(\displaystyle F=B+a\sum_{i,j=1}^n A_{ij}w_iw_jr_j+w_0\left(c-r_0+\frac{r_0}{d}\sum_{i=1}^n h_iw_i\right).\)
Using \(r_j\le c\) and \(h_i\le\varepsilon\), we obtain
\(\displaystyle F\le B+acQ(w)+w_0\bigl[c-r_0(1-aW)\bigr].\)
To verify the sign of the last term, set
\(\displaystyle H=8n^2+n-1.\)
Direct substitution gives
\(\displaystyle c=\frac{2(n-1)}H,\qquad a=\frac{2n}H,\qquad aW=\frac1H.\)
Also, \(D<\varepsilon/2\), so \(c<\varepsilon\le1/8\), while \(aW<1/(8n^2)\le1/32\). Hence
\(\displaystyle c-r_0(1-aW)\le\frac18-\frac12\left(1-\frac1{32}\right)<0.\)
The quadratic clique identity now implies
\(\displaystyle F\le B+acQ(w)\le B+acS^2M_\omega\le B+\lambda M_\omega.\)
This bound covers every feasible real vector, including those leaving type \(0\) partially unshielded.
Choose a maximum clique and assign unshielded mass \(W/\omega\) to each of its vertices, zero to all other vertex types, and \(w_0=0\). This is feasible because \(W/\omega\le W=\mu_i\). It satisfies
\(\displaystyle Q(w)=W^2M_\omega.\)
When \(w_0=0\), the equilibrium identities and \(r_j\le c\) give
\(\displaystyle r_i\ge c-ac\sum_j A_{ij}w_j\ge c(1-aW).\)
Consequently, for this explicit feasible split,
\(\displaystyle F=B+a\sum_{i,j}A_{ij}w_iw_jr_j\ge B+\lambda(1-aW)M_\omega\ge B+\lambda(M_\omega-aW).\)
The final inequality uses \(0\le M_\omega\le1\).
Thus we have proved:
For the CLIQUE target \(k\), define
\(\displaystyle \Delta=M_k-M_{k-1}=\frac1{k(k-1)},\)
and the rational midpoint
\(\displaystyle q_* = B+\frac{\lambda}{2}(M_k+M_{k-1}).\)
Since \(k\le n\),
\(\displaystyle \Delta\ge\frac1{n^2},\qquad aW=\frac1H<\frac1{8n^2}\le\frac{\Delta}{8}.\)
If \(\omega\ge k\), the clique witness constructed above satisfies
\(\displaystyle F\ge B+\lambda(M_k-aW)=q_*+\lambda\left(\frac{\Delta}{2}-aW\right)>q_*.\)
If \(\omega\le k-1\), every feasible split satisfies
\(\displaystyle F\le B+\lambda M_{k-1}=q_*-\frac{\lambda\Delta}{2}.\)
We can make the input threshold dyadic while preserving this separation. Set
\(\displaystyle R=1024n^6,\qquad q=\frac{\lfloor Rq_*\rfloor}{R}.\)
Because \(n\) is a power of two, \(R\) is a power of two. Also,
\(\displaystyle \lambda=\frac{n-1}{nH^2}\ge\frac1{162n^4},\)
using \(n-1\ge n/2\) and \(H\le9n^2\). Therefore
\(\displaystyle \frac{\lambda\Delta}{2}\ge\frac1{324n^6}>\frac1R.\)
Rounding gives \(q_*-1/R<q\le q_*\). It follows that:
Thus the graph contains a clique of size at least \(k\) if and only if the constructed society admits a feasible shielding vector satisfying \(F\ge q\).
The constructed society has exactly \(\tau=n+1\) supported types. Since \(n\) is a power of two, all masses, kernel entries, internal opinions, the intervention share, and the rounded threshold are dyadic rationals.
Every entry has bit length \(O(\log n)\). The rational arithmetic used to compute \(q_*\) and its rounded threshold also involves only \(O(\log n)\)-bit integers. The complete society therefore has encoding length \(O(n^2\log n)\) and is constructible in polynomial time.
This completes the reduction and proves \(\mathrm{NP}\)-hardness for the exact continuous shielding threshold problem with the stated parameters \(\tau\) and \(L\).
⟨structured verdict parsed — rendered above⟩
The claimed NP-hardness result is proved. The reduction handles arbitrary real mass splits, gives a valid separating dyadic threshold, and has polynomial encoding size. I found no major or minor mathematical issues.
The supplied proof is valid.
For two positively weighted nonadjacent vertices, fixing their combined weight makes the quadratic objective affine in the allocation between them: the diagonal terms and their mutual interaction term vanish. Choosing an endpoint that maximizes this affine function does not decrease the objective and removes at least one vertex from the support. Thus the process terminates with support on a clique.
On a clique of size \(r\), the objective equals \(1-\sum_i p_i^2\). Cauchy–Schwarz gives \(\sum_i p_i^2\ge 1/r\), and \(r\le\omega\) gives the claimed upper bound. Uniform weights on a maximum clique attain it.
The homogeneous extension to nonnegative vectors of total weight \(S\) is correct. The separately included case \(S=0\) also holds.
Restricting CLIQUE to instances with at least two vertices and \(2\le k\le |V|\) preserves NP-completeness; the excluded cases are routinely decidable. Padding with isolated vertices preserves clique number because the original graph is nonempty, and increases the vertex count by less than a factor of two.
All constructed inputs satisfy the task’s requirements:
The common absolute interaction total is correctly computed:
\(h_i/2+\varepsilon\deg(i)/(2n)=\varepsilon(n-1)/(2n)=D\).
In particular, \(D>0\) because \(n\ge2\). Therefore \(a>0\), \(c>0\), and the later assertion \(\lambda>0\) is justified.
The change of variables \(w_i=\mu_i-x_i\) correctly converts feasibility into the stated box constraints and total unshielded mass \(W\). The identities for aggregate expression and \(F\) follow directly from \(r_i=1-y_i\).
The equilibrium update maps the cube into itself: each type’s aggregate expression has absolute value at most its mass, so the numerator has absolute value at most \(1+D_t\). Its supremum-norm Lipschitz constant is bounded by \(D_t/(1+D_t)\le1/2\). The cube is complete in this norm, so the contraction mapping theorem applies with all required hypotheses satisfied. This establishes the unique equilibrium and \(r_i\ge0\).
The rearranged equilibrium identity is correct. Because the kernel entries are nonpositive, \(\sum_u K_{tu}\mu_u=-D_t\), producing the constant term \(2D_t\).
For type \(0\), this gives \((3/2+w_0)r_0=1\), hence the displayed expression and \(r_0\ge1/2\).
For vertex types, the exact identity for \(r_i\) is also correct. Its subtracted terms are nonnegative, and the cube bound already supplies nonnegativity. Consequently, \(0\le r_i\le c\) is justified.
The displayed exact expression for \(F\) follows correctly by multiplying the vertex identities by \(w_i\), summing, and using \(S=W-w_0\).
Replacing \(r_j\) by \(c\) in the quadratic term preserves the upper-bound direction because its coefficients are nonnegative. Likewise, using \(h_i\le\varepsilon\) and \(S\le W\) yields the stated bound on the type \(0\) term.
The substitutions involving \(H\) are correct:
\(D=(n-1)/(8n^2)\), \(d=H/(8n^2)\), \(c=2(n-1)/H\), \(a=2n/H\), and \(aW=1/H\).
For \(n\ge2\), the bounds \(c<\varepsilon\le1/8\) and \(aW<1/(8n^2)\le1/32\) hold. Together with \(r_0\ge1/2\), they make the bracket multiplying \(w_0\) strictly negative. Dropping that term therefore gives a valid upper bound, including when \(w_0=0\).
The quadratic clique bound applies to the vertex masses, whose sum is \(S\). Since \(0\le S\le W\) and \(M_\omega\ge0\), the conclusion \(F\le B+\lambda M_\omega\) is valid for every feasible real vector.
The proposed witness is feasible: it assigns total mass \(W\), uses no unshielded mass at type \(0\), and assigns at most \(W=\mu_i\) to each vertex type. It attains \(Q(w)=W^2M_\omega\).
With \(w_0=0\), the exact identities and \(r_j\le c\) give the stated lower bound \(r_i\ge c(1-aW)\). Substitution into the exact expression for \(F\) preserves the inequality direction.
The final weakening to \(F\ge B+\lambda(M_\omega-aW)\) is justified by \(0\le M_\omega\le1\). This also covers an edgeless graph, where \(\omega=1\).
The witness need not be computed during the reduction: its role is to establish existence in yes-instances.
The gap calculation \(\Delta=1/[k(k-1)]\) is correct, including the boundary case \(k=2\).
Since \(k\le n\), the bounds \(\Delta\ge1/n^2\) and \(aW<\Delta/8\) hold. Thus the lower bound in yes-instances exceeds \(q_*\), while the upper bound in no-instances lies below \(q_*\) by \(\lambda\Delta/2\).
The rounding calculation is correct:
\(\lambda=(n-1)/(nH^2)\ge1/(162n^4)\),
using \(n-1\ge n/2\) and \(H\le9n^2\). Consequently,
\(\lambda\Delta/2\ge1/(324n^6)>1/(1024n^6)=1/R\).
Rounding downward changes the threshold by less than \(1/R\), which is smaller than the no-instance separation. Hence every no-instance still satisfies \(F<q\), while the yes-instance witness satisfies \(F>q_*\ge q\).
This proves the required equivalence for the non-strict target condition \(F\ge q\).
Because \(n\) is a power of two, the masses, kernel entries, intervention share, internal opinions, and rounded threshold are dyadic rationals. The quantities used to compute \(q_*\) involve integers with \(O(\log n)\) bits, including the factors depending on \(k\le n\).
There are \(O(n^2)\) kernel entries, each with \(O(\log n)\) encoding length. The asserted \(O(n^2\log n)\) total encoding size and polynomial construction time are valid.
The proof therefore establishes NP-hardness in the task’s parameters \(\tau\) and \(L\), with no separate population-size parameter. It does not claim NP membership, which is unnecessary for the requested hardness classification. The finite-network reference is background and supplies no essential step in this reduction.
No additional clarification or repair 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.