Answer: Both decision problems are in \(\mathrm P\), with bit running time \(O(L+m\tau^2L^2)\).
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet (𝐺= (𝑉, 𝐸),𝜀,𝑥) be any instance of a 𝑑-dimen- sional HKS and let 𝐺= 𝐾𝑛 be the complete social network. Using uniform random asynchronous update steps, the expected convergence time to a 𝛿-stable state is at most O(𝑛3 𝑛2 + (𝜀/𝛿)2). To prove these results we extend the potential function used in [34]. The main ingredient for strongly improving the upper bound derived in [34] is to significantly tighten and generalize the proof by Etesami and Başar [34].
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a rational finite-support initial opinion distribution \(\mu_0\) on \(\mathbb{Q}^d\) and rational \(\varepsilon>\delta>0\), evolve \(\mu_t\) by \(\dot{\mu}_t=(F_{\mu_t})_\#\mu_t-\mu_t\), where \(F_\mu(x)\) is the mean opinion within distance \(\varepsilon\) of \(x\). Determine or approximate the first time \(T_\delta\) when every \(x,y\in\operatorname{supp}(\mu_t)\) with \(\|x-y\|_2\le\varepsilon\) also satisfies \(\|x-y\|_2\le\delta\), including whether \(T_\delta\) is infinite.
A society is given by its support: distinct opinion types \(a_1,\ldots,a_\tau\in\mathbb Q^m\), where \(m=d\ge1\), with positive binary rational masses \(p_i\) summing to \(1\); set \(\mu_0=\sum_i p_i\delta_{a_i}\). Here \(\tau\) is the initial support size, not the number of possible types. All opinions interact through a complete social network. The input also contains binary rationals \(\varepsilon>\delta>0\) and \(h\ge0\); \(L\) is the total input bit length.
For the closed Euclidean ball \(B_\varepsilon(x)\), define \(F_\mu(x)=\mu(B_\varepsilon(x))^{-1}\int_{B_\varepsilon(x)}y\,d\mu(y)\) on \(\operatorname{supp}\mu\). Thus all mass at the opinion itself is included. Evolve probability measures at unit update rate by \(\dot\mu_t=(F_{\mu_t})_\#\mu_t-\mu_t\), interpreted as \(\int\varphi\,d\mu_t=\int\varphi\,d\mu_0+\int_0^t\int[\varphi(F_{\mu_s}(x))-\varphi(x)]\,d\mu_s(x)\,ds\) for every bounded continuous test function \(\varphi\).
Using topological support, define \(T_\delta=\inf\{t\ge0:\ \forall x,y\in\operatorname{supp}\mu_t,\ \|x-y\|_2\le\varepsilon\Rightarrow\|x-y\|_2\le\delta\}\), with \(\inf\varnothing=\infty\). Later measures need not have finite support.
For each of the decision problems \(T_\delta\le h\) and \(T_\delta=\infty\), is it in \(\mathrm P\) or \(\mathrm{NP}\)-hard? State running times in \(m,\tau,L\), including dependence on the encoded thresholds.
For discrete complete-network Hegselmann–Krause dynamics, one uniformly random agent averages its own opinion and those within confidence distance; the expected number of updates to the same edge-length stability criterion is \(O(n^3(n^2+(\varepsilon/\delta)^2))\). This is an update-count bound, rather than a bit-complexity algorithm for computing a hitting time. [Verified source](https://link.springer.com/article/10.1007/s00446-024-00467-3).
No complexity result for this exact measure jump equation and support-based hitting-time problem was located in the search.
Both decision problems are in \(\mathrm P\). More precisely, for every evolution satisfying the stated weak equation,
\[ T_\delta= \begin{cases} 0,&\text{if no initial pair has }\delta<\|a_i-a_j\|_2\le\varepsilon,\\ \infty,&\text{otherwise}. \end{cases} \]
The reason is specific to the measure jump equation: every initial atom retains positive mass at every finite time. This resolves the stated support-based hitting-time question, even though later measures may have infinite support. The proof does not require uniqueness of the evolution.
Fix a bounded continuous test function \(\varphi\), and write
\[ u_\varphi(t)=\int\varphi\,d\mu_t, \qquad v_\varphi(t)=\int\varphi(F_{\mu_t}(x))\,d\mu_t(x). \]
The stipulated weak equation gives
\[ u_\varphi(t)=u_\varphi(0)+\int_0^t\bigl(v_\varphi(s)-u_\varphi(s)\bigr)\,ds. \]
Because both measures involved are probability measures, the integrand has absolute value at most \(2\|\varphi\|_\infty\). Consequently, \(u_\varphi\) is absolutely continuous and satisfies \(u_\varphi'=v_\varphi-u_\varphi\) almost everywhere. Multiplying by \(e^t\) and integrating proves
\[ u_\varphi(t)=e^{-t}u_\varphi(0)+\int_0^t e^{-(t-s)}v_\varphi(s)\,ds. \]
For nonnegative \(\varphi\), the second term is nonnegative, so
\[ \int\varphi\,d\mu_t\ge e^{-t}\int\varphi\,d\mu_0. \]
Now fix an initial opinion \(a_i\). For \(r>0\), take the bounded continuous function
\[ \varphi_r(x)=\max\left\{0,1-\frac{\|x-a_i\|_2}{r}\right\}. \]
Since \(\varphi_r(a_i)=1\), the preceding inequality implies \(\int\varphi_r\,d\mu_t\ge e^{-t}p_i\). As \(r\) decreases to zero, these functions converge pointwise to the indicator of \(\{a_i\}\) and are bounded by \(1\). Dominated convergence therefore yields
\[ \mu_t(\{a_i\})\ge e^{-t}p_i>0 \]
for every finite \(t\). In particular, every \(a_i\) belongs to the topological support of \(\mu_t\).
There are two exhaustive cases.
Thus, for every allowed \(h\ge0\), deciding \(T_\delta\le h\) amounts to checking that no initial violating pair exists. Deciding \(T_\delta=\infty\) amounts to checking that such a pair exists.
Compute, for every \(i<j\), the rational squared distance
\[ D_{ij}=\sum_{k=1}^{m}(a_{ik}-a_{jk})^2. \]
A pair violates the criterion exactly when \(\delta^2<D_{ij}\le\varepsilon^2\). Squaring preserves these comparisons because distances and thresholds are nonnegative. Exact rational arithmetic handles both boundary equalities without approximation.
The algorithm uses \(O(m\tau^2)\) rational arithmetic operations. A conservative bit-complexity bound using schoolbook integer arithmetic is
\[ O\!\left(L+m\tau^2L^2\right). \]
To justify the operand lengths, write each input coordinate as an integer numerator over a positive integer denominator. For any fixed pair, an unreduced denominator for the squared-distance sum is the product of the squared coordinate denominators from that pair. Its bit length is \(O(L)\), since those denominator lengths are part of the total input length. The corresponding numerators and partial sums also have \(O(L)\) bits; summing \(m\) terms adds at most \(O(\log m)\) bits, which is absorbed by \(O(L)\). Each multiplication or comparison therefore costs \(O(L^2)\).
The threshold encodings are included in \(L\). There is no additional dependence on the numerical values of \(h\), \(\varepsilon/\delta\), or the masses. Both problems are polynomial-time solvable for variable \(m\) and \(\tau\).
For a concrete instance, take \(m=1\), \(\mu_0=\frac12\delta_0+\frac12\delta_1\), \(\varepsilon=1\), and \(\delta=\frac12\). Then
\[ \mu_t=\frac{e^{-t}}2\delta_0+\frac{e^{-t}}2\delta_1+(1-e^{-t})\delta_{1/2} \]
satisfies the equation: all support points are within confidence distance, their mean is always \(\frac12\), and differentiation gives the required weak identity.
Although these measures converge weakly to consensus, both endpoints remain in the support at every finite time. Hence \(T_\delta=\infty\).
The cited [asynchronous finite-agent result](https://link.springer.com/article/10.1007/s00446-024-00467-3) concerns an expected update count. The polynomial-time classification here follows directly from persistence of atoms in the stipulated measure equation.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The persistence argument is correct, the two cases determine the hitting time exactly, and the claimed polynomial bit-complexity bound is valid. No major or minor mathematical issues were found.
The output proves its formula for every probability-measure evolution satisfying the stipulated weak equation. It does not assume finite support at later times or uniqueness of the evolution. This is sufficient because the resulting hitting time depends only on the initial support and is identical for every such evolution.
The argument uses the evolution stipulated in the task; it does not independently establish existence of that evolution.
For any bounded continuous test function \(\varphi\), both \(u_\varphi(t)\) and \(v_\varphi(t)\) have absolute value at most \(\|\varphi\|_\infty\). Thus the integrand in the weak equation is bounded by \(2\|\varphi\|_\infty\).
The stipulated integral identity therefore makes \(u_\varphi\) absolutely continuous on every finite time interval, with \(u_\varphi'=v_\varphi-u_\varphi\) almost everywhere. Applying the product rule for absolutely continuous functions to \(e^t u_\varphi(t)\) gives exactly the displayed integrating-factor formula.
For nonnegative \(\varphi\), \(v_\varphi(s)\ge0\), so the resulting inequality \(\int\varphi\,d\mu_t\ge e^{-t}\int\varphi\,d\mu_0\) is justified for every finite \(t\).
The functions \(\varphi_r\) are bounded, continuous, and nonnegative, with \(\varphi_r(a_i)=1\). Consequently, \(\int\varphi_r\,d\mu_0\ge p_i\), regardless of whether other initial atoms lie inside their supports.
For fixed \(t\), these functions converge pointwise to the indicator of \(\{a_i\}\) as \(r\) tends to zero and are dominated by the integrable constant function \(1\). Dominated convergence applies and yields \(\mu_t(\{a_i\})\ge e^{-t}p_i>0\).
A positive-mass atom belongs to the topological support because every neighborhood containing it has positive measure. Thus the persistence conclusion uses the task’s precise notion of support correctly.
If an initial pair satisfies \(\delta<\|a_i-a_j\|_2\le\varepsilon\), both fixed locations remain in the support at every finite time. The same pair therefore violates the criterion at every time in the defining set. That set is empty, and \(T_\delta=\infty\).
Otherwise, the criterion holds at time zero because the initial support is exactly the finite set of distinct opinions with positive masses. Since the infimum is taken over nonnegative times and the set contains zero, \(T_\delta=0\). Subsequent violations would not alter this conclusion.
The cases are exhaustive. Self-pairs cannot violate the condition because their distance is zero and \(\delta>0\). The boundary conventions are also correct: distance \(\delta\) is permitted, while distance \(\varepsilon\) violates the criterion whenever it exceeds \(\delta\).
Since \(h\) is a finite nonnegative rational, \(T_\delta\le h\) holds exactly when \(T_\delta=0\). The infinity decision is its complement on valid inputs.
Comparing squared distances with \(\delta^2\) and \(\varepsilon^2\) is valid because all relevant quantities are nonnegative. Exact rational comparisons preserve both boundary equalities. No numerical dependence on \(h\) or \(\varepsilon/\delta\) enters beyond their encoding lengths.
There are \(O(\tau^2)\) pairs, each requiring \(O(m)\) rational operations.
For a fixed pair, the product of the squared coordinate denominators has bit length \(O(L)\): the sum of the bit lengths of those input denominators is bounded by the total input length. The corresponding numerators and partial sums also have \(O(L)\) bits; the possible additional \(\log m\) contribution is absorbed by \(L\).
Accumulating the terms using the described unreduced product denominators maintains these bounds. Schoolbook arithmetic therefore gives \(O(L^2)\) bit cost per rational operation, establishing the conservative total bound \(O(L+m\tau^2L^2)\). Reading the input accounts for the initial \(O(L)\) term.
In the example, all support points remain within confidence distance and the mean is always \(1/2\). Differentiating the three coefficients gives precisely the weak equation with inflow at \(1/2\). The persistent endpoint masses establish \(T_\delta=\infty\), consistently with the general argument.
The complexity proof does not invoke the cited finite-agent update-count result, so no application of that external theorem requires verification.
Repair feedback: None required. The proof settles both requested decision problems under the task’s stipulated evolution.
⟨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.