Answer: \(\mathrm{PSPACE}\)-complete, hence \(\mathrm{NP}\)-hard.
Proposition 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIt is PSPACE-complete to determine whether a given opinion diffusion is stabilizable, convergent, and majority dominat- ing respectively.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite role set \(R\), positive rational masses \(\mu_r\) summing to \(1\), rational influence shares \(q_{rs}\geq 0\) with \(\sum_{s\in R}q_{rs}=1\), a threshold \(T\in[1/2,1)\), and rational initial opinion shares \(x_r^0\in[0,1]\), iterate \(a_r^t=\sum_{s\in R}q_{rs}x_s^t\), setting \(x_r^{t+1}=1\) if \(a_r^t>T\), \(x_r^{t+1}=0\) if \(1-a_r^t>T\), and otherwise \(x_r^{t+1}=x_r^t\). Decide whether the process reaches unanimity on opinion \(1\) when \(\sum_{r\in R}\mu_rx_r^0>T\), or on opinion \(0\) when \(\sum_{r\in R}\mu_r(1-x_r^0)>T\); if neither inequality holds, the condition is vacuous.
A society is given by its support: a nonempty list \(R\) of \(\tau=|R|\) roles with positive binary rational masses \(\mu_r\), where \(\sum_{r\in R}\mu_r=1\). Here \(\tau\) is the support size, not the number of possible types; there are \(m=2\) opinions.
The input also contains binary rationals \(T\in[1/2,1)\), \(x_r^0\in[0,1]\), and \(q_{rs}\geq0\) with \(\sum_{s\in R}q_{rs}=1\). The share \(x_r^t\) is the fraction of role \(r\)'s mass holding opinion \(1\); \(q_{rs}\) specifies influence from role \(s\) on role \(r\), independently of the masses, and self-influence is allowed.
For every integer \(t\geq0\), update all roles synchronously: set \(a_r^t=\sum_{s\in R}q_{rs}x_s^t\), and set \(x_r^{t+1}=1\) if \(a_r^t>T\), \(x_r^{t+1}=0\) if \(1-a_r^t>T\), and \(x_r^{t+1}=x_r^t\) otherwise.
Accept exactly when \(\sum_r\mu_rx_r^0>T\) implies that some finite time has \(x_r^t=1\) for every role, and \(\sum_r\mu_r(1-x_r^0)>T\) implies that some finite time has \(x_r^t=0\) for every role. If neither inequality holds, accept. The initial profile is supplied, not universally quantified.
Is this decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m\), \(\tau\), and the total input bit length \(L\).
For finite directed networks with binary initial opinions and uniform influence over each agent's nonempty influencer set, deciding whether the supplied initial majority eventually becomes unanimous is \(\mathrm{PSPACE}\)-complete ([Zhuang et al., 2020](https://research-repository.griffith.edu.au/server/api/core/bitstreams/357bdeb9-c2d4-447b-b70f-701850f199ce/content)).
No result settling the exact rational mass and opinion-share problem above was located in the literature search.
The decision problem is \(\mathrm{PSPACE}\)-complete, and therefore \(\mathrm{NP}\)-hard. Hardness already holds for binary initial shares, uniform masses, and influence rows that are uniform over their nonzero entries.
For the stipulated \(m=2\), there is an exact deterministic algorithm using \(O(2^\tau\tau^2L^2)\) bit operations and \(O(\tau^2L)\) bits of space. Thus the problem admits a polynomial-time algorithm if and only if \(\mathrm{P}=\mathrm{PSPACE}\).
Here, binary rational encoding means that numerators and denominators are written in binary.
We use the network complexity result supplied in the question. Its formulation agrees with Definition 1 and Proposition 1 of [Zhuang et al., *Lifting Majority to Unanimity in Opinion Diffusion*](https://research-repository.griffith.edu.au/server/api/core/bitstreams/357bdeb9-c2d4-447b-b70f-701850f199ce/content):
Given a finite directed network, nonempty influencer sets, a threshold \(T_0\in[1/2,1)\), and a supplied binary initial profile, deciding whether each initial opinion whose population proportion exceeds \(T_0\) eventually becomes unanimous is \(\mathrm{PSPACE}\)-complete. Updates are synchronous, influence is uniform over each influencer set, comparisons are strict, and ties preserve the previous opinion.
The supplied initial profile is part of this source instance; the theorem does not require universal quantification over initial profiles.
Let a source instance have vertex set \(V=\{1,\ldots,n\}\), initial opinions \(b_r^0\in\{0,1\}\), and nonempty influencer sets \(I(r)\subseteq V\). Write \(d_r=|I(r)|\).
Construct an instance of the present problem by setting
\(R=V,\qquad \tau=n,\qquad m=2,\qquad T=T_0,\)
and, for every \(r,s\in V\),
\(\mu_r=\frac1n,\qquad x_r^0=b_r^0,\qquad q_{rs}=\begin{cases}\frac1{d_r}&s\in I(r),\\0&s\notin I(r).\end{cases}\)
These data satisfy every required hypothesis:
For example, the dense influence matrix has encoding length \(O(n^2\log(n+1))\). Together with the copied threshold, the entire construction has polynomial size and can be performed in polynomial time.
We now prove that the trajectories coincide. Let \(b^t\) denote the source profile. At time zero, \(x_r^0=b_r^0\). Suppose \(x_s^t=b_s^t\) for every \(s\). Then
\(a_r^t=\sum_s q_{rs}x_s^t=\frac{|\{s\in I(r):b_s^t=1\}|}{d_r}.\)
Consequently, \(a_r^t>T_0\) holds exactly when the source proportion of opinion \(1\) among \(r\)'s influencers exceeds its threshold. Likewise, \(1-a_r^t>T_0\) holds exactly when the corresponding proportion of opinion \(0\) exceeds the threshold. Both systems preserve the previous opinion when neither strict inequality holds. Therefore \(x_r^{t+1}=b_r^{t+1}\), completing the induction.
The initial majority tests also coincide, because
\(\sum_r\mu_rx_r^0=\frac{|\{r:b_r^0=1\}|}{n},\qquad \sum_r\mu_r(1-x_r^0)=\frac{|\{r:b_r^0=0\}|}{n}.\)
Finally, unanimity at any particular time is identical in the two trajectories. Thus the constructed instance is accepted if and only if the source instance is accepted.
This proves \(\mathrm{PSPACE}\)-hardness, and hence \(\mathrm{NP}\)-hardness.
We next prove membership in \(\mathrm{PSPACE}\), including instances with fractional initial shares.
Lemma. Along any trajectory, \(x_r^t\in\{x_r^0,0,1\}\) for every role and time. Once a coordinate becomes binary, it remains binary.
Proof. An update either preserves the coordinate or replaces it by \(0\) or \(1\). Applying this observation inductively proves both assertions.
Define the set of fractional coordinates at time \(t\) by
\(F_t=\{r:0<x_r^t<1\}.\)
The lemma gives \(F_{t+1}\subseteq F_t\). Moreover, every coordinate in \(F_t\) still equals its initial value.
Consider a consecutive interval of times on which \(F_t\) is constant, and put \(k=\tau-|F_t|\). Only its \(k\) binary coordinates can vary, so at most \(2^k\) distinct profiles occur during that interval.
Whenever the fractional set changes, it strictly shrinks, so \(k\) strictly increases. In particular, there is at most one such interval for each \(k\in\{0,\ldots,\tau\}\). Therefore the whole trajectory contains at most
\(B=\sum_{k=0}^{\tau}2^k=2^{\tau+1}-1\)
distinct profiles.
The update is deterministic. If two profiles coincide, their subsequent trajectories coincide as well. It follows that every profile that is ever reached first appears among times \(0,\ldots,B-1\): a first occurrence at any later time would require more than \(B\) distinct preceding profiles.
Thus checking these \(B\) times suffices to decide whether a prescribed unanimous profile is ever reached.
First compute the initial opinion-\(1\) mass
\(M_0=\sum_r\mu_rx_r^0.\)
At most one of \(M_0>T\) and \(1-M_0>T\) can hold. Indeed, if both held, adding them would give \(1>2T\), contradicting \(T\geq1/2\).
If neither holds, accept immediately. Otherwise, let \(b\in\{0,1\}\) be the uniquely qualifying opinion. Simulate synchronously and inspect the profiles at times \(0,\ldots,B-1\). Accept upon finding \(x_r^t=b\) for every role; reject if all \(B\) checks fail. Section 3 proves this algorithm correct.
To justify exact arithmetic bounds, let \(D\) be the product of the denominators of all input rationals. Its binary length is \(O(L)\). Define the integers
\(Q_{rs}=Dq_{rs},\qquad X_r^0=Dx_r^0,\qquad U_r=D\mu_r,\qquad C=DT.\)
At every time, store \(X_r^t=Dx_r^t\), which belongs to \(\{X_r^0,0,D\}\). For each role, compute
\(A_r^t=\sum_s Q_{rs}X_s^t.\)
The two update tests are exactly
\(A_r^t>CD,\qquad D^2-A_r^t>CD.\)
The initial majority tests similarly compare \(\sum_rU_rX_r^0\) and its complement in \(D^2\) against \(CD\). All comparisons therefore use integers, without rounding.
Because each influence row sums to one and all shares lie in \([0,1]\), every partial sum defining \(A_r^t\) is between \(0\) and \(D^2\). All arithmetic operands consequently have \(O(L)\) bits. With schoolbook arithmetic, one synchronous update takes \(O(\tau^2L^2)\) bit operations.
There are fewer than \(2^{\tau+1}\) inspected profiles. Including preprocessing, the running time is therefore \(O(2^\tau\tau^2L^2)\) for \(m=2\). Storing the scaled influence matrix, initial and current profiles, arithmetic workspace, and an \(O(\tau)\)-bit counter requires \(O(\tau^2L)\) bits.
This establishes membership in \(\mathrm{PSPACE}\). Combined with Section 2, it proves the claimed \(\mathrm{PSPACE}\)-completeness.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned problem. The reduction preserves both the dynamics and the acceptance condition, and the algorithm correctly handles fractional initial shares. No major or minor mathematical issues were found.
The cited source concerns a supplied initial profile: its opinion diffusion instance includes the graph, threshold, and initial opinions. Definition 1 uses the initial population majority and eventual unanimity of that same opinion; Proposition 1 states that deciding this property is \(\mathrm{PSPACE}\)-complete. Its update rule uses synchronous updates, strict threshold comparisons, and retention of the previous opinion otherwise. These match the source problem stated in USER_TASK. [Zhuang et al., Definition 1 and Proposition 1](https://research-repository.griffith.edu.au/server/api/core/bitstreams/357bdeb9-c2d4-447b-b70f-701850f199ce/content).
The prover therefore applies the supplied theorem to the correct decision problem. There is no substitution of a universally quantified initial-profile problem.
The source’s nonempty influencer sets, explicitly stipulated in USER_TASK, ensure that every denominator \(d_r\) in the reduction is positive.
Every constructed instance satisfies the target’s requirements:
The dense matrix encoding bound \(O(n^2\log(n+1))\) is valid. Copying the source threshold adds its existing encoding length. The construction has polynomial size and takes polynomial time.
The trajectory induction is correct. Assuming equality of the profiles at time \(t\), the target’s weighted average equals the source’s proportion of influencers holding opinion \(1\). Its complement equals the corresponding proportion holding opinion \(0\).
Both strict comparisons and the retention case consequently agree. The two threshold conditions cannot hold simultaneously because \(T_0\geq1/2\). The induction includes the initial profile and establishes equality at every nonnegative integer time.
Uniform masses also make both initial majority tests identical to the source population tests. Unanimity in the designated opinion is identical at every time. This covers the case where neither initial opinion qualifies: both acceptance implications are then vacuous.
Thus the reduction is a polynomial many-one reduction preserving acceptance. The conclusions of \(\mathrm{PSPACE}\)-hardness and hence \(\mathrm{NP}\)-hardness follow.
The coordinate lemma is correct: every update either retains the coordinate or replaces it with a binary value. A binary coordinate can therefore never become fractional.
Consequently, \(F_{t+1}\subseteq F_t\), and every still-fractional coordinate retains its initial value. During an interval with fixed \(F_t\), only the remaining \(k\) binary coordinates vary, giving at most \(2^k\) distinct profiles.
Whenever the fractional set changes, its cardinality strictly decreases. Hence \(k\) strictly increases, and there is at most one maximal constant-set interval for each \(k\). The bound
\[
B=2^{\tau+1}-1
\]
is valid.
The first-occurrence argument also holds. In a deterministic trajectory, any repetition makes subsequent evolution repeat; a new profile cannot first occur after a repeated prefix. Thus every reachable profile first appears at one of the times \(0,\ldots,B-1\). Checking these times suffices.
The initial-majority selection is correct. Both qualifying inequalities would imply \(1>2T\), contradicting \(T\geq1/2\). Immediate acceptance when neither holds matches the specification.
The integer scaling is valid. Each input denominator divides their product \(D\), so all defined scaled quantities are integers. Since
\[
a_r^t=A_r^t/D^2,
\]
the comparisons against \(CD\), including the complementary comparison, exactly implement the required strict inequalities.
The initial mass calculation has the same scaling, and its complement in \(D^2\) is correct.
The bit-length bounds hold:
Schoolbook arithmetic gives the claimed \(O(\tau^2L^2)\) cost per synchronous update. Forming \(D\) and scaling the inputs also fit within the overall bound.
The resulting bounds
\[
O(2^\tau\tau^2L^2)
\]
bit operations and
\[
O(\tau^2L)
\]
bits of space are justified. The time-zero check includes initially unanimous profiles, and the argument also covers \(\tau=1\) and threshold equality.
Polynomial space membership combined with the reduction establishes \(\mathrm{PSPACE}\)-completeness. The equivalence between a polynomial-time algorithm and \(\mathrm{P}=\mathrm{PSPACE}\) follows.
The running-time statement correctly fixes \(m=2\), as required by the task; no variable-\(m\) generalization is needed.
No additional mathematical clarification or repair is required.
⟨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.