Answer: Polynomial-time solvable for \(m=1\); every instance satisfying the stated hypotheses admits the feedback \(U(t,y)=x^\star-y_r\).
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateFor the CAIPD model with external influence in form of (8), any agreement 0 ≤x⋆≤1 is reachable at t0 for arbitrary x0 by influencing a single controlled individual xc using the control input ur = −ϵ · sgn(e) + BTLkx IF e ̸= 0 BTLkx IF e = 0 (9) with ϵ > 0 and error defined as e = xc −x⋆. Then lim t→∞x(t; t0, x0, ur(t)) = x⋆1.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many types \(a\in T\) with rational masses \(\mu_a>0\), \(\sum_a\mu_a=1\), a symmetric interaction matrix \(q_{ab}\), parameters \(b>c>0\) and \(\beta>0\), initial states \(y_a(0)\in[0,1]\), a target \(x^\star\in[0,1]\), and a controllable type \(r\) with \(\mu_r>0\), define \(d_a=\sum_b\mu_bq_{ab}\), \(F_a(y)=-cd_ay_a+b\sum_b\mu_bq_{ab}y_b\), \(p_{ab}(y)=q_{ab}\sigma(\beta(F_b(y)-F_a(y)))\), and \(g_a(y)=d_a^{-1}\sum_b\mu_bp_{ab}(y)(y_b-y_a)\), where \(\sigma(z)=(1+e^{-z})^{-1}\). With the type-interaction graph connected and every \(d_a>0\), the dynamics are \(\dot y_a=g_a(y)+\mathbf{1}_{a=r}u_r(t)\), with the same signal applied to all members of type \(r\). Construct an admissible feedback \(u_r(t)\) that ensures \(\lim_{t\to\infty}y_a(t)=x^\star\) for every type \(a\).
A society is given by its support: the list of the \(\tau\) types \(T\) with positive binary rational masses \(\mu_a\), with \(\sum_a\mu_a=1\); \(\tau\) is the support size, not the number of possible types. Each type has one scalar state, so \(m=1\); let \(L\) be the total input bit length.
The input also contains a symmetric rational matrix \(q\in[0,1]^{\tau\times\tau}\), rational parameters \(b>c>0\), \(\beta>0\), initial states \(y(0)\in[0,1]^\tau\), a rational target \(x^\star\in[0,1]\), and a controlled type \(r\in T\). Initial states are rational. Diagonal entries of \(q\) describe interactions within a type and may be positive. The graph with edges \(\{a,j\}\) whenever \(a\ne j\) and \(q_{aj}>0\) is connected, and every \(d_a=\sum_{j\in T}\mu_jq_{aj}\) is positive.
Define \(F_a(y)=-cd_ay_a+b\sum_{j\in T}\mu_jq_{aj}y_j\), \(\sigma(z)=(1+e^{-z})^{-1}\), \(p_{aj}(y)=q_{aj}\sigma(\beta(F_j(y)-F_a(y)))\), and \(g_a(y)=d_a^{-1}\sum_{j\in T}\mu_jp_{aj}(y)(y_j-y_a)\).
Dynamics are \(\dot y_a=g_a(y)+\mathbf1_{\{a=r\}}U(t,y)\), with instantaneous state observation and the same signal applied to all members of type \(r\). An admissible feedback is measurable and locally bounded, permits either sign without a prescribed amplitude or energy budget, and gives a unique global absolutely continuous trajectory from the supplied initial state, satisfying the equation almost everywhere and remaining in \([0,1]^\tau\).
The synthesis problem asks for an admissible feedback ensuring \(\lim_{t\to\infty}y_a(t)=x^\star\) for every \(a\in T\), or a determination that none exists. Feedbacks have finite expression descriptions using rational constants, arithmetic, exponentials, and finitely many comparisons and branches; complexity measures construction of the description, not exact numerical evaluation of exponentials.
Is this feedback synthesis problem polynomial-time solvable in \(m,\tau,L\), or is it NP-hard?
For finite individual networks, arbitrary feasible agreement is reachable by controlling one individual under the connected-network condition implicit in the reachability argument; no computational complexity classification is given. [Verified finite-network result](https://www.researchgate.net/publication/279529290_Influencing_Social_Networks_An_Optimal_Control_Study).
No result settling the exact support-and-mass feedback synthesis problem was located in the searches.
Every instance satisfying the stated hypotheses admits the feedback
\(U(t,y)=x^\star-y_r\).
Its description can be constructed in polynomial time. The proof below applies to arbitrary positive masses, positive diagonal entries, and targets at either endpoint of the state interval.
Define
\[
\]
\(k_{aj}(y)=\dfrac{\mu_jq_{aj}}{d_a}\sigma\bigl(\beta(F_j(y)-F_a(y))\bigr).\)
Under the proposed feedback, the vector field is
\(H_a(y)=\sum_{j\in T}k_{aj}(y)(y_j-y_a)+\mathbf 1_{\{a=r\}}(x^\star-y_a).\)
The coefficients have three properties used below:
Diagonal terms contribute zero to the drift because \(y_a-y_a=0\). Their contributions to \(d_a\) and \(F_a\) are retained.
We use the following elementary fact about finitely many differentiable functions: their maximum is locally Lipschitz, and its right derivative equals the maximum of the derivatives among functions currently attaining that maximum. Indeed, functions strictly below the maximum remain below it for sufficiently small positive increments, and first-order expansions give the formula for the remaining functions. Thus, if every active derivative is nonpositive, the maximum is nonincreasing. The corresponding statement holds for minima.
Smoothness of \(H\) gives a unique local continuously differentiable solution. Along this solution, set
\(M(t)=\max\bigl(\{x^\star\}\cup\{y_a(t):a\in T\}\bigr)\)
and
\(\ell(t)=\min\bigl(\{x^\star\}\cup\{y_a(t):a\in T\}\bigr)\).
If \(y_a(t)=M(t)\), then \(y_j(t)-y_a(t)\leq 0\) for every \(j\), and \(x^\star-y_a(t)\leq 0\). Nonnegativity of the coefficients therefore gives \(H_a(y(t))\leq 0\). The constant function \(x^\star\) has derivative zero. Consequently, \(M\) is nonincreasing.
Similarly, if \(y_a(t)=\ell(t)\), every difference in its drift is nonnegative, so \(H_a(y(t))\geq 0\). Hence \(\ell\) is nondecreasing.
The supplied initial states and target belong to \([0,1]\). Therefore, throughout the maximal existence interval,
\(0\leq\ell(0)\leq\ell(t)\leq y_a(t)\leq M(t)\leq M(0)\leq 1.\)
The trajectory stays in the compact cube \([0,1]^\tau\). Since \(H\) is smooth on a neighborhood of this cube, the ODE continuation theorem extends the solution for all nonnegative times.
Finally, \(U(t,y)=x^\star-y_r\) is continuous and locally bounded, and along the trajectory \(|U(t,y(t))|\leq 1\). The unique global solution is continuously differentiable and thus absolutely continuous on every bounded time interval. The feedback is admissible.
Write \(z_a=y_a-x^\star\), and define the maximum target error
\(V(y)=\max_{a\in T}|z_a|.\)
We first prove that \(V(y(t))\) is nonincreasing. Express \(V\) as the maximum of the finitely many differentiable functions \(z_a\) and \(-z_a\). If a signed coordinate \(\varepsilon z_a\), with \(\varepsilon\in\{-1,1\}\), attains this maximum, then
\(\varepsilon z_a=V\) and \(\varepsilon z_j\leq V\) for every \(j\). Its derivative is
\(\varepsilon\dot z_a=\sum_{j\in T}k_{aj}(y)(\varepsilon z_j-V)-\mathbf 1_{\{a=r\}}V\leq 0.\)
The maximum rule from Section 2 proves the assertion. Since \(V\) is nonnegative, there exists a limit
\(R=\lim_{t\to\infty}V(y(t))\geq 0.\)
We show that \(R=0\).
By compactness, choose times \(t_n\to\infty\) such that \(y(t_n)\to\bar y\in[0,1]^\tau\). Let \(\bar y(s)\) be the closed-loop trajectory starting from \(\bar y\).
For every fixed \(s\geq 0\), continuous dependence on initial conditions gives
\(y(t_n+s)\to\bar y(s).\)
To check this application explicitly, both trajectories remain in the cube, where the smooth vector field has a finite Lipschitz constant \(K\). Gronwall’s inequality gives
\(\|y(t_n+s)-\bar y(s)\|_\infty\leq e^{Ks}\|y(t_n)-\bar y\|_\infty.\)
Continuity of \(V\) now yields
\(V(\bar y(s))=R\)
for every \(s\geq 0\).
Suppose, for contradiction, that \(R>0\). At time \(s=1\), choose a type \(a\) and sign \(\varepsilon\in\{-1,1\}\) satisfying
\(\varepsilon(\bar y_a(1)-x^\star)=R.\)
For every type \(j\) and every \(s\geq 0\),
\(\varepsilon(\bar y_j(s)-x^\star)\leq R.\)
Thus any coordinate attaining this signed value at time \(1\) has a differentiable local maximum there, and its derivative is zero.
In particular,
\(0=\sum_{j\in T}k_{aj}(\bar y(1))\bigl(\varepsilon(\bar y_j(1)-x^\star)-R\bigr)-\mathbf 1_{\{a=r\}}R.\)
Every summand is nonpositive. If \(a=r\), the right-hand side is strictly negative, a contradiction. Otherwise, for every neighbor \(j\) with \(q_{aj}>0\), strict positivity of \(k_{aj}\) forces
\(\varepsilon(\bar y_j(1)-x^\star)=R.\)
The same reasoning applies to every such neighbor: it also attains the global signed bound at the interior time \(1\), so its derivative is zero. Following a path in the connected off-diagonal interaction graph propagates this equality from \(a\) to \(r\).
At \(r\), the displayed derivative equation has nonpositive interaction terms and the strictly negative term \(-R\). This contradicts its derivative being zero. Therefore \(R=0\), proving
\(\lim_{t\to\infty}y_a(t)=x^\star\)
for every \(a\in T\).
The synthesis algorithm outputs the expression
\(U(t,y)=x^\star-y_r\).
It copies the supplied rational target and identifies the controlled coordinate. The description uses one subtraction, has length \(O(L+\log\tau)\), and can be constructed in polynomial time in the input bit length. It requires no evaluation of exponentials and no simulation of the dynamics.
Thus, for the stipulated scalar setting \(m=1\), feedback synthesis is polynomial-time solvable. Every promised instance is feasible. This classification concerns constructing the feedback description; it does not assert a polynomial bound on convergence time.
⟨structured verdict parsed — rendered above⟩
The output settles the synthesis problem in substance: the proposed feedback is admissible, the convergence argument is sound, and its description is constructible in polynomial time. There is one minor overstatement in the preliminary maximum lemma; its hypotheses hold for the trajectories actually used.
Substituting \(U(t,y)=x^\star-y_r\) into the supplied dynamics gives exactly the stated vector field \(H\).
The coefficient properties are correct:
Diagonal interaction terms vanish in the drift. Retaining diagonal contributions in \(d_a\) and \(F_a\) correctly respects the task.
Where: Section 2, “their maximum is locally Lipschitz,” stated for finitely many differentiable functions.
Issue: Differentiability alone does not imply local Lipschitz continuity, even for one function. For example, define
\(f(t)=(t-1)^2\sin((t-1)^{-2})\) for \(t\neq1\), and \(f(1)=0\). This function is differentiable everywhere, but its derivative is unbounded near \(1\), so it is not locally Lipschitz there.
The right-derivative formula for a finite maximum is nevertheless correct under the stated differentiability hypothesis. Moreover, every function to which the prover applies the lemma is continuously differentiable, because the trajectories solve a smooth ODE. Consequently, the local Lipschitz property needed in this proof does hold.
Severity: Minor.
Minimum clarification: Restrict the preliminary local Lipschitz assertion to continuously differentiable functions, matching its actual applications.
Smoothness of \(H\) supplies the local existence and uniqueness hypotheses: \(H\) is defined on the open domain \(\mathbb R^\tau\) and is locally Lipschitz there.
The maximum and minimum calculations are correct. At an active maximum, every interaction difference is nonpositive, and the control contribution is nonpositive. At an active minimum, both have the opposite sign. Including the constant \(x^\star\) in both extrema is legitimate and accounts for the control term.
The resulting bounds keep the trajectory inside \([0,1]^\tau\) throughout its maximal existence interval. The continuation theorem applies because this compact cube lies inside the domain of the smooth vector field. Hence the trajectory exists uniquely for all nonnegative times.
The feedback is continuous, locally bounded, and has an allowed finite expression. Along the trajectory, its magnitude is at most \(1\). The trajectory has the required absolute continuity and satisfies the equation everywhere, which is stronger than almost everywhere.
No restriction excluding endpoint targets is introduced.
The signed-coordinate calculation is exact. If \(\varepsilon z_a=V\), then every \(\varepsilon z_j-V\leq0\), and the control contribution is \(-V\) when \(a=r\). Thus every active derivative is nonpositive, establishing monotonicity of \(V\) and existence of its limit \(R\geq0\).
The limiting-trajectory construction is justified:
The contradiction for \(R>0\) is also valid. A signed coordinate attaining \(R\) at time \(1\) has a local maximum at an interior time and therefore derivative zero. Its derivative equation is a finite sum of nonpositive terms. Consequently, every positive interaction coefficient forces the corresponding neighbor to attain the same signed value.
This argument can be repeated along a finite path to \(r\). Symmetry of \(q\) and connectedness of the off-diagonal graph ensure that every required coefficient along that path is positive. At \(r\), the additional term \(-R\) makes the derivative strictly negative, contradicting its being zero.
For \(\tau=1\), the initial maximizing coordinate is already \(r\), so the same contradiction applies immediately. Positive diagonal entries and endpoint targets cause no failure.
Thus the argument establishes convergence of every coordinate to \(x^\star\).
The algorithm outputs the supplied rational target minus the controlled coordinate. Copying that rational and encoding the coordinate index requires polynomial time and polynomial description length in the supplied input length.
This resolves every promised instance in the stipulated setting \(m=1\). It requires neither exponential evaluation during construction nor a polynomial convergence-time bound. The output correctly distinguishes these matters.
The only necessary revision is the hypothesis wording of the preliminary maximum lemma; no additional convergence 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.