| paper | d4-conf-ecai-2020-0408 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{PSPACE}\)-complete, hence \(\mathrm{NP}\)-hard. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
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 replicated processor population with finitely many roles, where each role has mass \(\mu_r\), receives influence according to shares \(q_{rs}\), and evolves through synchronous threshold updates of its opinion share.
Role-level influence shares erase within-role neighborhood correlations, so the singleton-role embedding does not show that coarse role blocks reproduce the original network dynamics.
fatal: False
The mirror covers Proposition 1’s majority-domination result; it leaves the stabilizability and convergence results in Proposition 1, and the graph-characterization results, aside.
The strongest mirror is the paper’s majority-dominating decision problem in a replicated processor network. The paper itself motivates opinion diffusion with processors holding replicated data: a large system may have many copies but only a small number of communication roles. For example, millions of replicas might fall into a few hardware and network classes. Agents in role \(r\) have the same threshold and receive the same fractions \(q_{rs}\) of their influence from each role \(s\). The mass \(\mu_r\) is the fraction of the whole system in role \(r\). The current opinion is a changing state: \(x_r\) denotes the fraction of role \(r\) holding opinion \(1\).
This model preserves synchronous threshold updating while replacing individual edges with type-level influence shares. Given a finite role set \(R\), rational masses \(\mu_r>0\) summing to \(1\), rational shares \(q_{rs}\geq 0\) with \(\sum_s q_{rs}=1\), threshold \(T\in[1/2,1)\), and rational initial shares \(x_r^0\in[0,1]\), define \(a_r^t=\sum_s q_{rs}x_s^t\). Then role \(r\) moves entirely to opinion \(1\) if \(a_r^t>T\), entirely to \(0\) if \(1-a_r^t>T\), and otherwise keeps its current opinion share. The initial mass of opinion \(1\) is \(\sum_r\mu_rx_r^0\).
Call the decision problem Continuous Majority-to-Unanimity Reachability. The question is whether the process reaches unanimity on its initial majority opinion: does some \(t\) have \(x_r^t=1\) for every \(r\), if \(\sum_r\mu_rx_r^0>T\), or \(x_r^t=0\) for every \(r\), if \(\sum_r\mu_r(1-x_r^0)>T\)? If neither side exceeds \(T\), the majority-dominating condition is vacuous, as in the paper’s definition. A solution is the yes/no answer; a yes instance has a finite trajectory to the target state. This is a legitimate continuous-population question: it asks whether the initial population majority takes over under the same synchronous majority rule, with mass and type-level influence replacing individual counts and edges.
My anchor is Proposition 1, which states that deciding whether a given opinion diffusion is stabilizable, convergent, and majority dominating is PSPACE-complete for each property. The paper proves membership directly. For hardness, it cites [6, Theorem 1] for stabilizability, gives a reduction for majority domination using the machine-simulation construction from [6], and says convergence follows by a nearly identical argument. I rely on the majority-dominating part: this paper proves that deciding whether a configured diffusion reaches unanimity on its initial majority is PSPACE-hard.
The continuous question has a direct discrete embedding. For a graph on \(n\) individuals, give each individual its own role with mass \(1/n\); set \(q_{ij}=1/d(i)\) when \(j\) influences \(i\), and \(0\) otherwise; and set each initial \(x_i^0\) to that individual’s binary opinion. The dynamics and majority test then match exactly. So for unrestricted support size \(\tau=|R|\), I expect the continuous problem to be PSPACE-complete: the paper’s hardness transfers, and the continuous process can be simulated in polynomial space.
There is also a useful high-multiplicity parameter question. Each coordinate \(x_r^t\) can only be its initial value, \(0\), or \(1\), so there are at most \(3^\tau\) states. This gives an \(O(3^\tau\operatorname{poly}(\tau,L))\)-time algorithm, where \(L\) is the rational input bit length. Thus the mirror is fixed-parameter tractable in support size even though its unrestricted complexity is PSPACE-complete. The further question is whether processors with many copies per role admit sharper algorithms, or whether PSPACE-hardness can persist under additional restrictions on the role-share matrix.
I expect the authors would recognize this as their problem in a block-mixed, replicated-network regime: the threshold dynamics and the majority-to-unanimity objective are unchanged, and the paper explicitly discusses replicated processors. The mirror covers Proposition 1’s majority-dominating result; it does not claim to continue the paper’s graph-characterization propositions.
The weakest point is that the mirror’s strongest hardness embedding uses one role per original vertex. It establishes hardness as \(\tau\) grows, but not hardness when the population is very large and \(\tau\) stays small. The type-level mixing model also omits within-role differences in who influences whom. That limits the scope of the hardness claim, but leaves a concrete and plausible high-multiplicity problem: whether role-level influence shares suffice to predict takeover in a large replicated system.
Proposition 1 is a real computational anchor: the paper proves PSPACE-completeness for majority domination. But the proposed role model does not preserve the graph dynamics behind that result.
A role’s influence shares say what fraction of its incoming edges comes from each role. They do not say which individuals supply those edges. That missing information can change an update. With threshold \(T=1/2\), suppose two agents in role \(A\) each receive influence only from role \(B\). If one sees two \(1\)-opinion agents and the other sees two \(0\)-opinion agents, they have identical role-level shares but update differently. The same aggregate opinion share for \(B\) cannot represent both outcomes. Yet majority domination asks about arbitrary initial profiles, where those arrangements matter.
The model is well-defined if every agent in a role responds to the same aggregate influence share. It is then a complete-mixing or mean-field process, rather than a population relaxation of the paper’s arbitrary directed graphs. That is a recognizable opinion-diffusion question, and replicated processors could motivate it. The cost is that the model changes the network structure that the paper’s controlling sets, neighborhood bounds, and PSPACE reduction analyze. It asks about a restricted new process, not the continuous-population version of Proposition 1.
A more faithful mirror would retain local neighborhoods, for example with a graphon or a distribution over neighborhood profiles. But then the state must preserve where opinions sit in that structure: agents with the same hardware role can still have different relevant neighbors. For arbitrary graphs, the representation may need a distinct coordinate for nearly every individual. The continuous masses then encode the original vertices without producing the small-support regime that makes continuization valuable. Coarsening those coordinates returns to the role model and loses the neighborhood information again.
So the negative case is limited. A computational study of mean-field processor networks may be worthwhile, but I cannot honestly rule out that scenario, and the paper’s explicit replicated-processor motivation makes it plausible. The strongest objection is narrower: the proposed low-support mirror either averages away the local correlations central to the named PSPACE result or retains enough structure that the population no longer has meaningful high multiplicity. That weakens the claim that this paper offers a worthwhile continuous mirror; it does not establish that no such scenario exists.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.