Answer: Exactly solvable in polynomial time.
Theorem 4.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe optimal solution to the OpinionMin problem is the set $T$ of $k$ nodes with the largest product of structure centrality and internal opinion. That is, for any node $i \in T$ and any node $j \in V \setminus T$, $ \rho_i s_i \geq \rho_j s_j$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\) with rational masses \(\mu_t\), innate opinions \(s_t\), roles \(r(t)\), and a rational nonnegative contact kernel \(K_{ru}\), let \(\nu_r=\sum_{t:r(t)=r}\mu_t\). Define \(H_{ru}=(1+\sum_v K_{rv}\nu_v)\mathbf{1}[r=u]-K_{ru}\nu_u\), and let the role equilibrium after intervention \(x\) satisfy \(Hz=\bar{s}(x)\), where \(\bar{s}_r(x)=\sum_{t:r(t)=r}(\mu_t-x_t)s_t/\nu_r\). For a population-share budget \(\alpha\), find \(x\) minimizing \(G(x)=\sum_r\nu_r z_r\), subject to \(0\le x_t\le\mu_t\) and \(\sum_t x_t=\alpha\).
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a binary-rational innate opinion \(s_t\in[0,1]\) and a role \(r(t)\in R=\{1,\ldots,m\}\); every role occurs. The input includes a binary-rational contact kernel \(K\in\mathbb{Q}_{\geq0}^{m\times m}\) and a binary-rational population-share budget \(0<\alpha\leq1\). Let \(L\) be the total input bit length.
An intervention chooses real masses \(0\leq x_t\leq\mu_t\) with \(\sum_{t\in T}x_t=\alpha\), changing the innate opinion of that mass of type \(t\) to zero. Population masses, roles, and contacts remain fixed.
Define \(\nu_r=\sum_{t:r(t)=r}\mu_t\), \(H_{ru}=(1+\sum_{v\in R}K_{rv}\nu_v)\mathbf{1}_{\{r=u\}}-K_{ru}\nu_u\), and \(\bar{s}_r(x)=\nu_r^{-1}\sum_{t:r(t)=r}(\mu_t-x_t)s_t\). The role-average equilibrium \(z\) is the unique solution of \(Hz=\bar{s}(x)\).
The optimization problem is to minimize \(G(x)=\sum_{r\in R}\nu_r z_r\) over feasible interventions; any minimizer is acceptable.
Is this continuous opinion-minimization problem solvable exactly in polynomial time in \(m,\tau,L\), or is it NP-hard?
For a finite unweighted directed network, selecting exactly \(k\) agents and setting their innate opinions to zero to minimize the average Friedkin–Johnsen equilibrium opinion has an exact \(O(n^3)\) algorithm, where \(n\) is the number of agents ([Sun and Zhang](https://arxiv.org/html/2306.16847v1)).
No result settling this exact support-encoded continuous formulation was identified in the literature search.
Theorem. The support-encoded continuous problem is exactly solvable in polynomial time in \(m,\tau,L\). There is an optimal rational intervention that fully treats some types, partially treats at most one type, and leaves the remaining types untreated.
The proof consists of reducing the objective to a linear function, proving a sorting rule, and verifying polynomial bit complexity.
1. Invertibility and positivity of the equilibrium operator.
Every role occurs and every type has positive mass, so \(\nu_r>0\) for every \(r\). Define \(a_{ru}=K_{ru}\nu_u\) for \(u\ne r\). Cancellation of the diagonal contact term gives
\[
\text{PLACEHOLDER}
\]
\( \displaystyle H_{rr}=1+\sum_{u\ne r}a_{ru},\qquad H_{ru}=-a_{ru}\quad(u\ne r). \)
Thus, for every vector \(y\),
\( \displaystyle (Hy)_r=y_r+\sum_{u\ne r}a_{ru}(y_r-y_u). \)
To prove invertibility, suppose \(Hy=0\) and choose \(r\) with \(|y_r|=\max_u|y_u|\). The row equation implies
\( \displaystyle \left(1+\sum_{u\ne r}a_{ru}\right)|y_r|\leq\sum_{u\ne r}a_{ru}|y_u|\leq\left(\sum_{u\ne r}a_{ru}\right)|y_r|. \)
Consequently \(y_r=0\), and hence \(y=0\). Therefore \(H\) is invertible.
We also have \(H^{-1}\geq0\) entrywise. Indeed, let \(Hy=b\) with \(b\geq0\). If a minimum coordinate \(y_r\) were negative, then
\( \displaystyle b_r=y_r+\sum_{u\ne r}a_{ru}(y_r-y_u)\leq y_r<0, \)
a contradiction. Applying this argument to each coordinate vector \(b\) proves the assertion.
Moreover, \((H^{-1})_{rr}>0\). For \(y=H^{-1}e_r\), we already know \(y\geq0\). If \(y_r=0\), its \(r\)-th equation would give
\( \displaystyle 1=(Hy)_r=-\sum_{u\ne r}a_{ru}y_u\leq0, \)
which is impossible.
These arguments require neither symmetry nor connectivity of the contact kernel.
2. Exact linearization of the objective.
Write \(\nu=(\nu_1,\ldots,\nu_m)^{\mathsf T}\), and compute the unique rational vector \(w\) satisfying
\( \displaystyle H^{\mathsf T}w=\nu. \)
Because \(w=H^{-\mathsf T}\nu\), the preceding positivity result implies
\( \displaystyle w_r=\sum_u(H^{-1})_{ur}\nu_u\geq(H^{-1})_{rr}\nu_r>0. \)
For every feasible intervention,
\( \displaystyle G(x)=\nu^{\mathsf T}H^{-1}\bar s(x)=w^{\mathsf T}\bar s(x)
=\sum_{t\in T}\frac{w_{r(t)}}{\nu_{r(t)}}(\mu_t-x_t)s_t. \)
Define the rational benefit per unit of intervention mass by
\( \displaystyle c_t=\frac{w_{r(t)}}{\nu_{r(t)}}s_t. \)
Then
\( \displaystyle G(x)=G(0)-\sum_{t\in T}c_tx_t,\qquad
G(0)=\sum_{t\in T}c_t\mu_t. \)
Here \(G(0)\) denotes the objective without intervention; it is a constant even when the zero intervention is infeasible for the specified budget. Thus the original minimization is exactly equivalent to
\( \displaystyle \max\left\{\sum_{t\in T}c_tx_t:\ 0\leq x_t\leq\mu_t,\ \sum_{t\in T}x_t=\alpha\right\}. \)
Crucially, every coefficient \(c_t\) is independent of \(x\), since population masses and contacts remain fixed.
3. An optimal intervention and its proof.
Order the types as \(t_1,\ldots,t_\tau\) so that
\( \displaystyle c_{t_1}\geq c_{t_2}\geq\cdots\geq c_{t_\tau}, \)
breaking ties arbitrarily.
Let
\( \displaystyle M_0=0,\qquad M_i=\sum_{h=1}^i\mu_{t_h}. \)
Since \(M_\tau=1\) and \(0<\alpha\leq1\), there is a least index \(j\) with \(M_j\geq\alpha\). Set
\( \displaystyle
x^*_{t_i}=
\begin{cases}
\mu_{t_i},&i<j,\\
\alpha-M_{j-1},&i=j,\\
0,&i>j.
\end{cases}
\)
Minimality of \(j\) gives \(M_{j-1}<\alpha\leq M_j\), so
\( \displaystyle 0<x^*_{t_j}\leq\mu_{t_j}. \)
All capacity constraints hold, and the coordinates sum to \(\alpha\). Hence \(x^*\) is feasible.
For optimality, take any feasible \(x\) and put \(\lambda=c_{t_j}\). Equal total intervention masses imply
\( \displaystyle
\sum_{i=1}^{\tau}c_{t_i}(x^*_{t_i}-x_{t_i})
=
\sum_{i=1}^{\tau}(c_{t_i}-\lambda)(x^*_{t_i}-x_{t_i}).
\)
Every term on the right is nonnegative:
Therefore
\( \displaystyle \sum_t c_tx^*_t\geq\sum_t c_tx_t, \)
and the linearization proves \(G(x^*)\leq G(x)\).
This covers ties, zero innate opinions, and \(\alpha=1\). In the last case, the construction returns \(x^*=\mu\).
4. Polynomial bit complexity.
An arithmetic-operation count alone would not establish exact polynomial-time solvability. We therefore bound the sizes of the rational numbers used.
Represent input rationals by binary numerators and positive denominators. Let \(D\) be the product of all input denominators. Because their encodings are included in \(L\),
\( \displaystyle \log_2D\leq L. \)
Every input denominator divides \(D\). Hence every \(\nu_r\) has denominator dividing \(D\), and every entry of \(H\) has denominator dividing \(D^2\).
Consequently the system for \(w\) is equivalent to the integer system
\( \displaystyle Aw=b,\qquad A=D^2H^{\mathsf T},\qquad b=D^2\nu. \)
Every input kernel entry is at most \(2^L\). Using \(\sum_r\nu_r=1\), we obtain
\( \displaystyle |H_{ru}|\leq1+2^L,\qquad 0<b_r\leq D^2. \)
Thus all entries of \(A\) and \(b\) have absolute value at most
\( \displaystyle U=2^{3L+2}. \)
For any \(k\)-by-\(k\) integer matrix with entries bounded by \(U\), Hadamard’s determinant inequality gives
\( \displaystyle |\det B|\leq(\sqrt{k}\,U)^k. \)
Its hypotheses hold because each row has Euclidean norm at most \(\sqrt{k}\,U\). Every determinant formed from at most \(m\) rows and columns of the augmented matrix therefore has bit length
\( \displaystyle O\bigl(m(L+\log m)\bigr). \)
Cramer’s rule now shows that each coordinate of \(w\), in reduced rational form, has polynomial bit length: both its numerator determinant and its nonzero denominator determinant obey this bound.
For completeness, \(w\) can also be *computed* using only polynomial-size intermediate values. Every principal submatrix of \(H\) remains strictly row diagonally dominant: deleting indices only decreases its off-diagonal absolute row sums. The invertibility argument in Section 1 applies to each such submatrix. Therefore every leading principal submatrix of \(A\) is invertible, and Gaussian elimination needs no pivot exchanges.
After eliminating an initial index set \(I=\{1,\ldots,k\}\), a remaining coefficient is the Schur-complement entry
\( \displaystyle
A_{ij}-A_{iI}A_{II}^{-1}A_{Ij}
=
\frac{\det\begin{pmatrix}A_{II}&A_{Ij}\\A_{iI}&A_{ij}\end{pmatrix}}
{\det A_{II}}.
\)
The equality follows by block elimination of the displayed matrix. The corresponding right-hand-side entry has the same formula with the last column replaced by \(b\).
Thus every reduced intermediate coefficient and right-hand-side entry has polynomial bit length by the determinant bound. Each elimination update uses a fixed number of rational arithmetic operations; reducing fractions after each update keeps their encodings polynomial. Back substitution also has polynomial bit complexity: the solution coordinates have the Cramer bound, and each partial sum contains at most \(m\) products of polynomial-size rationals. There are \(O(m^3)\) arithmetic operations, and integer arithmetic and greatest-common-divisor computations on polynomial-size integers take polynomial time.
Finally:
The entire algorithm runs in polynomial time in \(m,\tau,L\), with no expansion of the support into individual agents.
Conclusion. Solve one rational linear system, sort the resulting benefits per unit mass, and fill capacities in that order. This completely resolves the stated continuous formulation. The cited [Sun–Zhang paper](https://arxiv.org/html/2306.16847v1) establishes an exact cubic algorithm for the finite unweighted model; the proof here directly establishes both optimality and exact bit complexity for the support encoding.
⟨structured verdict parsed — rendered above⟩
Assessment: The prover resolves the stated support-encoded continuous problem. The linearization, sorting argument, and polynomial bit-complexity analysis are correct. There is one minor editorial issue and no mathematical blocking issue.
The proof addresses the precise intervention model in USER_TASK: intervention masses are real, types can be partially treated, and population masses, roles, and contacts remain fixed.
Every role occurs and every type has positive mass, so \(\nu_r>0\). All divisions by \(\nu_r\) are therefore legitimate. The construction uses only the listed support; it does not require expanding rational masses into individual agents.
The diagonal cancellation is correct:
\(H_{rr}=1+\sum_{u\ne r}K_{ru}\nu_u\).
The off-diagonal entries are correctly identified as \(-K_{ru}\nu_u\).
The maximum-absolute-coordinate argument proves that the real kernel of \(H\) is trivial. Since \(H\) is square, invertibility follows. Nonnegative contacts supply exactly the sign condition needed for both inequalities.
The minimum-coordinate argument correctly proves that \(Hy=b\), with \(b\geq0\), implies \(y\geq0\). Applying this to the coordinate vectors establishes entrywise nonnegativity of \(H^{-1}\).
The argument establishing strictly positive diagonal entries of \(H^{-1}\) is also correct: if the relevant coordinate were zero, its row equation could not equal \(1\).
These arguments cover a single role, zero contacts, self-contacts, and disconnected or asymmetric kernels.
Minor issue: The displayed “PLACEHOLDER” is an unfinished editorial token. The complete identity immediately following it supplies everything needed, so no mathematical step is missing.
The equation \(H^{\mathsf T}w=\nu\) has a unique rational solution because \(H\) is an invertible rational matrix.
The indexing in
\(w_r=\sum_u(H^{-1})_{ur}\nu_u\)
is correct. Nonnegativity of the inverse and strict positivity of its diagonal establish \(w_r>0\).
The substitution into \(G(x)\) correctly yields
\(G(x)=G(0)-\sum_t c_tx_t\),
where \(c_t=s_tw_{r(t)}/\nu_{r(t)}\). These coefficients are independent of the intervention.
Thus minimizing the original equilibrium objective is exactly equivalent to the stated linear maximization problem. The explanation of \(G(0)\) correctly handles the fact that the zero intervention is infeasible when \(\alpha>0\).
No gap occurs here.
Positive masses make the prefix sums strictly increasing. Since their final value is \(1\), the least index \(j\) exists for every permitted budget.
The inequalities
\(M_{j-1}<\alpha\leq M_j\)
correctly establish the capacity constraint for the split coordinate. The constructed intervention has total mass exactly \(\alpha\).
The optimality identity correctly subtracts
\(\lambda\sum_i(x^*_{t_i}-x_{t_i})=0\).
Every resulting term has the asserted sign:
Consequently the constructed intervention is optimal against every real feasible intervention, not merely against rational ones.
Ties and zero opinions cause no difficulty. If the budget equals a prefix sum, the split coordinate is fully treated. If \(\alpha=1\), all types are fully treated. The claim of at most one partially treated type is established.
The denominator and magnitude bounds check out.
The proof establishes exact polynomial running time, rather than merely a polynomial arithmetic-operation count.
The contextual claim about the finite unweighted model agrees with the abstract of the [Sun–Zhang paper](https://arxiv.org/html/2306.16847v1), which states an optimal algorithm with running time \(O(n^3)\). The continuous proof does not depend on transferring that result.
The only requested repair is to delete the stray “PLACEHOLDER” display in Section 1. No additional lemma, hypothesis, or mathematical argument 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.