Answer: The stated continuous opinion-shaping decision problem is in $\mathrm{P}$.
Lemma 3.6 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateIf the mean opinion dynamics is stable, then the steady state average opinion of the non- control nodes is given by lim t→∞EHt [x ∗ Ic (t)] = I −A1ΛIc ω −1 αIc + A2 η+ I −η− I , (12) where ΛIc = diag h I −B1 ν i−1 ηIc and B1 = diag([bv]v ∈Ic ). Eq. (15) is equivalent to, (A1Λ1 −ωI)xIc + A2 η+ I −η− I + ωαIc = 0 (13) where xIc = limt→∞EHt [x ∗ Ic (t)]. In terms of S, the one-hot representation of I, Eq.
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\), a fixed set of control types \(I\), stable per-capita organic posting rates \(\lambda_s\), baseline opinions \(\alpha_t\), block influence coefficients \(W_{ts}\), costs \(c_s\), and budget \(C\), choose control-post rates \(h_s^+,h_s^-\ge 0\) for \(s\in I\) and steady-state means \(x_t\) for \(t\notin I\) to maximize \(-\sum_{t\notin I}\mu_t x_t\), subject to \(\sum_{s\in I}\mu_s c_s(h_s^++h_s^-)\le C\) and \(0=\omega(\alpha_t-x_t)+\sum_{s\notin I}W_{ts}\mu_s\lambda_s x_s+\sum_{s\in I}W_{ts}\mu_s(h_s^+-h_s^-)\) for each \(t\notin I\).
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_{t\in T}\mu_t=1\). The support size is not the number of possible types.
Input includes a fixed control set \(I\subseteq T\), with \(O=T\setminus I\ne\varnothing\), and \(m=|O|\). All numerical inputs are binary rationals: decay \(\omega>0\), constant per-capita organic posting rates \(\lambda_s\ge0\), baseline opinions \(\alpha_t\in\mathbb R\), signed influence coefficients \(W_{ts}\in\mathbb R\), per-post costs \(c_s\ge0\), budget \(C\ge0\), and threshold \(q\in\mathbb R\).
Promise mean stability: every eigenvalue of \(D=(W_{ts}\mu_s\lambda_s)_{t,s\in O}-\omega\operatorname{Id}_m\) has strictly negative real part.
Control type \(s\in I\) posts sentiments \(+1\) and \(-1\) at chosen constant per-capita rates \(h_s^+,h_s^-\ge0\); it contributes no organic posts. Non-control steady-state means \(x_t\in\mathbb R\) have no imposed opinion bounds.
Feasible choices satisfy \(\sum_{s\in I}\mu_sc_s(h_s^++h_s^-)\le C\) and, for every \(t\in O\), \(0=\omega(\alpha_t-x_t)+\sum_{s\in O}W_{ts}\mu_s\lambda_sx_s+\sum_{s\in I}W_{ts}\mu_s(h_s^+-h_s^-)\).
The decision problem asks whether a feasible choice achieves \(-\sum_{t\in O}\mu_tx_t\ge q\). Let \(L\) be the total binary input length; express running times in \(m,\tau,L\), and \(|I|\).
Is this continuous opinion-shaping decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For finite agents, stable mean dynamics admit a steady-state characterization by linear balance equations; fixed-control-set utility maximization under per-post budget constraints is also formulated, without a complexity classification in the anchor. [Source](https://www.ifaamas.org/Proceedings/aamas2018/pdfs/p1336.pdf)
No result addressing exactly the support-and-mass problem above was located in the search.
The stated continuous decision problem is in $\mathrm{P}$. In fact, its optimum has an explicit formula: either a zero-cost control makes the objective unbounded above, or the entire budget can be assigned to one control type with the best utility gain per unit cost.
The proof uses the fixed control set and the given balance equations directly.
Write $k=|I|$, so $\tau=m+k$. Define
$$
A=(W_{ts}\mu_s\lambda_s)_{t,s\in O},
\qquad
M=\omega\operatorname{Id}_m-A,
\qquad
G=(W_{ts}\mu_s)_{t\in O,\ s\in I}.
$$
Let $p=(\mu_t)_{t\in O}$ and $\alpha=(\alpha_t)_{t\in O}$, both column vectors.
Since $M=-D$, the stability promise implies that $M$ is invertible: otherwise $0$ would be an eigenvalue of $D$, contradicting its strictly negative real part.
For each control type, define its net posting rate
$$
u_s=h_s^+-h_s^-.
$$
The balance equations become
$$
Mx=\omega\alpha+Gu.
$$
Consequently, every choice of finite rates determines exactly one steady-state vector,
$$
x=M^{-1}(\omega\alpha+Gu).
$$
There are no imposed opinion bounds, so this vector introduces no additional feasibility condition.
Solve the single adjoint system
$$
M^{\mathsf T}y=p.
$$
Then $p^{\mathsf T}M^{-1}=y^{\mathsf T}$, and the utility equals
$$
-p^{\mathsf T}x
=
-\omega y^{\mathsf T}\alpha-y^{\mathsf T}Gu
=
b+\sum_{s\in I}a_su_s,
$$
where
$$
b=-\omega y^{\mathsf T}\alpha,
\qquad
a_s=-\mu_s\sum_{t\in O}y_tW_{ts}.
$$
All these coefficients are rational.
Define the effective cost
$$
d_s=\mu_sc_s\ge0.
$$
A vector $u\in\mathbb R^k$ is induced by feasible posting rates if and only if
$$
\sum_{s\in I}d_s|u_s|\le C.
$$
For necessity, nonnegativity of the posting rates gives
$$
|h_s^+-h_s^-|\le h_s^++h_s^-.
$$
Multiplying by $d_s$ and summing proves the required inequality.
For sufficiency, set
$$
h_s^+=\max\{u_s,0\},
\qquad
h_s^-=\max\{-u_s,0\}.
$$
These rates have difference $u_s$ and sum $|u_s|$, so they satisfy the original budget constraint.
Thus the problem is exactly whether some $u$ satisfies
$$
\sum_{s\in I}d_s|u_s|\le C,
\qquad
b+\sum_{s\in I}a_su_s\ge q.
$$
Suppose some $s\in I$ satisfies
$$
d_s=0,
\qquad
a_s\ne0.
$$
For any $R\ge0$, choose
$$
u_s=\operatorname{sgn}(a_s)R,
\qquad
u_r=0\quad(r\ne s).
$$
Its cost is zero and its utility is $b+|a_s|R$. Hence the utility is unbounded above, and every finite threshold $q$ is attainable, including when $C=0$.
Explicitly, the rational choice
$$
R=\max\left\{0,\frac{q-b}{|a_s|}\right\}
$$
already attains the threshold.
Assume
$$
d_s=0\ \Longrightarrow\ a_s=0.
$$
Define
$$
\rho=
\max\left(
\{0\}\cup
\left\{\frac{|a_s|}{d_s}:s\in I,\ d_s>0\right\}
\right).
$$
This definition includes $I=\varnothing$.
For every feasible $u$,
$$
\sum_{s\in I}a_su_s
\le
\sum_{s\in I}|a_s|\,|u_s|
\le
\rho\sum_{s\in I}d_s|u_s|
\le
\rho C.
$$
The second inequality also holds for zero-cost types because their coefficients vanish. Therefore, every feasible utility is at most $b+C\rho$.
This bound is attained:
$$
u_{s^\star}
=
\operatorname{sgn}(a_{s^\star})\frac{C}{d_{s^\star}},
\qquad
u_s=0\quad(s\ne s^\star).
$$
Its cost is $C$, and its utility is $b+C\rho$.
Consequently, in Case B the answer is exactly
$$
\boxed{b+C\rho\ge q}.
$$
The optimum is attained, so equality at the threshold causes no difficulty.
Constructing $M$, solving $M^{\mathsf T}y=p$, computing all coefficients, and selecting the best ratio require
$$
O\!\left(m^3+m|I|+\tau\right)
$$
rational arithmetic operations using Gaussian elimination. Reading the input additionally takes $O(L)$ bit operations. To establish membership in $\mathrm{P}$, we must also bound the integer sizes used by an exact implementation.
Here is a conservative explicit bit-time bound.
Let $Q$ be the product of the positive denominators of all input rationals. Its binary length is $O(L)$. Each entry of $M$ is a difference between an input rational and a product of three input rationals, whose denominator divides $Q$. Thus
$$
H=QM^{\mathsf T},
\qquad
r=Qp
$$
are an integer matrix and integer vector, with entries of binary length $O(L)$.
Since $H$ is nonsingular, Cramer’s rule gives
$$
y_j=\frac{\det H_j}{\det H},
$$
where $H_j$ replaces column $j$ of $H$ by $r$. Hadamard’s inequality bounds the binary lengths of these determinants, and of all their minors, by
$$
O\!\left(m\bigl(L+\log(m+1)\bigr)\right).
$$
Use pivoted fraction-free elimination to compute these $m+1$ determinants. This standard exact determinant algorithm takes $O(m^3)$ integer arithmetic operations per determinant; its intermediate entries are signed minors, and its divisions are exact. It applies to both singular and nonsingular integer matrices, so it also handles any singular $H_j$. Hence the total determinant computation takes $O(m^4)$ such operations on integers of the bounded length above.
For completeness, subsequent coefficient sums also retain polynomial length. Write each input rational $v$ as $\widehat v/Q$, and let
$$
\Delta=\det H,
\qquad
z_j=\det H_j.
$$
Then
$$
b=
-\frac{\widehat\omega\sum_{t\in O}z_t\widehat\alpha_t}
{\Delta Q^2},
\qquad
a_s=
-\frac{\widehat\mu_s\sum_{t\in O}z_t\widehat W_{ts}}
{\Delta Q^2},
\qquad
d_s=\frac{\widehat\mu_s\widehat c_s}{Q^2}.
$$
These formulas use common denominators. Their numerators and denominators have binary length
$$
O\!\left(m\bigl(L+\log(m+1)\bigr)\right).
$$
All signs, ratios, and the final threshold can therefore be compared exactly by cross multiplication with integers of that same asymptotic length.
Using schoolbook integer multiplication and division yields the explicit bit-time upper bound
$$
O\!\left(
L+
\bigl(m^4+m|I|+\tau\bigr)
m^2\bigl(L+\log(m+1)\bigr)^2
\right).
$$
This bound is conservative but polynomial. No expansion into individual agents or unlisted possible types is involved.
The algorithm need not test stability: it uses the input promise to obtain invertibility.
The promised problem is polynomial-time solvable, with the exact decision rule proved above. The cited paper’s Equation (13) gives the related finite-agent linear balance characterization, and Equation (18) gives a per-post budget constraint; the classification here follows from the specified support-and-mass equations. [De, Bhattacharya, and Ganguly, *Shaping Opinion Dynamics in Social Networks*](https://www.ifaamas.org/Proceedings/aamas2018/pdfs/p1336.pdf).
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated decision problem correctly. The reduction, optimization formula, and polynomial bit-time bound are valid. No major or minor issues were found.
The argument addresses the problem as stated: the control set is fixed, input size is measured by the listed support and binary encoding, and non-control opinions have no imposed bounds.
It does not substitute the number of individual agents for the support size or optimize over the choice of control set. Those distinctions are essential to the conclusion.
The promise $O\ne\varnothing$ ensures $m\ge1$. The proof also explicitly handles $I=\varnothing$.
The definitions of $A$, $M$, and $G$ have the correct dimensions and mass factors. Rearranging the original balance equations gives exactly
$$ Mx=\omega\alpha+Gu. $$
Since $M=-D$, singularity of $M$ would give a zero eigenvalue of $D$, contradicting the stability promise. Thus the use of $M^{-1}$ is justified.
Every finite choice of posting rates consequently determines a unique finite steady-state vector. Because the task imposes no opinion bounds, eliminating $x$ adds no feasibility restriction.
The adjoint identity is correct:
$$ M^{\mathsf T}y=p \quad\Longrightarrow\quad y^{\mathsf T}=p^{\mathsf T}M^{-1}. $$
Substitution gives the stated utility coefficients, including their signs:
$$ b=-\omega y^{\mathsf T}\alpha, \qquad a_s=-\mu_s\sum_{t\in O}y_tW_{ts}. $$
All coefficients are rational because the nonsingular linear system has rational entries.
Both directions of the claimed equivalence are established.
For necessity, nonnegative posting rates satisfy
$$ |h_s^+-h_s^-|\le h_s^++h_s^-. $$
Multiplication by $d_s\ge0$ and summation preserve the inequality, including when some costs vanish.
For sufficiency, the proposed positive and negative parts are nonnegative, have difference $u_s$, and have total posting rate $|u_s|$. They therefore satisfy precisely the original budget constraint.
The resulting optimization problem is equivalent to the original decision problem, with no loss from simultaneous positive and negative posting.
If $d_s=0$ and $a_s\ne0$, the proposed direction has zero cost and utility
$$ b+|a_s|R. $$
This establishes unbounded utility above. The explicit choice of $R$ is finite, nonnegative, and rational, and attains every input threshold $q$. Thus the proof correctly distinguishes unbounded optimization from attainment of a finite decision threshold.
The argument remains valid when $C=0$.
Under the assumption that every zero-cost control has zero utility coefficient, the definition of $\rho$ is valid even if there are no positive-cost controls.
Each inequality in the upper-bound chain is justified. In particular, zero-cost coordinates contribute zero to both the utility estimate and the weighted cost estimate.
Attainment is also established correctly:
The latter construction also works when $C=0$, yielding $u=0$. Equality at the threshold is correctly accepted.
Therefore the stated decision rule is exact.
Constructing the relevant matrix takes $O(m^2)$ rational operations. Gaussian elimination takes $O(m^3)$, and computing all control coefficients takes $O(m|I|)$. The remaining work is covered by $O(\tau)$.
Thus the stated rational-operation bound
$$ O\!\left(m^3+m|I|+\tau\right) $$
is valid. This count describes the Gaussian-elimination implementation; the subsequent, more conservative bit-time analysis uses a separate determinant implementation. These are compatible claims.
The denominator-clearing argument is valid. The product $Q$ has binary length $O(L)$. Each product forming an entry of $M$ uses the denominators of its input factors, so its denominator divides $Q$. Consequently, $H$ and $r$ are integral, with entry lengths $O(L)$.
Cramer’s rule applies because $H$ is nonsingular. Replacement matrices $H_j$ may be singular, which merely makes the corresponding numerator determinant zero.
The determinant and minor length bound
$$ O\!\left(m\bigl(L+\log(m+1)\bigr)\right) $$
is consistent with Hadamard’s inequality for integer matrices of the stated dimensions and entry sizes.
The stated properties of pivoted fraction-free determinant computation are applicable to these integer matrices: exact divisions and pivot handling permit determinant computation, including detection of singular replacement matrices. Temporary multiplication and subtraction operands remain within the same asymptotic bit-length bound.
The common-denominator formulas for $b$, $a_s$, and $d_s$ are algebraically correct. Their sums and products retain the claimed polynomial lengths. Exact sign checks, ratio comparisons, and threshold comparisons can therefore use cross multiplication with polynomial-size integers; no floating-point accuracy assumption is needed.
The resulting schoolbook-arithmetic bound
$$ O\!\left( L+ \bigl(m^4+m|I|+\tau\bigr) m^2\bigl(L+\log(m+1)\bigr)^2 \right) $$
is a valid conservative polynomial upper bound. Denominator preparation and construction of the relevant integer entries fit within this bound.
The algorithm may rely on the stability promise without testing stability. The proof requires only its consequence that $M$ is invertible.
The source attribution is accurate: Equation $13$ gives the related finite-agent steady-state balance equation, and Equation $18$ gives the posting-cost budget constraint. These references provide context; the complexity classification follows independently from the supplied equations. [Cited paper](https://www.ifaamas.org/Proceedings/aamas2018/pdfs/p1336.pdf)
No additional clarification or mathematical repair is required. The proof establishes polynomial-time solvability of the promised support-and-mass decision problem.
⟨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.