| paper | d4-conf-ijcai-2020-0518 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 5.1
statement extracted from the paper’s text layer
Given finitely many types \(T\) with rational masses \(\mu_i>0\) summing to \(1\), a rational symmetric contact kernel \(K\) with positive row normalizers, rational \(\alpha\in(0,1]\), and rational \(\varepsilon,\delta\in(0,1)\), define \(Q_{ij}=\mu_jK_{ij}/\sum_\ell\mu_\ell K_{i\ell}\). Starting from \(x_i(0)=0\), evolve \(\dot{x}_i=\alpha(1-x_i)+(1-\alpha)(\sum_jQ_{ij}x_j-x_i)\). Return a certified interval of width at most \(\delta\) containing the first time \(s\) at which \(\max_i(1-x_i(s))\le\varepsilon\).
A finite-type continuous population with masses \(\mu_i\), where each type follows the paper's biased voter update rule against contact probabilities \(Q_{ij}\). The type-level opinion-1 fractions \(x_i\) follow the stated ODE; the objective is the first time every type's dissenting mass is at most \(\varepsilon\).
With the all-zero initial condition, the ODE has dissent fractions \(1-x_i(s)=e^{-αs}\), so the contact kernel and type masses do not affect the threshold time; the proponent does not identify this exact collapse.
fatal: False
The mirror covers Theorem 5.1's voter-model convergence result. It leaves the majority results, including Theorems 4.2, 4.4, and 4.5, outside its scope.
The paper has no named theorem classifying a problem as NP-hard, in P, FPT, or similar. Its closest useful anchor is a proved convergence-time bound: Theorem 5.1, proved in Section 5, shows that under the biased voter rule, the process reaches the all-1 state in \(O((n/\alpha)\log n)\) globally sampled updates with high probability, for any underlying graph and \(\alpha\in(0,1]\). At each update, a uniformly selected agent adopts 1 with probability \(\alpha\), and otherwise copies a uniformly selected neighbor. The paper also notes that the bound holds from any initial opinion configuration. This is a quantitative runtime result, not a computational-complexity classification, so the case for a mirror is necessarily narrow.
The continuous question I find credible is Finite-Type Voter \(\varepsilon\)-Convergence Time. An instance has a finite set \(T\) of \(\tau\) types, rational masses \(\mu_i>0\) summing to 1, a rational symmetric contact kernel \(K_{ij}\), a bias \(\alpha\in(0,1]\), and rational tolerances \(\varepsilon,\delta>0\). The mass \(\mu_i\) is the fraction of the population in type \(i\). Everyone of type \(i\) has the same contact rates with other types, and the same update rule and bias. Write \(Q_{ij}=\mu_jK_{ij}/\sum_\ell\mu_\ell K_{i\ell}\) for the probability a type-\(i\) agent contacts type \(j\). Let \(x_i(s)\) be the fraction of type \(i\) holding opinion 1 at per-capita time \(s\), initially \(x_i(0)=0\). Each unit of population updates at rate 1, giving the voter mean-field dynamics
\[
\dot{x}_i(s)=\alpha(1-x_i(s))+(1-\alpha)\left(\sum_j Q_{ij}x_j(s)-x_i(s)\right).
\]
The question is to return a certified interval of width at most \(\delta\) containing the first time
\[
\tau_\varepsilon=\inf\{s\ge 0:\max_{i\in T}(1-x_i(s))\le\varepsilon\}.
\]
Thus the target is close to complete adoption in every type; the answer is a time, not an encoding of the dynamics.
This is a natural high-multiplicity regime: \(n\) is very large, while \(\tau\) is moderate because agents fall into a small number of roles or cohorts with the same contact patterns. For example, members of a large platform or institution might share a region-and-role contact profile. The population remains the continuous object, while each individual still holds one of the paper’s two discrete opinions. The paper’s technology-adoption motivation and its question about convergence make this a plausible analogue of the authors’ problem.
I expect this continuous question to be tractable. It is a finite-dimensional linear system, and the voter bound has a direct per-capita counterpart: the maximum dissent fraction contracts at least as fast as \(e^{-\alpha s}\), so \(\tau_\varepsilon\le \alpha^{-1}\log(1/\varepsilon)\). Taking \(\varepsilon\) on the order of \(1/n\) gives \(O(\alpha^{-1}\log n)\) per-capita time, or \(O((n/\alpha)\log n)\) globally sampled updates. This is the scaling in Theorem 5.1. A prover could investigate a certified approximation algorithm with complexity in \(\tau\), the input bit length, and the requested precision.
The mirror covers Theorem 5.1 only. I would not use the majority lower bound in Theorem 4.2 as a second anchor: its slow convergence depends on rare, local fluctuations, which a deterministic mass equation may erase. The weakest point is the same distinction that limits the whole case: Theorem 5.1 analyzes a stochastic finite network; it does not give a complexity result for computing a continuous convergence time. The proposed problem preserves the paper’s voter dynamics and convergence objective, but its algorithmic classification would be a new question rather than a result already established by the authors.
The strongest case against the proposed mirror is that its chosen instance makes the computational question disappear. With \(Q\) row-stochastic and every type initially at opinion \(0\), let \(y_i=1-x_i\). The proposed ODE gives
\[
\dot y=-\alpha y+(1-\alpha)(Q-I)y.
\]
Since \(Q\mathbf 1=\mathbf 1\), its solution from \(y(0)=\mathbf 1\) is exactly \(y(s)=e^{-\alpha s}\mathbf 1\). Thus \(\tau_\varepsilon=\alpha^{-1}\log(1/\varepsilon)\), independent of the type masses, support size, and contact kernel. The proposed certified-interval problem is just numerical evaluation of a closed-form expression; its apparent network input plays no role.
That also exposes a mismatch with Theorem 5.1. Its \(n\log n\) scale concerns a finite stochastic population and the last individual reaching opinion \(1\). A continuum has no last individual of positive mass. Replacing exact absorption with an \(\varepsilon\)-mass threshold is sensible, but it creates a different target; setting \(\varepsilon=1/n\) imports a finite population size into a model that has none. The theorem supplies a convergence bound for a process, not an algorithmic problem of computing its convergence time from an encoded society.
The stronger version with arbitrary initial type-level opinion fractions avoids the immediate collapse: then
\[
y(s)=e^{-\alpha s}e^{(1-\alpha)(Q-I)s}y(0).
\]
But this remains a finite-dimensional linear-system calculation. Approximating its threshold time is a numerical linear algebra task, rather than a new complexity landscape of the kind the programme is meant to chart. That is a case against spending programme effort on this anchor, though a simple tractability result can still be worthwhile under the programme’s own criteria.
I cannot make the universal negative case airtight. The paper’s majority result on dense graphs depends on rare finite-population fluctuations, which a deterministic continuum limit erases; a stochastic finite-type or large-deviation mirror might preserve a substantive computational question. That possibility does not rescue this voter mirror, but it does make “no worthwhile mirror in any scenario” stronger than the evidence supports. My honest verdict is that the proponent’s stated voter question is a poor use of the programme, while the paper as a whole may still have a better mirror.
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.