| paper | d4-journals-ai-2026-0066 |
| 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: \(\mathsf{NP}\)-complete, hence \(\mathsf{NP}\)-hard. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 7
statement extracted from the paper’s text layer
Given finitely many roles \(T\), rational role masses \(\mu_{t,q}\) for each initial opinion state \(q\subseteq\{a,b\}\), a symmetric nonnegative rational exposure matrix \(K\), rational thresholds \(\theta_{t,1},\theta_{t,2}\), and a four-round horizon, choose rational seed masses \(x_{t,q,r}\ge 0\), where \(r\subseteq\{a,b\}\setminus q\) and \(\sum_r x_{t,q,r}=\mu_{t,q}\). At each round, role \(t\) receives opinion-\(c\) exposure \(E^i_{t,c}=\sum_{u\in T}K_{tu}M^i_{u,c}\), where \(M^i_{u,c}\) is the mass of role \(u\) holding \(c\); unopinionated agents adopt \(c\) at threshold \(\theta_{t,1}\), and agents already holding the other opinion adopt \(c\) at threshold \(\theta_{t,2}\). Minimize \(\sum_{t,q,r}|r|x_{t,q,r}\) subject to stabilization by round \(4\) and zero mass holding exactly one opinion.
A finite-role population with rational masses, common role-level exposure given by a symmetric matrix \(K\), and rational seed allocations; minimize total seeded mass while preserving the paper’s threshold update and exact balance objective.
Section 6.3 discusses agent types while retaining an explicit network, so the paper offers limited direct evidence that its authors would recognize replacing individual neighborhoods with common role-level exposure.
fatal: False
The mirror covers Theorem 7’s four-round balanced seed-selection hardness regime; it leaves the other hardness theorems and the paper’s FPT results unaddressed.
The strongest mirror I see is a mass version of the paper’s four-round seed-selection problem. It continuizes the population while retaining the two opinions, threshold-triggered spread, seed budget, and exact balancing requirement.
A plausible regime is a large online platform or other population exposed through a small number of recurring social roles. A role specifies an agent’s two thresholds, initial opinion status, and exposure to every other role. Members of a role have the same response to the same role-level exposure. There may be millions of agents but only \(\tau\) distinct roles. This resembles the paper’s own discussion in Section 6.3 of clustering agents into types and specifying seed choices by type. The mirror uses that type structure for deterministic population mass; it does not make opinions, time, or outcomes continuous.
Here is a concrete problem for a prover. Call it Continuous Four-Round Two-Opinion Target-Mass Selection. An instance has a finite set \(T\) of \(\tau\) roles, rational masses \(\mu_t\ge 0\) summing to \(1\), a symmetric rational exposure matrix \(K\), and rational thresholds \(\theta_{t,1},\theta_{t,2}\) for each role. It also gives the mass in each role with each initial opinion state \(q\subseteq\{a,b\}\), and a rational seed-mass budget \(\beta\).
The decision is how much mass of each role and initial state to seed with each permissible additional set of opinions. Write \(x_{t,q,r}\ge 0\) for the mass initially in state \(q\) that receives the additional seed set \(r\subseteq\{a,b\}\setminus q\); the allocations for each \((t,q)\) must sum to its given mass. Their cost is \(\sum_{t,q,r}|r|x_{t,q,r}\), which must be at most \(\beta\).
At round \(i\), let \(M^i_{u,c}\) be the mass of role \(u\) holding opinion \(c\). Every member of role \(t\) receives exposure \(E^i_{t,c}=\sum_{u\in T}K_{tu}M^i_{u,c}\). The paper’s rule carries over: a member with neither opinion gains \(c\) when \(E^i_{t,c}\ge\theta_{t,1}\); one who already has the other opinion gains \(c\) when \(E^i_{t,c}\ge\theta_{t,2}\). The state masses then update synchronously. A feasible solution is a seed allocation for which the process has stabilized by round \(4\) and the mass holding exactly one opinion is zero. Thus the outcome is balanced person by person, not merely in aggregate. The optimization version minimizes seed mass.
My lead anchor is Theorem 7, proved in this paper. It shows that \(\twoTSS\) is \(\W[1]\)-hard parameterized by the combined value \(B+\td(G)+\fvs(G)+\operatorname{4pvc}(G)\), even when every successful activation process stabilizes within \(\fin=4\) rounds and \(f_1(v)\le f_2(v)\) for every vertex. It also proves an ETH lower bound: for that same combined parameter \(k\), no algorithm runs in \(g(k)n^{o(k/\log k)}\), for arbitrary computable \(g\), under those restrictions. The theorem is proved here by a reduction from Partitioned Subgraph Isomorphism.
The corresponding continuous question is whether the mass-allocation problem above can be solved exactly, or classified as hard, when the sparse role-exposure graph has small treedepth, feedback vertex number, and \(4\)-path vertex-cover number, with the seed budget \(\beta\) and rational input bit length accounted for. This is the question I would hand to a prover; the theorem itself does not answer it. I would weakly expect continuum-specific hardness (Class C) as the first working hypothesis: even at four rounds, choices about which role exposures cross thresholds create many coupled activation patterns. But Theorem 7 does not establish that conclusion. Its reduction relies on gadgets forcing discrete seed selections, and fractional seeding could dissolve their exactly-one choice. Hardness would transfer (Class B) if a continuous reduction can force endpoint masses; a tractable polyhedral structure (Class A) is also possible.
The mirror covers only the paper’s four-round, balanced-spread seed-selection question. The paper changes individual neighbors and integer thresholds into role-level exposure and rational thresholds because members of a role must respond identically to type-level mass. That is the key co-modification, and it is why this is a mean-field version of their influence model rather than a direct restatement.
The weakest point is that the exposure matrix averages away individual neighborhoods. A referee could reasonably ask whether authors studying sparse local networks would recognize that as their problem. The case for recognition is that the type-based seed formulation is already anticipated in Section 6.3, while the mirror keeps their deterministic threshold process and balancing objective. The case is strongest for platforms or institutions where members of a role really do face comparable exposure mixtures. A useful next result would be a discrete-to-continuous dictionary: determine when high-multiplicity instances approximate this model and whether fractional seed mass changes the optimum or the hardness.
Theorem 7 is a real computational anchor: it proves \(\W[1]\)-hardness for a named seed-selection problem, with a four-round restriction and an ETH lower bound. There is no existing continuous treatment in the paper that answers its complexity question. The best case against the mirror therefore has to challenge the population model, not the theorem’s status or what its answer might be.
The theorem’s hard instances make the network itself carry the choices. Candidate vertices and edges occupy distinct positions in incidence gadgets; paths and neighborhoods encode which choices match. Under ChoCo’s complete-type definition, two agents with different relevant neighborhoods are different types, even if they share thresholds and seed status. The paper’s Section 6.3 says its constructions use only a constant number of agent types, but that does not establish a constant number of complete types once network position is included.
The proponent’s role-exposure matrix gives a clean four-round mass process, but it replaces sparse, individual neighbor counts with exposure from pools of roles. That is a substantial change in the interaction structure. Section 6.3 does discuss clustered thresholds and seed probabilities, while retaining a network; it does not itself endorse replacing that network with an aggregate exposure matrix. A more faithful sparse-network limit could track local neighborhoods, but seed choices and activation states must remain consistent across overlapping neighborhoods. Masses of neighborhood types alone need not capture those dependencies. Tracking enough network context may then leave the model without the finite, compact type input that makes the proposed computation tractable to formulate.
This is a serious limitation of the specific mirror, but it is not a decisive objection to every mirror. A large platform with recurring roles and genuinely mixed exposure is plausible, and its mass model is well-posed; the authors might recognize it as a useful variant. Nothing in the paper rules that out. So the honest negative case is weak at the universal claim: it exposes a gap between the paper’s sparse, identity-bearing networks and the proposed mean-field model, but it cannot show that no worthwhile population mirror 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.