| paper | d4-conf-sagt-2013-0001 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: \(\mathrm{NP}\)-hard under polynomial-time Turing reductions · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a finite community template \(G=(V,E)\), thresholds \(c_v\), rational acceptance probabilities \(p_v\), and a fixed schedule \(\pi\), consider a continuum of copies indexed by \(x\in[0,1]\), with edges only between corresponding roles within each copy. What is the exact expected adopting mass \(M=\frac{1}{|V|}\sum_{v\in V}\Pr[X_v=1]\) under the paper's cascade process?
Use the society \(\Omega=[0,1]\times V\), with mass measure \(dx/|V|\) for each role and within-copy edges \((x,u)(x,v)\) whenever \(\{u,v\}\in E\). Every copy uses the same \(c_v\), \(p_v\), and schedule \(\pi\); the objective is the exact expected adopting mass \(M\).
The mirror covers Theorem 4's exact evaluation problem for a fixed non-adaptive schedule in partial-propagation networks; it leaves Theorems 1–3 and 5–6, including the full-propagation and adaptive results, unaddressed.
The strongest positive case I believe is a continuous version of the paper’s partial-propagation evaluation problem, anchored on Theorem 4. Theorem 4 is proved in the paper: in a partial-propagation network, computing the expected number of adopters for a given non-adaptive spreading strategy \(\pi\) is \(\#\mathrm P\)-complete. The proof reduces from a network-reliability problem whose hardness is cited to [18]. The paper’s reduction uses multiple behavior types, so this is not a claim about a one-type special case.
A plausible high-multiplicity regime is a very large collection of independent, replicated communities—say, many campuses or local organizations with the same internal communication layout. Let one community have \(r\) areas, represented by a graph \(G=(V,E)\), with threshold \(c_v\) and initial acceptance probability \(p_v\) for each role \(v\in V\). The continuous society is \(\Omega=[0,1]\times V\): each \(x\in[0,1]\) indexes a community, and \((x,v)\) is its area in role \(v\). Give each role mass \(\mu_v=1/r\). Connect \((x,u)\) to \((x,v)\) exactly when \(\{u,v\}\in E\); communities have no cross-links. Thus every role is repeated across a continuum of communities, while \(r\), the number of distinct structural roles, is finite for each instance. A type is a role together with its behavior and place in the community’s interaction pattern. All copies of that role have the same \(c_v,p_v\), and network role.
Here is the continuous problem, which I would call Continuum Replicated-Template Cascade Evaluation. Its input is a finite template \(G\), its thresholds and rational acceptance probabilities, and a fixed permutation \(\pi\) of its roles. Apply \(\pi\) in every community, so that role \(\pi(i)\) is scheduled at stage \(i\). Each community follows the paper’s opposing-influence cascade rules. The task is to compute the exact expected adopting mass
\[
M(G,c,p,\pi)=\frac{1}{r}\sum_{v\in V}\Pr[X_v=1],
\]
where \(X_v\) is the decision of role \(v\) in one community. The required solution is the exact rational value of \(M\).
This is a continuous-population question: the society is nonatomic across communities, and \(M\) is the fraction of its mass expected to adopt. It preserves the paper’s underlying question—how a fixed order interacts with positive and negative influence on a partial network—rather than making outcomes, time, or axioms the continuous object. The replication scenario is also legible in the authors’ terms: their decision-making units are areas, and the schedule is still an ordering of those areas. In a finite approximation with \(K\) communities, each role occurs \(K\) times, so the number of areas grows while the number of types remains \(r\).
For this mirror, I expect hardness to transfer (Class B). By construction, \(M\) is exactly the expected adopter count for one template divided by \(r\). Multiplying an exact answer by \(r\) recovers the value in Theorem 4, so the continuous evaluation problem is \(\#\mathrm P\)-hard as well. The hard combinatorics remain in the community’s interaction graph; the continuum averages over replicated communities but does not erase that graph structure.
The scope is deliberately narrow: this mirrors Theorem 4’s fixed, non-adaptive schedule evaluation in the partial-propagation setting. It does not claim a continuous counterpart for every result in the paper. It also suggests further questions: does hardness persist for restricted template graphs such as bounded-treewidth networks? Which parameters, including the number of structural types, permit fixed-parameter algorithms? And would a dense graphon-style limit, which changes the interaction model, make evaluation tractable?
The weakest point is that replication gives a clean continuum of areas while retaining the entire hard finite network inside each community. It establishes a credible continuous mirror and a transferred-hardness result, but it does not show that continuizing one large, heterogeneous network dissolves its computational difficulty. The hardness still lives in the structural roles, whose number can grow with the template.
Theorem 4 is a real computational anchor: it asks for the exact expected number of adopters on a partial-propagation graph, and proves that evaluation is \(\#\mathrm P\)-complete. The strongest objection to the proposed mirror is that its “types” do not by themselves describe the interactions. Two copies of role \(v\) are connected to different agents, at their own community coordinates \(x\). So the input needs the fiber structure that pairs roles within each community; the masses \(\mu_v=1/r\) alone do not specify the cascade.
That objection can be repaired by including the repeated network structure as part of the model. Then each template role is repeated across communities, and the adopting mass is the component’s expected adopter count divided by \(r\). The finite template remains intact. This makes the proposed mirror computationally thin: the continuum aggregates copies of the same finite experiment rather than creating mass interactions within one network. But thinness is not enough to reject it under ChoCo’s criteria. Repeated communities are plausible, population is what becomes continuous, and transferred hardness is an intended outcome. I can’t honestly say that this anchor fails.
A denser version has a different weakness. A graphon-style population in which agents interact with positive mass of other agents changes the paper’s local-neighbor process: degrees and thresholds must scale, and the cascade now depends on aggregate influence. That may be a worthwhile new model, but it no longer mirrors Theorem 4’s arbitrary sparse-network evaluation. This narrows the strongest argument against the anchor; it does not rule out continuous mirrors of the paper.
In fact, Theorem 6 supplies a credible alternative even if one sets aside replicated communities. Its setting has a constant number of types and full propagation, so topology does not distinguish otherwise identical areas. Give type \(i\) mass \(\mu_i\), acceptance probability \(p_i\), and a threshold proportional to population size, expressed as a signed-mass cutoff \(\kappa_i\). A schedule can allocate infinitesimal mass to types over time; the current signed adoption mass determines whether the next mass follows its initial probability or the threshold rule. Maximizing final adopting mass is then a continuous scheduling or control problem. Adaptivity may collapse when mass makes the state deterministic, but finding out what optimization remains is itself a recognizable computational question. The threshold rescaling is a natural co-modification of a count-based model, not continuity of the outcome space in place of the population.
So the negative case is weak where the burden is broadest. The replication mirror may be a formal rescaling with limited new algorithmic content, but neither that nor the need to encode network structure defeats it. And a high-multiplicity mirror of Theorem 6 appears sensible on its own. I cannot support the claim that no worthwhile continuous mirror exists in any scenario.
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.