| paper | d4-conf-aaai-2023-1123 |
| 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{coNP}\)-complete under polynomial-time many-one reductions, and \(\mathsf{NP}\)-hard under polynomial-time Turing reductions, even with maximum in-degree \(2\). It is in \(\mathsf{P}\) if and only if \(\mathsf{P}=\mathsf{NP}\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 10
statement extracted from the paper’s text layer
Given a finite Boolean SyDS template \(S=(G,\{f_v\})\), where \(G\) is a DAG of maximum in-degree \(3\), consider an atomless unit-mass population of independent copies of \(S\). Each copy has an internal configuration \(q\in\{0,1\}^{V(G)}\) and follows the template's synchronous update. Decide whether every measurable initial population profile reaches, after some finite time, a profile in which almost every copy is at a fixed point.
Treat each repeated community as a population unit and let \(\mu_q\) be the mass of communities in configuration \(q\in\{0,1\}^{V(G)}\). The template's successor map \(F\) updates the distribution by pushforward; ask whether every initial distribution reaches, in finite time, one supported entirely on \(\operatorname{Fix}(F)\).
Role masses alone do not encode the within-community state correlations used by local rules, so a faithful mirror must represent each whole community configuration and retain the template wiring.
fatal: False
The mirror covers only Theorem 10's coNP-hardness result for ALLCONV on DAGs of maximum in-degree \(3\); it leaves the path-gadget result, the reachability and convergence results, and the treedepth algorithms unaddressed.
My strongest case is a narrow mirror of ALLCONV, the paper’s guarantee that every starting configuration eventually reaches a fixed point.
The anchor is Theorem 10 in the short version of the text (Theorem 9 in the long version). It says that deciding ALLCONV is coNP-hard even when the synchronous dynamic system is Boolean, its network is a DAG, and every node has in-degree at most \(3\). The paper proves this result here by reduction from 3-UNSAT. In full, the underlying question is: given such a system, does *every* initial assignment of Boolean states to its nodes eventually reach a fixed point? The reduction makes a designated node oscillate when the initial states encode a satisfying assignment, so the system has the guarantee exactly when no such assignment exists.
Here is a continuous-population version. Start with a finite Boolean system \(S=(G,\{f_v\})\) on \(n\) nodes. Make a continuum of identical copies of \(S\), indexed by \(r\in[0,1]\). A person is a node-role/copy pair \((v,r)\). The type is the role \(v\): it includes that role’s Boolean update function and its position in the shared network template. Each type has mass \(1/n\), so there is a continuum of agents per type. Agents in different roles connect to their corresponding roles in the same copy: if \(uv\) is an arc of \(G\), then \((u,r)\) influences \((v,r)\).
A population configuration is a measurable family of Boolean states \(x_v(r)\). Its update is
\[
\Phi(x)_v(r)=f_v\bigl(x_v(r),(x_u(r))_{u\in N^-(v)}\bigr).
\]
Call the decision problem Continuum All-Configuration Convergence: given the finite template \(S\), decide whether, for every measurable initial population configuration \(x\), there is a finite time \(T\) such that \(\Phi^{T+1}(x)=\Phi^T(x)\) almost everywhere. The instance is finitely encoded by \(G\) and the local truth tables; a YES answer means every population profile settles, and a NO answer means some profile does not.
This is an exact high-multiplicity regime: a finite approximation has \(M\) copies, \(nM\) agents and \(n\) role types, with \(M\) agents per type. The role types are interchangeable across copies under a joint relabeling of the copy index; the matching between roles is part of the common network structure. At each \(r\), the dynamics are precisely those of the original system. Since the template has only finitely many configurations, if every one converges then there is a common finite time by which they all have reached fixed points. Conversely, any nonconvergent template configuration gives a nonconvergent population profile by assigning it to every copy. Thus the continuous problem is equivalent to ALLCONV on the template, and Theorem 10 gives coNP-hardness for DAG templates of maximum in-degree \(3\). I expect this mirror to fall in Class B: the reduction’s logic lives in the network roles and their update rules, so repeating the population does not remove the hardness.
The scenario is many repeated small interaction modules—teams or communities with the same network roles and synchronous update rules—and the question is whether the entire population is guaranteed to settle from any initial state. The paper’s authors study synchronous network dynamics and explicitly motivate them with diffusion phenomena, so I think they could recognize this as a continuous-population analogue for that repeated-module regime. It keeps individual states Boolean; what becomes continuous is the population across copies. It does not continuize time or replace the question with a mean-field equilibrium question.
This case covers only Theorem 10. Its weakest point is that the copies are uncoupled: the continuum gives a genuine population with fractional role masses, but the computation remains inside each finite module. That makes the mirror exact and the hardness claim robust, while offering no new algorithmic gain from continuous optimization. It also leaves open the more ambitious question of what happens when copies interact through population-level averages, or when the paper’s hardness reduction is restricted to more socially plausible local rules.
The anchor is real: Theorem 9 in the long version (Theorem 10 in the short version) is a named coNP-hardness result for ALLCONV on DAGs of in-degree at most \(3\). The proposed clone construction is also mathematically coherent. Each copy follows the original system, and a constant population profile can represent any starting configuration of that system. Since the template has finitely many configurations, if they all converge, there is a common finite time by which they have settled. Repeating the system over a continuum therefore preserves the universal convergence question exactly.
My strongest objection is about what the construction makes continuous. ChoCo’s society is represented by masses of types. Here, masses of node roles do not determine the dynamics: which \(u\)-agent is paired with which \(v\)-agent matters because the local rule reads their states in the same copy. Two populations can have identical role masses and identical state fractions within each role, yet different cross-role pairings and different next states. The shared copy coordinate \(r\) supplies that extra coupling. To encode it, one must either retain the continuum of matched copies as part of the network structure, or lift each copy to a whole-system type with an internal configuration. The first retains the graph of matched interactions; the second makes each population unit an input-sized dynamical system rather than a node in the paper’s network.
A more population-driven version could couple copies through aggregate state fractions. But arbitrary Boolean update functions depend on joint neighbor states, so role-level fractions generally do not determine the next fractions. Tracking enough joint information can require types that encode whole neighborhoods or configurations. That is a potentially interesting new model, but it changes the dynamics behind Theorem 9/10 rather than giving a faithful mirror of its result.
This leaves a plausible repaired mirror: treat repeated communities as the population units, with each community running the paper’s network. That is a sensible scenario, and I cannot dismiss it because its answer is inherited from the finite theorem or because it offers no continuous-optimization gain. Its vulnerability is narrower: the population continuum sits over copies of one network, while the computational object and its wiring remain the finite template. Whether the authors would regard convergence of a continuum of independent, identical communities as their problem is uncertain.
So the negative case rests on a mismatch between role masses and the relational information the dynamics require. It does not establish that no worthwhile mirror exists. If the authors accept repeated communities as agents and allow the matched-copy structure, the proponent’s anchor survives; my case against a universal “no mirror” verdict is weak.
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.